Bird
Raised Fist0

Design an Online Tic-Tac-Toe Game - Board, Player, Win Detection, Replay

LLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design an Online Tic-Tac-Toe Game
40 min · medium
medium

Design an online Tic-Tac-Toe game system that supports two players playing remotely, maintains game state, detects wins or draws, and allows replaying the game without restarting the application.

Given Info
  • The board is a 3x3 grid with cells that can be empty, X, or O.
  • Two players take turns placing their marks on empty cells.
  • The system must detect a win (3 in a row horizontally, vertically, or diagonally) or a draw (board full with no winner).
  • Players can replay the game multiple times without restarting the system.
  • Concurrency must be handled to prevent race conditions when players make moves simultaneously.
📋
Guided Steps
1/5
Step 1
Define the Board and Cell Representation
Design classes to represent the Tic-Tac-Toe board and its cells, ensuring the board can track cell states and provide methods to update and query cells.
💡 Hint
Use an enum to represent cell states (EMPTY, X, O) to leverage Java's type safety and exhaustive switch checks.
Key Decision
Use enum CellState { EMPTY, X, O } for cell states - enums provide compile-time safety and prevent invalid values unlike Strings.
Interviewer Expectation
Mid: Defines Board with 2D CellState array. Senior: Explains enum benefits over String for cell states, preventing runtime bugs from invalid values.
Step 2
Design Player Abstraction and Turn Management
Create Player classes and a mechanism to manage turns between two players, ensuring only the correct player can make a move at a time.
💡 Hint
Use an abstract Player class with subclasses for human or AI players if needed; use synchronized methods or locks to enforce turn order.
Key Decision
abstract class Player with playerId and mark (CellState) fields - abstract because it holds shared instance state; interface cannot hold fields in Java.
Interviewer Expectation
Mid: Uses abstract Player class with subclasses. Senior: Explains why abstract class is needed for shared state and how synchronized move() method prevents concurrent moves.
Step 3
Implement Win and Draw Detection Logic
Design a method to detect if the current board state results in a win or draw after each move.
💡 Hint
Encapsulate win detection in Board class; use synchronized method to ensure consistent reads of board state during detection.
Key Decision
public synchronized boolean checkWin(CellState mark) - synchronized to prevent race conditions where board state changes mid-check.
Interviewer Expectation
Mid: Implements win detection by checking rows, columns, diagonals. Senior: Explains thread interleaving where unsynchronized check can read inconsistent board state causing false negatives.
Step 4
Enable Replay Functionality Without Restart
Design how the game can be reset and replayed multiple times without restarting the application, preserving player info and game history.
💡 Hint
Use composition: Game class contains Board and Player instances; reset method clears board state but retains player objects. Use volatile boolean gameActive to manage game lifecycle visibility across threads.
Key Decision
volatile boolean gameActive to ensure visibility of game state changes across threads; reset() method clears board cells atomically.
Interviewer Expectation
Mid: Provides reset method to clear board. Senior: Explains volatile ensures threads see updated gameActive flag immediately, preventing stale reads during replay.
Step 5
Handle Concurrency for Online Moves
Ensure that when two players attempt to make moves concurrently, the system prevents invalid state updates or turn violations.
💡 Hint
Synchronize the method that places a mark on the board and checks turn validity atomically; consider using ReentrantLock for finer control if needed.
Key Decision
public synchronized boolean placeMark(int row, int col, Player player) - atomic check of turn and cell availability prevents race conditions.
Interviewer Expectation
Mid: Uses synchronized placeMark to serialize moves. Senior: Traces race condition where without synchronization, two threads read cell empty and both place marks, corrupting game state.
🔌
API Design Challenge
Design the API endpoints and methods to support remote play between two players, including making moves, querying game state, and replaying games.
Hints
  • Use RESTful endpoints with clear resource naming, e.g., /games/{gameId}/moves.
  • Consider WebSocket or Server-Sent Events for real-time updates to players.
  • Include authentication and session management to identify players and enforce turn order.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use enum for cell states to prevent invalid values at compile time.
  • abstract Player class with shared instance state fields.
  • Synchronized methods for atomic board updates and win detection.
  • volatile flag for game lifecycle visibility across threads.
  • Synchronized placeMark method to prevent concurrent invalid moves.
Good to Have - 30%
  • Composition relationship between Game, Board, and Player with clear lifecycle ownership.
  • Reset method that clears board state but retains player objects for replay.
  • Clear separation of concerns: Board handles state, Player handles identity and moves.
  • Use of synchronized keyword instead of coarse-grained locking for better concurrency.
  • Explanations of thread interleavings causing race conditions.
Bonus - 10%
  • Use ReentrantLock for finer concurrency control if needed.
  • Support for AI Player subclass extending abstract Player.
  • Detailed concurrency scenario tracing in interviewer explanations.
Anti-patterns to Avoid
Using String for cell or player states leads to runtime bugs due to typos and no compile-time validation, causing invalid game states and crashes.
Not synchronizing board updates causes race conditions leading to corrupted game state and inconsistent gameplay.
Not using volatile for shared flags causes stale reads and inconsistent game lifecycle behavior, resulting in threads acting on outdated game status.
Using interface for Player when instance state is needed forces duplicating state in subclasses, violating DRY and complicating turn management.
✅
Model Answer
▼ Reveal

This design models an online Tic-Tac-Toe game supporting two remote players with concurrency-safe state management, win/draw detection, and replay capability. It uses Java enums for cell states, an abstract Player class for shared state, synchronized methods for atomic updates, and volatile flags for thread visibility.

Key Decisions
  • Use enum CellState { EMPTY, X, O } to leverage Java's type safety and prevent invalid cell values.
  • Implement abstract Player class with fields playerId and mark to hold shared state; interfaces cannot hold fields in Java.
  • Synchronize placeMark and checkWin methods to prevent race conditions and ensure consistent board state reads.
  • Use volatile boolean gameActive flag in Game class to ensure visibility of game lifecycle changes across threads.
  • Use composition in Game class to manage Board and Player lifecycle; reset method clears board without recreating players.
  • Consider ReentrantLock for finer concurrency control if scaling beyond simple synchronized methods.
  • Design API endpoints for remote play with RESTful design and real-time updates via WebSocket or SSE.
  • Use enum CellState for cell values to leverage Java's type safety and exhaustive switch statements.
  • abstract class Player holds shared instance state like playerId and mark; interface cannot hold fields in Java.
  • Board uses a 2D CellState array with synchronized methods to update and query cells atomically.
  • Win detection logic is encapsulated in Board with synchronized checkWin method to prevent inconsistent reads.
  • volatile boolean gameActive flag ensures visibility of game lifecycle state changes across threads.
  • Game class composes Board and Player instances; reset method clears board state but retains player objects (composition with lifecycle ownership).
  • placeMark method is synchronized to atomically check turn validity and cell availability, preventing race conditions.
  • Replay functionality resets board state without recreating Player objects, adhering to Single Responsibility Principle.
  • Avoid using String for states or player marks to prevent runtime bugs due to typos and lack of compile-time checks.
  • Concurrency control uses synchronized methods and volatile flags to ensure thread-safe game state updates.

Practice

(1/5)
1. In a Chess game design, the Board class has a private constructor and a static synchronized getInstance() method. Which design pattern is applied here and why is it the correct choice?
easy
A. Singleton pattern, to ensure only one board instance exists during the game.
B. Factory pattern, because it creates different types of boards dynamically.
C. Builder pattern, to construct the board step-by-step with pieces placed.
D. Prototype pattern, to clone board states for move validation.

Solution

  1. Step 1: Identify the role of private constructor and static synchronized method

    The private constructor prevents external instantiation, and the static synchronized getInstance() ensures thread-safe single instance creation.

  2. Step 2: Match to design pattern intent

    This matches the Singleton pattern, which restricts instantiation to one object, suitable for a unique game board shared across the system.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Singleton ensures single board instance across threads [check]
Hint: Private constructor + static synchronized method -> Singleton [check]
Common Mistakes:
2. In designing the Meeting Scheduler, should the Attendee entity be modeled as an abstract class or an interface, considering that attendees can be both internal employees and external guests with different data and behaviors?
easy
A. Interface, because it enforces a fixed implementation and prevents state duplication.
B. Interface, because attendees only define behaviors without shared state, allowing multiple inheritance.
C. Abstract class, because it allows sharing common state like name and email while enabling method overrides.
D. Abstract class, because interfaces cannot have any methods related to scheduling conflicts.

Solution

  1. Step 1: Analyze state and behavior needs

    Attendee has shared state (name, email) and some common behavior, which favors abstract class to avoid duplicating fields.

  2. Step 2: Evaluate interface limitations

    Interfaces cannot hold state, so using interface would force duplication or external state holders, complicating design.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Shared state + behavior -> abstract class [check]
Hint: Shared state? Use abstract class, not interface [check]
Common Mistakes:
3. In the Restaurant Management System, the OrderManager class has a private constructor and a static synchronized getInstance() method. Which design pattern is applied here and why is it the correct choice?
easy
A. Factory pattern, because it controls object creation centrally.
B. Builder pattern, to incrementally construct complex orders.
C. Singleton pattern, to ensure only one instance manages all orders globally.
D. Prototype pattern, to clone existing orders efficiently.

Solution

  1. Step 1: Identify the pattern from constructor and method

    The private constructor prevents external instantiation, and the static synchronized getInstance() method ensures a single shared instance, which matches the Singleton pattern.

  2. Step 2: Why Singleton fits OrderManager

    OrderManager must coordinate all orders centrally to avoid conflicting states; multiple instances would cause inconsistent order tracking.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Private constructor + synchronized static getInstance() -> Singleton [check]
Hint: Private constructor + static getInstance() -> Singleton [check]
Common Mistakes:
4. In a traffic light system design, a TrafficLightController class has a private constructor and a static synchronized getInstance() method. Which design pattern is applied here and why is this the correct choice?
easy
A. Factory pattern to create multiple controller instances safely
B. Builder pattern to construct complex traffic light states
C. Prototype pattern to clone traffic light controllers for scalability
D. Singleton pattern to ensure only one controller manages the traffic lights

Solution

  1. Step 1: Identify the pattern from constructor and method

    The private constructor prevents external instantiation, and the static synchronized getInstance() ensures a single shared instance, matching Singleton pattern characteristics.

  2. Step 2: Why Singleton fits traffic light controller

    Only one controller should coordinate the traffic lights to avoid conflicting states; multiple instances would cause inconsistent signals.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Private constructor + synchronized getInstance() -> Singleton pattern [check]
Hint: Private constructor + static synchronized getInstance() -> Singleton [check]
Common Mistakes:
5. In designing a Vehicle abstraction for a parking system, should Vehicle be an abstract class or an interface if it needs to hold state like licensePlate? Why?
easy
A. Interface, because it enforces method signatures without implementation or state, which is ideal for all vehicles.
B. Abstract class, because it forces all subclasses to implement all methods explicitly.
C. Interface, because Java 8+ allows default methods that can hold state variables safely.
D. Abstract class, because it can hold shared state like licensePlate and provide common behavior implementations.

Solution

  1. Step 1: Identify state holding needs

    licensePlate is shared state, which interfaces cannot hold as fields.

  2. Step 2: Evaluate options

    Abstract classes can hold state and provide default behavior; interfaces cannot hold instance fields, only constants.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Abstract class holds shared state like licensePlate [check]
Hint: State needs abstract class, interfaces only declare behavior [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard