Win condition checking in LLD - System Design Exercise

Design: Win Condition Checking System

Design focuses on the logic and architecture for checking win conditions in turn-based games. UI, networking, and player matchmaking are out of scope.

Functional Requirements

FR1: Support multiple game types (e.g., Tic-Tac-Toe, Connect Four, Chess) with different win conditions

FR2: Check if a player has won after each move

FR3: Provide real-time feedback on game status (win, draw, ongoing)

FR4: Allow easy addition of new game types and win conditions

FR5: Ensure correctness and efficiency in win condition evaluation

Non-Functional Requirements

NFR1: Must handle up to 1000 concurrent games

NFR2: Win check latency should be under 50ms per move

NFR3: System availability should be 99.9%

NFR4: Memory usage should be optimized for embedded or low-resource environments

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Game state manager to hold current board or game data

Win condition evaluator module with pluggable rules

Move processor to update state and trigger checks

Result notifier to inform about game status

Configuration loader for different game rules

Design Patterns

Strategy pattern for different win condition algorithms

Observer pattern for notifying game status changes

State pattern for managing game phases

Command pattern for moves and undo functionality

Reference Architecture

  +---------------------+
  |   Move Processor    |
  +----------+----------+
             |
             v
  +----------+----------+       +---------------------+
  |  Game State Manager  |<---->|  Configuration Loader |
  +----------+----------+       +---------------------+
             |
             v
  +----------+----------+
  | Win Condition Evaluator |
  +----------+----------+
             |
             v
  +----------+----------+
  |   Result Notifier    |
  +---------------------+

Components

Move Processor

Custom logic module

Receives player moves, validates them, and updates the game state

Game State Manager

In-memory data structures

Maintains current state of the game board or pieces

Configuration Loader

JSON/YAML config files

Loads rules and win condition definitions for different games

Win Condition Evaluator

Strategy pattern implementations

Checks if the current game state meets any win or draw conditions

Result Notifier

Event emitter or callback system

Notifies the system or players about game results or ongoing status

Request Flow

1. Player submits a move to Move Processor

2. Move Processor validates and updates Game State Manager

3. Game State Manager provides updated state to Win Condition Evaluator

4. Win Condition Evaluator applies game-specific rules to check for win/draw

5. Result Notifier sends status update (win/draw/ongoing) to the game controller or UI

Database Schema

Not applicable as system is designed for in-memory low-latency checking; persistent storage is out of scope.

Scaling Discussion

Bottlenecks

High concurrency causing contention on shared game state

Complex win condition logic increasing latency

Memory usage growing with many concurrent games

Solutions

Partition games across multiple instances or threads to reduce contention

Optimize win condition algorithms with early exits and caching

Use lightweight data structures and clean up finished games promptly

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing components and data flow, 10 minutes discussing scaling and optimizations, 5 minutes summarizing.

Emphasize modular design for supporting multiple games

Explain choice of design patterns for flexibility and maintainability

Discuss trade-offs between latency and complexity

Highlight how to handle concurrency and resource constraints

Show awareness of real-time feedback importance

Practice

1. What is the primary purpose of win condition checking in a game system?

easy

A. To update the player's score after each move

B. To determine if a player has won the game by matching symbols in a row, column, or diagonal

C. To reset the game board after a draw

D. To display the game instructions to the player

Solution

1. Step 1: Understand the role of win condition checking

   Win condition checking is used to decide if the game has ended with a winner by checking patterns on the board.

2. Step 2: Identify the correct purpose among options

   Only To determine if a player has won the game by matching symbols in a row, column, or diagonal describes checking rows, columns, or diagonals for matching symbols to declare a winner.

3. Final Answer:

   To determine if a player has won the game by matching symbols in a row, column, or diagonal -> Option B

4. Quick Check:

   Win condition checking = Determine winner [OK]

Hint: Win condition means checking if someone won the game [OK]

Common Mistakes:

• Confusing win checking with score updating
• Thinking it resets the game board
• Assuming it shows instructions

2. Which of the following code snippets correctly checks a row for a win in a 3x3 tic-tac-toe board represented as a 2D array board?

easy

A. if board[row][0] != board[row][1] != board[row][2]:

B. if board[0][row] == board[1][row] == board[2][row] != None:

C. if board[row][0] == board[row][1] == board[row][2] != None:

D. if board[0][0] == board[1][1] == board[2][2] != None:

Solution

1. Step 1: Identify row checking syntax

   Checking a row means comparing all elements in the same row index but different columns.

2. Step 2: Match code to row check

   if board[row][0] == board[row][1] == board[row][2] != None: compares board[row][0], board[row][1], and board[row][2], which is correct for a row check.

3. Final Answer:

   if board[row][0] == board[row][1] == board[row][2] != None: -> Option C

4. Quick Check:

   Row check = compare same row elements [OK]

Hint: Row check compares same row, different columns [OK]

Common Mistakes:

• Mixing row and column indices
• Using != instead of == for equality
• Checking diagonal instead of row

3. Given the following 3x3 board state:

board = [["X", "O", "X"],
         ["O", "X", "O"],
         ["O", "X", "X"]]

Which of these checks will correctly identify a win for 'X' on the main diagonal?

medium

A. board[0][0] == board[1][1] == board[2][2] == "X"

B. board[0][2] == board[1][1] == board[2][0] == "X"

C. board[0][0] == board[0][1] == board[0][2] == "X"

D. board[2][0] == board[2][1] == board[2][2] == "X"

Solution

1. Step 1: Identify main diagonal positions

   Main diagonal cells are at positions (0,0), (1,1), and (2,2).

2. Step 2: Check which option matches main diagonal and 'X'

   board[0][0] == board[1][1] == board[2][2] == "X" compares these exact positions to 'X', correctly checking the main diagonal win.

3. Final Answer:

   board[0][0] == board[1][1] == board[2][2] == "X" -> Option A

4. Quick Check:

   Main diagonal check = positions (0,0),(1,1),(2,2) [OK]

Hint: Main diagonal is top-left to bottom-right [OK]

Common Mistakes:

• Confusing main diagonal with anti-diagonal
• Checking wrong row or column
• Using equality with wrong symbol

4. Consider this code snippet for checking a column win:

def check_column(board, col):
    return board[0][col] == board[1][col] == board[2][col]

What is the main issue with this code when used for win condition checking?

medium

A. It only checks rows, not columns

B. It uses incorrect indices for columns

C. It returns a list instead of a boolean

D. It does not check if the cells are not empty or None

Solution

1. Step 1: Analyze the equality check

   The code checks if all three cells in the column are equal but does not verify if they are non-empty.

2. Step 2: Identify missing condition for valid win

   Without checking for None or empty, it may falsely report a win if all cells are empty.

3. Final Answer:

   It does not check if the cells are not empty or None -> Option D

4. Quick Check:

   Check for non-empty cells to confirm win [OK]

Hint: Always check cells are not empty before confirming win [OK]

Common Mistakes:

• Ignoring empty or None cells in equality
• Mixing row and column indices
• Expecting a list return instead of boolean

5. You are designing a scalable win condition checker for an n x n board game. Which approach best balances efficiency and scalability?

hard

A. Only check the row, column, and diagonals related to the last move

B. Check all rows, columns, and both diagonals after every move

C. Check the entire board for a winner after every move

D. Check only the diagonals after every move

Solution

1. Step 1: Understand the cost of checking all lines

   Checking all rows, columns, and diagonals after every move is expensive for large boards.

2. Step 2: Focus on last move's related lines

   Only the row, column, and diagonals that include the last move can change the win state, so checking these is efficient and scalable.

3. Final Answer:

   Only check the row, column, and diagonals related to the last move -> Option A

4. Quick Check:

   Check only affected lines after move for efficiency [OK]

Hint: Check only lines affected by last move for best performance [OK]

Common Mistakes:

• Checking entire board every time wastes resources
• Ignoring diagonals in win checking
• Checking unrelated rows or columns