Board and piece hierarchy in LLD - Scalability & System Analysis

Scalability Analysis - Board and piece hierarchy

Growth Table: Board and Piece Hierarchy

Scale	Number of Boards	Number of Pieces	Memory Usage	Operations per Second	Complexity
100 Boards	100	1,600 (16 per board)	Low (MBs)	Low (few hundred ops)	Simple object management
10,000 Boards	10,000	160,000	Moderate (GBs)	Moderate (thousands ops)	Need efficient data structures
1,000,000 Boards	1,000,000	16,000,000	High (hundreds GBs)	High (hundreds of thousands ops)	Requires sharding and caching
100,000,000 Boards	100,000,000	1,600,000,000	Very High (TBs)	Very High (millions ops)	Distributed system with partitioning

First Bottleneck

The first bottleneck is memory and CPU on the application server managing the board and piece objects. As the number of boards and pieces grows, keeping all objects in memory and processing moves or state changes becomes expensive. The object hierarchy and frequent updates cause CPU load and memory pressure before storage or network limits.

Scaling Solutions

• Horizontal scaling: Add more application servers to distribute board and piece management load.
• Caching: Cache frequently accessed board states or piece positions to reduce recomputation.
• Sharding: Partition boards across servers by ID ranges or user groups to limit per-server load.
• Efficient data structures: Use lightweight representations for pieces and boards to reduce memory footprint.
• Event-driven updates: Process piece moves asynchronously to smooth CPU spikes.

Back-of-Envelope Cost Analysis

• Assuming 16 pieces per board, 1 million boards = 16 million pieces.
• Each piece object ~200 bytes -> 3.2 GB memory for pieces alone.
• Boards with metadata ~1 KB each -> 1 GB memory for boards.
• Operations: 10 moves per second per board -> 10 million ops/sec at 1 million boards.
• Network bandwidth depends on update size; small updates (~100 bytes) -> ~1 GB/s bandwidth.

Interview Tip

Start by explaining the system components: boards and pieces as objects. Discuss how load grows with number of boards and pieces. Identify bottlenecks in memory and CPU. Propose scaling solutions like sharding and caching. Use real numbers to justify your approach. Keep answers structured: growth, bottleneck, solution, cost.

Self Check

Your application server handles 1,000 piece updates per second. Traffic grows 10x to 10,000 updates per second. What do you do first?

Answer: Add horizontal scaling by deploying more application servers behind a load balancer to distribute the update processing load and avoid CPU bottlenecks.

Key Result

The main scalability challenge is managing memory and CPU load for many board and piece objects; horizontal scaling and sharding are key to handle growth beyond thousands of boards.

Practice

1. What is the main purpose of having a base Piece class in a board game design?

easy

A. To manage network communication between players

B. To define common properties like position and type for all pieces

C. To handle user input events

D. To store the entire board layout

Solution

1. Step 1: Understand the role of a base class

   A base class provides shared properties and methods for all derived classes, avoiding repetition.

2. Step 2: Apply to board game pieces

   All pieces share common traits like position and type, so the base Piece class holds these.

3. Final Answer:

   To define common properties like position and type for all pieces -> Option B

4. Quick Check:

   Base class = common properties [OK]

Hint: Base class holds shared traits for all pieces [OK]

Common Mistakes:

• Confusing board layout storage with piece properties
• Thinking base class handles user input
• Assuming base class manages network tasks

2. Which of the following is the correct way to declare a subclass King that extends a base Piece class in a typical object-oriented design?

easy

A. class King extends Piece { constructor(position) { super(position); } }

B. function King() { this.position = position; } extends Piece

C. class King inherits Piece { constructor() { } }

D. King = Piece + position

Solution

1. Step 1: Identify correct subclass syntax

   In modern OOP, a subclass uses extends keyword and calls super() in constructor.

2. Step 2: Check each option

   class King extends Piece { constructor(position) { super(position); } } uses correct syntax: class King extends Piece { constructor(position) { super(position); } }.

3. Final Answer:

   class King extends Piece { constructor(position) { super(position); } } -> Option A

4. Quick Check:

   Subclass syntax = extends + super() [OK]

Hint: Subclass uses extends and calls super() in constructor [OK]

Common Mistakes:

• Using incorrect keywords like inherits
• Placing extends after function declaration
• Trying to add properties with '+' operator

3. Given this code snippet for a board and pieces, what will be the output of console.log(board.pieces[0].type);?

class Piece {
  constructor(type, position) {
    this.type = type;
    this.position = position;
  }
}
class Board {
  constructor() {
    this.pieces = [];
  }
  addPiece(piece) {
    this.pieces.push(piece);
  }
}
const board = new Board();
board.addPiece(new Piece('Knight', 'B1'));

medium

A. undefined

B. "B1"

C. Error: pieces is not defined

D. "Knight"

Solution

1. Step 1: Understand object creation and storage

   A new Piece with type 'Knight' and position 'B1' is created and added to board.pieces.

2. Step 2: Access the first piece's type

   board.pieces[0] refers to the first piece, so board.pieces[0].type is 'Knight'.

3. Final Answer:

   "Knight" -> Option D

4. Quick Check:

   First piece type = 'Knight' [OK]

Hint: First piece type is stored in pieces[0].type [OK]

Common Mistakes:

• Confusing position with type
• Assuming pieces array is empty
• Expecting an error due to missing pieces

4. Identify the error in this piece hierarchy code snippet:

class Piece {
  constructor(type, position) {
    this.type = type;
    this.position = position;
  }
}
class Queen extends Piece {
  constructor(position) {
    this.type = 'Queen';
    this.position = position;
  }
}

medium

A. Position should not be passed to constructor

B. Queen class should not have a constructor

C. Missing call to super() in Queen constructor

D. Type should be passed as parameter to Queen constructor

Solution

1. Step 1: Review subclass constructor rules

   In subclasses, the constructor must call super() before using this.

2. Step 2: Check Queen constructor

   Queen constructor assigns this.type and this.position without calling super(), causing an error.

3. Final Answer:

   Missing call to super() in Queen constructor -> Option C

4. Quick Check:

   Subclass constructor must call super() first [OK]

Hint: Always call super() before using this in subclass constructor [OK]

Common Mistakes:

• Forgetting super() call in subclass constructor
• Trying to assign this before super()
• Assuming constructor is optional in subclass

5. You want to design a scalable board game system where each piece type has unique movement rules. Which design approach best supports adding new piece types without changing existing code?

hard

A. Use a base Piece class and create subclasses for each piece type implementing their own move logic

B. Store all piece types and moves in a single large switch-case statement

C. Keep piece types as strings and handle moves in a separate global function with if-else

D. Use a flat list of pieces with no hierarchy and hardcode moves in the board class

Solution

1. Step 1: Understand scalability and extensibility

   Good design allows adding new piece types without modifying existing code, following open-closed principle.

2. Step 2: Evaluate design options

   Subclassing Piece lets each piece implement its own move logic, enabling easy extension.

3. Final Answer:

   Use a base Piece class and create subclasses for each piece type implementing their own move logic -> Option A

4. Quick Check:

   Subclassing = scalable and extensible design [OK]

Hint: Subclass each piece type for unique moves [OK]

Common Mistakes:

• Using large switch-case blocks that are hard to maintain
• Handling moves globally with if-else reduces flexibility
• Hardcoding moves in board class limits scalability