Move validation in LLD - System Design Exercise

Design: Move Validation System

Design the core move validation logic and system architecture. Exclude UI design and player matchmaking.

Functional Requirements

FR1: Validate moves in a turn-based board game (e.g., chess, checkers).

FR2: Ensure moves follow game rules before applying them.

FR3: Support multiple game types with different move rules.

FR4: Provide immediate feedback if a move is invalid.

FR5: Allow undoing moves only if they were valid and last move.

FR6: Support concurrent games for multiple players.

FR7: Log moves for replay and audit.

Non-Functional Requirements

NFR1: Handle up to 10,000 concurrent games.

NFR2: Validate moves with p99 latency under 100ms.

NFR3: System availability of 99.9%.

NFR4: Support extensibility for new game rules without downtime.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

❓ Question 7

Key Components

Game state storage (in-memory or database)

Move validation engine (rule checker)

API layer for receiving moves

Cache for fast state access

Logging and audit service

Undo management component

Design Patterns

Command pattern for moves

Strategy pattern for different game rules

Event sourcing for move history

Cache aside pattern for game state

CQRS for separating read/write operations

Reference Architecture

Client
  |
  v
API Gateway
  |
  v
Move Validation Service <--> Game State Cache <--> Persistent Storage
  |
  v
Logging Service

Undo Service <--> Move Validation Service

Rule Engine (plug-in modules) <--> Move Validation Service

Components

API Gateway

REST/HTTP

Receive move requests from clients and route to validation service

Move Validation Service

Microservice (e.g., Node.js, Python)

Validate moves using game rules and current game state

Game State Cache

Redis or in-memory store

Store current board state for fast access during validation

Persistent Storage

Relational DB (PostgreSQL) or NoSQL

Store game states, move history, and audit logs

Logging Service

Kafka or centralized logging

Record all moves and validation results for replay and audit

Undo Service

Microservice

Manage undo requests and validate undo conditions

Rule Engine

Modular plug-in system

Encapsulate game-specific move validation logic

Request Flow

1. Client sends move request to API Gateway.

2. API Gateway forwards move to Move Validation Service.

3. Move Validation Service fetches current game state from Game State Cache.

4. Move Validation Service calls Rule Engine module for the specific game to validate the move.

5. If valid, Move Validation Service updates Game State Cache and Persistent Storage with new move.

6. Move Validation Service sends success response to client.

7. Move Validation Service sends move details to Logging Service.

8. If undo requested, Undo Service checks last move validity and updates state accordingly.

Database Schema

Entities: - Game: game_id (PK), game_type, current_state, status - Move: move_id (PK), game_id (FK), player_id, move_data, timestamp, valid_flag - Player: player_id (PK), name - UndoLog: undo_id (PK), game_id (FK), move_id (FK), timestamp Relationships: - Game 1:N Move - Player 1:N Move - Move 1:1 UndoLog (optional)

Scaling Discussion

Bottlenecks

Game State Cache saturation under high concurrent games.

Move Validation Service CPU load with complex rule checks.

Database write latency for move history logging.

Undo Service consistency under concurrent undo requests.

Solutions

Partition cache by game_id to distribute load and use sharding.

Scale Move Validation Service horizontally with stateless design.

Use asynchronous logging with batching to reduce DB write pressure.

Implement optimistic concurrency control and locking in Undo Service.

Interview Tips

Time: 10 minutes for requirements and clarifications, 15 minutes for architecture and components, 10 minutes for scaling and trade-offs, 10 minutes for Q&A.

Clarify game types and validation strictness early.

Explain modular rule engine for extensibility.

Describe caching strategy for low latency validation.

Discuss data consistency and undo handling.

Highlight scalability and fault tolerance approaches.

Practice

1. What is the primary purpose of move validation in a system design context?

easy

A. To create user interfaces

B. To speed up the system by skipping checks

C. To store user data securely

D. To ensure changes follow rules and prevent invalid actions

Solution

1. Step 1: Understand move validation role

   Move validation checks if a requested change or move follows system rules.

2. Step 2: Identify its main goal

   The goal is to prevent invalid or harmful actions that could break system logic or data.

3. Final Answer:

   To ensure changes follow rules and prevent invalid actions -> Option D

4. Quick Check:

   Move validation = Prevent invalid moves [OK]

Hint: Move validation means checking rules before allowing changes [OK]

Common Mistakes:

• Confusing validation with data storage
• Thinking validation speeds up by skipping checks
• Mixing validation with UI creation

2. Which of the following is a correct basic check in move validation logic?

easy

A. if move.position = max_position:
return True

B. if move.position == 'any':
return True

C. if move.position < 0 or move.position > max_position:
return False

D. if move.position > max_position then return False

Solution

1. Step 1: Check syntax correctness

   if move.position < 0 or move.position > max_position: return False uses proper comparison operators and syntax for boundary check.

2. Step 2: Identify errors in other options

   if move.position == 'any': return True uses string instead of number, C uses assignment (=) instead of comparison (==), D uses invalid syntax 'then'.

3. Final Answer:

   if move.position < 0 or move.position > max_position: return False -> Option C

4. Quick Check:

   Boundary check uses < and > with proper syntax [OK]

Hint: Use proper comparison operators and syntax for validation checks [OK]

Common Mistakes:

• Using assignment '=' instead of comparison '=='
• Using invalid keywords like 'then'
• Checking position against wrong data types

3. Given the code snippet for move validation, what will be the output if move.position = 5 and max_position = 4?

def validate_move(move, max_position):
    if move.position < 0 or move.position > max_position:
        return False
    return True

print(validate_move(move, max_position))

medium

A. True

B. False

C. Error

D. null

Solution

1. Step 1: Evaluate condition with given values

   move.position = 5, max_position = 4, so 5 > 4 is true.

2. Step 2: Determine return value

   Since condition is true, function returns False.

3. Final Answer:

   False -> Option B

4. Quick Check:

   5 > 4 triggers False return [OK]

Hint: Check boundary conditions carefully to predict output [OK]

Common Mistakes:

• Assuming 5 <= 4 is true
• Confusing return values
• Ignoring condition logic

4. Identify the bug in this move validation function:

def validate_move(move, max_position):
    if move.position <= 0 or move.position >= max_position:
        return False
    return True

medium

A. It incorrectly disallows move.position = 0

B. It allows move.position = max_position which should be invalid

C. It uses wrong comparison operators for boundaries

D. It returns true for all positions

Solution

1. Step 1: Analyze boundary conditions

   Condition disallows move.position <= 0, so position 0 is invalid.

2. Step 2: Check if position 0 should be allowed

   Usually position 0 is valid boundary, so disallowing it is a bug.

3. Final Answer:

   It incorrectly disallows move.position = 0 -> Option A

4. Quick Check:

   Check boundary inclusiveness carefully [OK]

Hint: Check if boundary conditions exclude valid edge values [OK]

Common Mistakes:

• Confusing < and <= in conditions
• Assuming 0 is always invalid
• Ignoring inclusive vs exclusive boundaries

5. In a system where moves must be validated for both boundary and occupancy, which design approach best ensures scalability and maintainability?

hard

A. Use separate modular validators for boundary and occupancy checks, composed in sequence

B. Combine all validation logic in a single monolithic function

C. Skip occupancy checks to improve performance

D. Validate moves only after applying them to the system state

Solution

1. Step 1: Consider modular design benefits

   Separating boundary and occupancy checks into modules improves clarity and reusability.

2. Step 2: Evaluate scalability and maintainability

   Modular validators can be updated independently and composed flexibly, aiding scalability.

3. Final Answer:

   Use separate modular validators for boundary and occupancy checks, composed in sequence -> Option A

4. Quick Check:

   Modular design = scalable and maintainable [OK]

Hint: Modular validation improves system scalability and clarity [OK]

Common Mistakes:

• Combining all logic makes code hard to maintain
• Skipping important checks reduces reliability
• Validating after applying moves risks inconsistent state