Extensibility (NxN board, multiple players) in LLD - System Design Exercise

Design: Extensible Board Game System

Design focuses on the core game engine and architecture for extensibility. UI, network communication, and persistence are out of scope.

Functional Requirements

FR1: Support a board game with a flexible NxN board size.

FR2: Allow multiple players (more than two) to participate in a game.

FR3: Players can join, leave, and take turns in order.

FR4: Game rules should be adaptable to different board sizes and player counts.

FR5: Provide a way to track game state and determine the winner or draw.

FR6: Support basic game actions like placing a piece or moving a piece.

Non-Functional Requirements

NFR1: The system should handle board sizes from 3x3 up to 100x100.

NFR2: Support up to 10 players in a single game.

NFR3: Game state updates should be processed with low latency (<100ms).

NFR4: The design should allow easy addition of new game rules or player types.

NFR5: The system should be maintainable and testable with clear separation of concerns.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Board representation module

Player management and turn controller

Game rules engine or strategy pattern

Game state manager

Move validator

Design Patterns

Strategy pattern for game rules

Observer pattern for state changes

Command pattern for player actions

Factory pattern for creating players and pieces

Reference Architecture

 +--------------------+       +--------------------+       +--------------------+
 |   Player Manager   |<----->|   Turn Controller  |<----->|   Game State       |
 +--------------------+       +--------------------+       +--------------------+
          ^                             ^                             ^
          |                             |                             |
          |                             |                             |
 +--------------------+       +--------------------+       +--------------------+
 |   Board Module     |<----->|  Rules Engine      |<----->|  Move Validator    |
 +--------------------+       +--------------------+       +--------------------+

Components

Player Manager

Object-oriented classes

Manage player information, joining, leaving, and player order.

Turn Controller

State machine or controller class

Control turn order and notify players when it's their turn.

Game State

In-memory data structures

Store current board state, player states, and game progress.

Board Module

2D array or matrix abstraction

Represent the NxN board and provide methods to update and query cells.

Rules Engine

Strategy pattern classes

Encapsulate game rules and logic for different board sizes and player counts.

Move Validator

Validation logic module

Check if player moves are valid according to current rules and game state.

Request Flow

1. 1. Player Manager registers players and assigns unique IDs.

2. 2. Turn Controller determines which player's turn is next.

3. 3. Player submits a move command to the system.

4. 4. Move Validator checks if the move is valid based on the Rules Engine and current Game State.

5. 5. If valid, Board Module updates the board state.

6. 6. Game State updates player statuses and checks for win/draw conditions via Rules Engine.

7. 7. Turn Controller advances to the next player.

8. 8. Observers or UI components are notified of state changes.

Database Schema

Entities: - Player {player_id (PK), name, status} - Game {game_id (PK), board_size, current_turn_player_id, status} - BoardCell {game_id (FK), row, column, occupant_player_id (nullable)} - Move {move_id (PK), game_id (FK), player_id (FK), from_position (nullable), to_position, timestamp} Relationships: - Game has many Players (N players per game) - Game has many BoardCells (NxN cells) - Player makes many Moves - Moves update BoardCells

Scaling Discussion

Bottlenecks

Large board sizes increase memory and processing time for move validation.

Multiple players increase complexity of turn management and state synchronization.

Rules Engine complexity grows with more game variants and player interactions.

Real-time updates may cause latency if many players act simultaneously.

Solutions

Optimize board representation using sparse data structures for large boards.

Use efficient turn scheduling algorithms and event-driven notifications.

Modularize Rules Engine with plug-in architecture to isolate complexity.

Implement caching and incremental state updates to reduce processing load.

Interview Tips

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

Explain how the design supports flexible board sizes and multiple players.

Describe the use of design patterns for extensibility and maintainability.

Discuss how turn management works with many players.

Highlight how the system validates moves and updates game state consistently.

Address potential bottlenecks and scaling strategies.

Practice

1. What is the main benefit of designing a game system with an NxN board and support for multiple players?

easy

A. It allows the game to be easily extended to different board sizes and more players without major code changes.

B. It limits the game to only two players and a fixed board size.

C. It makes the game run faster by using fixed-size arrays only.

D. It removes the need for input validation.

Solution

1. Step 1: Understand extensibility in game design

   Extensibility means the system can grow or change easily without rewriting code.

2. Step 2: Apply extensibility to NxN board and multiple players

   Using flexible data structures and modular code allows changing board size and player count easily.

3. Final Answer:

   It allows the game to be easily extended to different board sizes and more players without major code changes. -> Option A

4. Quick Check:

   Extensibility = Easy growth [OK]

Hint: Extensibility means easy to add features later [OK]

Common Mistakes:

• Thinking fixed size is more extensible
• Ignoring input validation importance
• Assuming extensibility means faster code

2. Which of the following code snippets correctly initializes a flexible NxN board in Python for any given size n?

easy

A. board = [[0]*n]*n

B. board = [[0 for _ in range(n)] for _ in range(n)]

C. board = [0]*n

D. board = [0 for _ in range(n)]

Solution

1. Step 1: Understand list initialization for 2D board

   Using list comprehension creates independent inner lists for each row.

2. Step 2: Compare options for correct 2D board creation

   board = [[0 for _ in range(n)] for _ in range(n)] creates a list of lists with separate inner lists, avoiding shared references.

3. Final Answer:

   board = [[0 for _ in range(n)] for _ in range(n)] -> Option B

4. Quick Check:

   Independent rows = board = [[0 for _ in range(n)] for _ in range(n)] [OK]

Hint: Use nested list comprehensions for independent 2D lists [OK]

Common Mistakes:

• Using [[0]*n]*n causes shared inner lists
• Initializing only 1D list for 2D board
• Confusing list multiplication with comprehension

3. Given a game system supporting multiple players, what will be the output of this Python snippet?

players = ['Alice', 'Bob', 'Carol']
turns = 5
for i in range(turns):
    current = players[i % len(players)]
    print(current)

medium

A. Bob Carol Alice Bob Carol

B. Alice Bob Carol Carol Carol

C. Alice Alice Alice Alice Alice

D. Alice Bob Carol Alice Bob

Solution

1. Step 1: Understand modulo for cycling players

   The modulo operator cycles index through player list length (3).

2. Step 2: Trace each iteration's player

   i=0 -> Alice, i=1 -> Bob, i=2 -> Carol, i=3 -> Alice, i=4 -> Bob.

3. Final Answer:

   Alice Bob Carol Alice Bob -> Option D

4. Quick Check:

   Modulo cycles players = Alice Bob Carol Alice Bob [OK]

Hint: Use modulo to cycle through players repeatedly [OK]

Common Mistakes:

• Not using modulo causes index errors
• Assuming players list is longer than turns
• Confusing player order in output

4. Identify the bug in this code snippet for initializing a variable-sized board and multiple players:

def setup_game(n, players):
    board = [[None]*n]*n
    for p in players:
        print(f"Player: {p}")
    return board

setup_game(3, ['A', 'B'])

medium

A. The board rows are references to the same list, causing shared updates.

B. The players list is not printed correctly.

C. The function does not return anything.

D. The board size is fixed to 3 regardless of input.

Solution

1. Step 1: Analyze board initialization

   Using [[None]*n]*n creates rows that reference the same list object.

2. Step 2: Understand impact of shared references

   Changing one cell affects all rows because they share the same inner list.

3. Final Answer:

   The board rows are references to the same list, causing shared updates. -> Option A

4. Quick Check:

   Shared inner lists cause bugs = The board rows are references to the same list, causing shared updates. [OK]

Hint: Avoid list multiplication for nested lists [OK]

Common Mistakes:

• Ignoring shared reference problem
• Thinking players print is incorrect
• Assuming function returns nothing

5. You are designing a turn-based game with an NxN board and support for multiple players. Which design approach best supports easy extensibility for future features like variable board sizes, more players, and custom rules?

hard

A. Write all game logic in one large function for simplicity.

B. Use fixed-size arrays and hardcoded player count with separate functions for each board size.

C. Use flexible data structures (lists/dictionaries), modular functions, and validate inputs dynamically.

D. Use global variables for board and players to avoid passing parameters.

Solution

1. Step 1: Identify extensibility requirements

   Extensibility needs flexible data structures and modular code to adapt easily.

2. Step 2: Evaluate design options

   Use flexible data structures (lists/dictionaries), modular functions, and validate inputs dynamically. uses lists/dictionaries and modular functions with input validation, supporting future changes well.

3. Final Answer:

   Use flexible data structures (lists/dictionaries), modular functions, and validate inputs dynamically. -> Option C

4. Quick Check:

   Modular + flexible data = extensible design [OK]

Hint: Modular code + flexible data = easy extensibility [OK]

Common Mistakes:

• Using fixed sizes limits future changes
• Writing monolithic functions reduces flexibility
• Using globals causes maintenance issues