Advanced Data Structures & Algorithms

Java Backend Modernization

Beginner's Guide to Data Structures

Agentic AI Systems

Data Engineering & Spark Mastery

Low-Level Design Interview Prep

Microservices Interview Roadmap

Design Patterns Interview Roadmap

Distributed Systems Interview Roadmap

Mastering Python Development

System Design Interview Prep

Distributed Systems Refresher

AI Engineering Launchpad

Architecture Patterns for Scalable Systems

RAG & Vector Search Mastery

Production DevOps & Reliability

Enterprise Patterns Playbook

Master Coding Interviews

Coding Techniques Interview Roadmap

Data Structures Interview Roadmap

Architecture Patterns Interview Roadmap

software-engineering-principles

Migrate your Spring Boot services from thread-pool exhaustion to JDK 21 virtual threads — the practical Spring developer guide

Adapting to Virtual Threads for Spring Developers

how-it-works-internals-explained

From WAL and MVCC to fsync and isolation levels — the internals behind every ACID guarantee in PostgreSQL, MySQL, Oracle, and SQL Server.

ACID Properties Explained: How SQL Databases Guarantee Atomicity, Consistency, Isolation, and Durability

How modern NoSQL databases achieve atomicity and isolation without a single machine

ACID Transactions in Distributed Databases: DynamoDB, Cosmos DB, and Spanner Compared

llm-engineering

Is an LLM a brain in a jar? To make it truly useful, we need to give it access to the world. This guide explains RAG and Agents.

Advanced AI: Agents, RAG, and the Future of Intelligence

Production AI needs explicit routing, memory, execution, and evaluation layers rather than one loop.

AI Architecture Patterns: Routers, Planner-Worker Loops, Memory Layers, and Evaluation Guardrails

datastructures-and-algorithms

Master shortest paths, dependency resolution, and cycle detection with robust Java solutions.

Advanced Graph Algorithms: Dijkstra, Topological Sort, and Disjoint Set Union (DSU)

An LLM can talk, but an AI Agent can *act*. We explain how Agents use the ReAct framework to brow...

AI Agents Explained: When LLMs Start Using Tools

A production-first guide to picking the right vector index for recall, latency, memory, and update patterns.

ANN Index Types Explained: When to Choose Flat, HNSW, IVF, or IVF-PQ

apache-spark-engineering

Process petabytes with Python: understand Spark's execution model, DataFrame transformations, partitioning strategy, and real-time streaming.

Apache Spark for Data Engineers: RDDs, DataFrames, and Structured Streaming

ACID guarantees consistency. BASE guarantees availability. We explain the trade-offs between SQL...

BASE Theorem Explained: How it Stands Against ACID

machine-learning-fundamentals

From the query-key-value formulation to multi-head attention — the mechanism that made transformers dominate AI

Attention Mechanism Explained: How Transformers Learn to Focus

system-design-interview-prep

They all sit in front of your servers. But do you need Nginx, HAProxy, or Kong? We clarify the roles of each component.

API Gateway vs. Load Balancer vs. Reverse Proxy: What's the Difference?

architecture-patterns-for-production-systems

Mobile apps need less data than Desktop dashboards. Why serve them the same JSON? The Backend for Frontend (BFF) pattern solves this.

Backend for Frontend (BFF): Tailoring APIs for UI

BFS explores graphs level by level using a queue — the key to shortest paths and level-order problems.

BFS — Breadth-First Search: Level-by-Level Graph Exploration

Backtracking is a brute-force algorithmic technique that solves problems by trying to build a sol...

Exploring Backtracking Techniques in Data Structures

big-data-engineering

Choose ingestion, serving, and ownership patterns deliberately when data platforms start to scale.

Big Data Architecture Patterns: Lambda, Kappa, CDC, Medallion, and Data Mesh

Why traditional databases fail at scale, what the 5 Vs really mean, and a practical map of the big data ecosystem from ingestion to insights.

Big Data 101: The 5 Vs, Ecosystem, and Why Scale Breaks Everything

Not all Binary Trees are created equal. We explain Full, Complete, Perfect, and Balanced Binary T...

Exploring Different Types of Binary Trees

Master Big O notation: measure algorithm efficiency from O(1) to O(n²) with growth diagrams, worked examples, and the interview mental model.

Big O Notation Explained: Time Complexity, Space Complexity, and Why They Matter in Interviews

Binary search has five distinct patterns — classic, leftmost, rightmost, rotated arrays, and 2D matrices.

Binary Search Patterns: Five Variants Every Senior Engineer Knows

low-level-design-guide

OOP design of an elevator system: Encapsulation, Abstraction, Polymorphism, SOLID principles, and two design patterns — all in one domain model.

LLD for Elevator System: Designing a Smart Lift

Designing a parking lot is the 'Hello World' of OOP Design. Break down LLD using OOP pillars, SOLID, and classic design patterns.

LLD for Parking Lot System: Designing a Smart Garage

Designing a movie booking system involves handling concurrency (no double bookings!), managing complex hierarchies, and ensuring a smooth user experie

LLD for Movie Booking System: Designing BookMyShow

How do you match a rider with a driver in real-time? We break down the Low-Level Design of a ride-sharing app using the Observer and Strategy patterns

LLD for Ride Booking App: Designing Uber/Lyft

A classic interview problem. We design an extensible Tic-Tac-Toe game that supports N*N grids, multiple players, and different winning strategies.

LLD for Tic-Tac-Toe: Designing an Extensible OOP Game

## Scenario context

A hotel has 10 floors and 3 elevators. At any moment:
- External requests come in: "Someone on Floor 5 pressed UP."
- Internal requests come in: "Someone inside Lift 1 pressed Floor 10."
- The system must decide which car to dispatch, and which order to serve floors.

This is a classic **State Machine + Scheduling** design. The key insight is that a lift behaves differently based on its current state — and we should…

This walkthrough focuses on **The Hotel Lift Problem: What We Are Designing**.

Before making a design choice, clarify:

- A hotel has 10 floors and 3 elevators.
- At any moment: - External requests come in: "Someone on Floor 5 pressed UP." - Internal requests come in: "Someone inside Lift 1 pressed Floor 10." - The system must decide which car to dispatch, and which order to serv…
- This is a classic State Machine + Scheduling design.

**Concepts in play:** low-level-design-systems, jvm-internals-and-garbage-collection, design-patterns-gof, design-principles-solid

## Stage 1 — Elevator System Basics: Entities, States, and Button Types

- Before writing a single line of code it helps to name every moving part in plain English.
- Core entities: States an ElevatorCar can be in: - IDLE — the car is stopped and has no pending stops.
- - MOVING UP — the car is travelling upward and serving stops along the way.
- - MOVING DOWN — the car is travelling downward and serving stops along the way.

*Applies **low-level-design-systems** to the decision above.*

**Observable outcome:** - MOVING DOWN — the car is travelling downward and serving stops along the way.

## Stage 2 — Domain Model: The Core Entities

- - ElevatorCar: Holds a sorted set of destination floors.
- Has a state (IDLE, MOVING UP, MOVING DOWN).
- Assigns incoming Request to the best car.
- - Request: Either ExternalRequest (floor + direction pressed outside) or InternalRequest (destination floor pressed inside the car).

*Applies **jvm-internals-and-garbage-collection** to the decision above.*

```mermaid
classDiagram
    class Building {
        +List~Floor~ floors
        +List~ElevatorCar~ cars
        +Dispatcher dispatcher
        +handleExternalRequest(Request r)
    }
    class ElevatorCar {
        +int id
        +int currentFloor
        +Direction direction
        +ElevatorState state
        -TreeSet~Integer~ stops
        +addStop(int floor)
        +move()
        +getCurrentFloor() int
    }
    class Dispatcher {
        -DispatchStrategy strategy
        +assign(Request r) ElevatorCar
    }
    class Request {
        +int sourceFloor
        +Direction direction
    }
    class ElevatorState {
        <<interface>>
        +handleExternalRequest(ElevatorCar car, Request r)
        +handleInternalRequest(ElevatorCar car, int floor)
        +isIdle() bool
    }
    class DispatchStrategy {
        <<interface>>
        +assign(Request request, List~ElevatorCar~ available) ElevatorCar
    }
    class IdleState {
        +handleExternalRequest(ElevatorCar, Request)
        +handleInternalRequest(ElevatorCar, int)
        +isIdle() bool
    }
    class MovingUpState {
        +handleExternalRequest(ElevatorCar, Request)
        +handleInternalRequest(ElevatorCar, int)
        +isIdle() bool
    }
    class MovingDownState {
        +handleExternalRequest(ElevatorCar, Request)
        +handleInternalRequest(ElevatorCar, int)
        +isIdle() bool
    }
    class NearestCarStrategy {
        +assign(Request, List~ElevatorCar~) ElevatorCar
    }

    Building "1" *-- "many" ElevatorCar : contains
    Building --> Dispatcher : uses
    Dispatcher o-- DispatchStrategy : uses (injected)
    ElevatorCar o-- ElevatorState : state (State Pattern)
    ElevatorState <|.. IdleState : implements
    ElevatorState <|.. MovingUpState : implements
    ElevatorState <|.. MovingDownState : implements
    DispatchStrategy <|.. NearestCarStrategy : implements
    Dispatcher --> ElevatorCar : assigns
```

**Observable outcome:** - Request: Either ExternalRequest (floor + direction pressed outside) or InternalRequest (destination floor pressed inside the car).

## Stage 3 — Deep Dive: State Pattern for Elevator Movement

- An elevator's behavior depends on its current state.
- We make this explicit with the State pattern: The state transitions:

*Applies **design-patterns-gof** to the decision above.*

```java
public interface ElevatorState {
    void handleRequest(ElevatorCar car, int targetFloor);
    String name();
}

public class IdleState implements ElevatorState {
    public void handleRequest(ElevatorCar car, int targetFloor) {
        car.addStop(targetFloor);
        if (targetFloor > car.getCurrentFloor()) {
            car.setState(new MovingUpState());
        } else if (targetFloor < car.getCurrentFloor()) {
            car.setState(new MovingDownState());
        }
    }
    public String name() { return "IDLE"; }
}

public class MovingUpState implements ElevatorState {
    public void handleRequest(ElevatorCar car, int targetFloor) {
        // SCAN: only add if it's above current floor
        if (targetFloor >= car.getCurrentFloor()) {
            car.addStop(targetFloor);   // serve on the way
        } else {
            car.deferRequest(targetFloor);  // serve on the next sweep
        }
    }
    public String name() { return "MOVING_UP"; }
}
```

```mermaid
stateDiagram-v2
    [*] --> IDLE
    IDLE --> MOVING_UP : request above current floor
    IDLE --> MOVING_DOWN : request below current floor
    MOVING_UP --> IDLE : no more up requests
    MOVING_UP --> MOVING_DOWN : switch at top
    MOVING_DOWN --> IDLE : no more down requests
    MOVING_DOWN --> MOVING_UP : switch at bottom
```

**Observable outcome:** We make this explicit with the State pattern: The state transitions:

## Stage 4 — Dispatcher: Strategy Pattern for Assignment Policy

- The Dispatcher uses the Strategy pattern so we can swap assignment algorithms: canService() checks the car's state: - IDLE → always serviceable.
- - MOVING UP → serviceable if request is above current floor and direction matches.
- - MOVING DOWN → serviceable if request is below current floor and direction matches.

*Applies **design-principles-solid** to the decision above.*

```java
public interface DispatchStrategy {
    ElevatorCar select(List<ElevatorCar> cars, Request request);
}

// Nearest-Car strategy: pick the car that will reach the requester soonest
public class NearestCarStrategy implements DispatchStrategy {
    public ElevatorCar select(List<ElevatorCar> cars, Request request) {
        return cars.stream()
            .filter(c -> c.canService(request))
            .min(Comparator.comparingInt(c ->
                Math.abs(c.getCurrentFloor() - request.getSourceFloor())))
            .orElse(null);
    }
}
```

**Observable outcome:** - MOVING DOWN → serviceable if request is below current floor and direction matches.

## Stage 5 — Interface Contracts: DispatchStrategy and ElevatorState

- Two interfaces form the entire behavioral backbone of this design.
- Every concrete class — state implementations, dispatch algorithms, the Dispatcher itself — is wired together through these two contracts.
- Why separate handleExternalRequest from handleInternalRequest ?
- External requests originate from a floor panel and route through the Dispatcher — the strategy can load-balance across cars.

*Applies **low-level-design-systems** to the decision above.*

```java
// Who implements: NearestCarStrategy, ZoneStrategy, LookStrategy
// Who consumes:   Dispatcher
interface DispatchStrategy {
    ElevatorCar assign(Request request, List<ElevatorCar> available);
}

// Who implements: IdleState, MovingUpState, MovingDownState
// Who consumes:   ElevatorCar.handleExternalRequest(), ElevatorCar.handleInternalRequest()
interface ElevatorState {
    void handleExternalRequest(ElevatorCar car, Request request);
    void handleInternalRequest(ElevatorCar car, int targetFloor);
    boolean isIdle();
}
```

```mermaid
sequenceDiagram
    participant U as User (Floor 3)
    participant D as Dispatcher
    participant S as DispatchStrategy
    participant C as ElevatorCar
    participant ST as ElevatorState
    U->>D: handleExternalRequest(floor=3, UP)
    D->>S: assign(request, availableCars)
    S->>S: score each car by distance
    S-->>D: bestCar (Car #2)
    D->>C: handleExternalRequest(car, request)
    C->>ST: delegate to current state
    ST->>C: addStop(floor=3)
    ST->>C: setState(MovingUpState)
    C-->>D: stop added
    Note over C: Car moves toward Floor 3 via SCAN
```

**Observable outcome:** External requests originate from a floor panel and route through the Dispatcher — the strategy can load-balance across cars.

## Stage 6 — OOP Pillars in the Elevator Design

- Each of the four OOP pillars maps cleanly to a specific boundary in this design.
- The table below names the pillar, the class or interface that embodies it, and the concrete mechanism.
- Encapsulation deep-dive: The TreeSet<Integer inside ElevatorCar is the most critical encapsulation boundary in the design.
- If external code could add floors to the set arbitrarily, it could insert a below-current-floor stop while the car is sweeping up — silently breaking the SCAN invariant.

*Applies **jvm-internals-and-garbage-collection** to the decision above.*

```mermaid
classDiagram
    class Building {
        +List~Floor~ floors
        +List~ElevatorCar~ cars
        +Dispatcher dispatcher
        +handleExternalRequest(Request) void
    }
    class ElevatorCar {
        +int id
        +int currentFloor
        -ElevatorState state
        -TreeSet~Integer~ stopQueue
        +addStop(int) void
        +deferRequest(int) void
        +move() void
        +setState(ElevatorState) void
        +getCurrentFloor() int
    }
    class Dispatcher {
        -DispatchStrategy strategy
        +assign(Request, List~ElevatorCar~) ElevatorCar
    }
    class ElevatorState {
        <<interface>>
        +handleExternalRequest(ElevatorCar, Request) void
        +handleInternalRequest(ElevatorCar, int) void
        +isIdle() boolean
    }
    class DispatchStrategy {
        <<interface>>
        +assign(Request, List~ElevatorCar~) ElevatorCar
    }
    class IdleState {
        +handleExternalRequest(ElevatorCar, Request) void
        +handleInternalRequest(ElevatorCar, int) void
        +isIdle() boolean
    }
    class MovingUpState {
        +handleExternalRequest(ElevatorCar, Request) void
        +handleInternalRequest(ElevatorCar, int) void
        +isIdle() boolean
    }
    class MovingDownState {
        +handleExternalRequest(ElevatorCar, Request) void
        +handleInternalRequest(ElevatorCar, int) void
        +isIdle() boolean
    }
    class NearestCarStrategy {
        +assign(Request, List~ElevatorCar~) ElevatorCar
    }
    class DestinationDispatchStrategy {
        +assign(Request, List~ElevatorCar~) ElevatorCar
    }
    class Request {
        +int sourceFloor
        +Direction direction
    }
    class Direction {
        <<enumeration>>
        UP
        DOWN
    }
    Building "1" *-- "many" ElevatorCar : contains
    Building --> Dispatcher : uses
    Dispatcher o-- DispatchStrategy : uses (injected)
    ElevatorCar o-- ElevatorState : current state
    ElevatorState <|.. IdleState : implements
    ElevatorState <|.. MovingUpState : implements
    ElevatorState <|.. MovingDownState : implements
    DispatchStrategy <|.. NearestCarStrategy : implements
    DispatchStrategy <|.. DestinationDispatchStrategy : implements
    Dispatcher --> ElevatorCar : assigns
    Request --> Direction : uses
```

**Observable outcome:** If external code could add floors to the set arbitrarily, it could insert a below-current-floor stop while the car is sweeping up — silently breaking the SCAN invariant.

## End-to-end outcome

A hotel has 10 floors and 3 elevators.

## Alternatives considered

### Decision Guide: Choosing the Right Elevator Scheduling Strategy

Start with the SCAN algorithm and Nearest-Car dispatch.


## Failure and degraded modes

### Trade-offs & Failure Modes in Elevator Design

- **Detection:** Trade-offs & Failure Modes in Elevator Design
- **User or operator impact:** Trade-offs & Failure Modes in Elevator Design



## Scenario context

You pull up to a mall garage. Three things happen:
1. **Entry gate:** You press a button → get a ticket → gate opens.
2. **Parking:** Find a spot (the system might display "Floor 2, Spot 14").
3. **Exit:** Scan your ticket → system calculates fee based on time parked → gate opens.

The software behind this manages hundreds of concurrent vehicles across multiple floors, spot types, and pricing tiers.

---

This walkthrough focuses on **The Mall Garage Problem**.

Before making a design choice, clarify:

- Entry gate: You press a button → get a ticket → gate opens.
- Parking: Find a spot (the system might display "Floor 2, Spot 14").
- Exit: Scan your ticket → system calculates fee based on time parked → gate opens.

**Concepts in play:** tree-data-structures, low-level-design-systems, vector-databases-rag, design-patterns-gof

## Stage 1 — Parking Lot Design Basics

- Before writing any code, it helps to map out the real-world entities the system must represent.
- Spot Types — Not every bay fits every vehicle.
- A typical garage divides its spaces into three tiers: Vehicle Types — Each vehicle carries a licensePlate and a VehicleType enum ( BIKE , CAR , TRUCK ).
- The type determines which spot tier it can occupy — a TRUCK cannot squeeze into a CompactSpot .

*Applies **tree-data-structures** to the decision above.*

**Observable outcome:** The type determines which spot tier it can occupy — a TRUCK cannot squeeze into a CompactSpot .

## Stage 2 — The Domain Model

- Hierarchy: - ParkingSpot → subclasses: BikeSpot , CompactSpot , LargeSpot - Vehicle → subclasses: Bike , Car , Truck - ParkingLot → Singleton (one physical lot, one controller)

*Applies **low-level-design-systems** to the decision above.*

```mermaid
classDiagram
    class ParkingLot {
        -static ParkingLot instance
        +List~ParkingFloor~ floors
        -PricingStrategy pricingStrategy
        +Ticket park(Vehicle v)
        +double exit(Ticket t)
    }
    class ParkingFloor {
        +int floorNumber
        -Map~VehicleType,PriorityQueue~ heaps
        +ParkingSpot findNearest(VehicleType t)
        +void releaseSpot(ParkingSpot s)
    }
    class ParkingSpot {
        <<abstract>>
        +int id
        +boolean isFree
        +VehicleType type
        +void assign(Vehicle v)
        +void free()
    }
    class BikeSpot {
        +VehicleType type = BIKE
    }
    class CompactSpot {
        +VehicleType type = CAR
    }
    class LargeSpot {
        +VehicleType type = TRUCK
    }
    class Vehicle {
        <<abstract>>
        +String licensePlate
        +VehicleType type
    }
    class Bike
    class Car
    class Truck
    class Ticket {
        +Vehicle vehicle
        +ParkingSpot spot
        +Instant entryTime
    }
    class PricingStrategy {
        <<interface>>
        +calculateFee(VehicleType type, long minutes) double
    }
    class HourlyPricing {
        +calculateFee(VehicleType type, long minutes) double
    }

    ParkingLot "1" *-- "many" ParkingFloor : owns
    ParkingFloor "1" *-- "many" ParkingSpot : contains
    BikeSpot --|> ParkingSpot : extends
    CompactSpot --|> ParkingSpot : extends
    LargeSpot --|> ParkingSpot : extends
    Bike --|> Vehicle : extends
    Car --|> Vehicle : extends
    Truck --|> Vehicle : extends
    Ticket --> Vehicle : records
    Ticket --> ParkingSpot : records
    ParkingLot o-- PricingStrategy : uses
    HourlyPricing ..|> PricingStrategy : implements
```

**Observable outcome:** Hierarchy: - ParkingSpot → subclasses: BikeSpot , CompactSpot , LargeSpot - Vehicle → subclasses: Bike , Car , Truck - ParkingLot → Singleton (one physical lot, one controller)

## Stage 3 — OOP Pillars in the Parking Lot Domain

- The four OOP pillars are not abstract ideals here — each one maps to a concrete class or interface in this design.
- Encapsulation — ParkingFloor hides its Min-Heap ParkingFloor owns a Map<VehicleType, PriorityQueue<ParkingSpot internally.
- No external class ever touches that map directly.
- The public surface is exactly two methods: findNearest(VehicleType) (wraps poll() ) and releaseSpot(ParkingSpot) (wraps offer() ).

*Applies **vector-databases-rag** to the decision above.*

```mermaid
stateDiagram-v2
    [*] --> AVAILABLE : spot added to Min-Heap
    AVAILABLE --> OCCUPIED : findNearest()  assign(vehicle)
    OCCUPIED --> AVAILABLE : releaseSpot()  re-insert into heap
    AVAILABLE --> [*] : floor decommissioned
```

**Observable outcome:** The public surface is exactly two methods: findNearest(VehicleType) (wraps poll() ) and releaseSpot(ParkingSpot) (wraps offer() ).

## Stage 4 — Finding the Nearest Spot: Min-Heap

- A naive O(N) linear scan through all spots is too slow for a large garage.
- Optimized: Use a Min-Heap (priority queue ordered by spot ID, lowest = nearest entrance) per vehicle type per floor.
- Operations: - findNearest(CAR) → heaps.get(CAR).poll() → O(log N) - releaseSpot(spot) → heaps.get(spot.type).offer(spot) → O(log N) For N = 1000 spots per floor: log₂(1000) ≈ 10 operations vs.

*Applies **design-patterns-gof** to the decision above.*

```
Floor 1 Compact Heap: [101, 103, 107, ...]   ← pop 101 in O(log N)
Floor 1 Large Heap:   [150, 155, ...]
```

**Observable outcome:** Operations: - findNearest(CAR) → heaps.get(CAR).poll() → O(log N) - releaseSpot(spot) → heaps.get(spot.type).offer(spot) → O(log N) For N = 1000 spots per floor: log₂(1000) ≈ 10 operations vs.

## Stage 5 — Deep Dive: Factory and Strategy Patterns

- Callers use VehicleFactory.create(VehicleType.CAR, "ABC-123") — never new Car(...) directly.
- This decouples object creation from business logic and makes it easy to add ElectricVehicle later.

*Applies **tree-data-structures** to the decision above.*

```java
public class VehicleFactory {
    public static Vehicle create(VehicleType type, String plate) {
        return switch (type) {
            case BIKE   -> new Bike(plate);
            case CAR    -> new Car(plate);
            case TRUCK  -> new Truck(plate);
        };
    }
}
```

**Observable outcome:** This decouples object creation from business logic and makes it easy to add ElectricVehicle later.

## Stage 6 — Strategy Pattern for Pricing

- Pricing rules vary (hourly, daily, weekend, EV charging surcharge): The ParkingLot holds a reference to any PricingStrategy .
- Swapping from HourlyPricing to DynamicPricing requires zero changes to the rest of the code.
- 📊 Factory and Strategy: Class Diagram This class diagram extends the core domain model to show the full Factory and Strategy pattern integration, including the VehicleFactory creation point, the pluggable PricingStrate…
- The key relationship is that ParkingLot depends on interfaces ( PricingStrategy , SpotAllocator ) rather than concrete classes, which is what allows EVSpot and ChargingPricing to be added without modifying any existing…

*Applies **low-level-design-systems** to the decision above.*

```java
public interface PricingStrategy {
    double calculateFee(VehicleType type, long parkingMinutes);
}

public class HourlyPricing implements PricingStrategy {
    public double calculateFee(VehicleType type, long minutes) {
        double ratePerHour = type == VehicleType.TRUCK ? 3.50 :
                             type == VehicleType.CAR   ? 2.00 : 1.00;
        return ratePerHour * Math.ceil(minutes / 60.0);
    }
}
```

```mermaid
classDiagram
    class VehicleFactory {
        +create(VehicleType, String) Vehicle
    }
    class PricingStrategy {
        <<interface>>
        +calculateFee(VehicleType, long) double
    }
    class HourlyPricing {
        +calculateFee(VehicleType, long) double
    }
    class ChargingPricing {
        +calculateFee(VehicleType, long) double
    }
    class SpotAllocator {
        <<interface>>
        +findNearest(VehicleType, List~ParkingFloor~) Optional~ParkingSpot~
        +release(ParkingSpot, List~ParkingFloor~) void
    }
    class NearestFirstAllocator {
        +findNearest(VehicleType, List~ParkingFloor~) Optional~ParkingSpot~
        +release(ParkingSpot, List~ParkingFloor~) void
    }
    class EVSpot {
        +chargerType String
        +canFit(VehicleType) boolean
    }
    class ParkingLot {
        -PricingStrategy pricingStrategy
        -SpotAllocator allocator
        +park(Vehicle) Ticket
        +exit(Ticket) double
    }
    HourlyPricing ..|> PricingStrategy : implements
    ChargingPricing ..|> PricingStrategy : implements
    NearestFirstAllocator ..|> SpotAllocator : implements
    ParkingLot o-- PricingStrategy : uses (injected)
    ParkingLot o-- SpotAllocator : uses (injected)
    VehicleFactory --> Vehicle : creates
    EVSpot --|> ParkingSpot : extends
```

**Observable outcome:** The key relationship is that ParkingLot depends on interfaces ( PricingStrategy , SpotAllocator ) rather than concrete classes, which is what allows EVSpot and ChargingPricing to be added without modifying any existing…

## End-to-end outcome

Entry gate: You press a button → get a ticket → gate opens.

## Alternatives considered

### Decision Guide: When to Apply These Parking Lot Patterns

Start simple: a flat HashMap<SpotId, Spot works for a garage under 50 spots.


## Failure and degraded modes

### Trade-offs & Failure Modes in Parking Lot Design

- **Detection:** Trade-offs & Failure Modes in Parking Lot Design
- **User or operator impact:** Trade-offs & Failure Modes in Parking Lot Design



## Scenario context

You run a cinema. A Friday night show has 200 seats. Two scenarios break a naive implementation:

1. **Double-booking:** User A and User B click "Book Seat A1" at the same millisecond. Only one should succeed.
2. **Abandoned locks:** User A locks Seat A1 but never completes payment. The seat should become available again after 10 minutes.

This needs a **3-state model + distributed lock** strategy.

---

This walkthrough focuses on **The Cinema Inventory Problem: What Makes It Hard**.

Before making a design choice, clarify:

- A Friday night show has 200 seats.
- Two scenarios break a naive implementation: 1.
- Double-booking: User A and User B click "Book Seat A1" at the same millisecond.

**Concepts in play:** low-level-design-systems, caching, api-gateway, distributed-locking

## Stage 1 — Key Entities in a Movie Booking System

- Before writing a single line of concurrency code, you need a clear domain model.
- A movie booking platform has six core entities: SeatType classifies seats by price tier: - PLATINUM — premium recliner seats (front/center) - GOLD — standard premium tier - SILVER — economy tier SeatStatus is the concur…
- Every Booking references a Show, not the Movie directly — this is why "the 7 PM showing of a film" is completely separate inventory from "the 9 PM showing" of the same film.
- This hierarchy shapes every query, index, and cache partition in the real system.

*Applies **low-level-design-systems** to the decision above.*

**Observable outcome:** This hierarchy shapes every query, index, and cache partition in the real system.

## Stage 2 — The Domain Hierarchy: City → Cinema → Screen → Show → Seat

- The composition arrows ( -- ) running down the left spine — City → Cinema → Screen → Seat — model physical containment: a Screen cannot exist without its owning Cinema , and Seat instances are part of the Screen .
- Show sits at the centre as the critical join entity, linking a Movie and a Screen at a specific startTime ; every Booking references a Show , not a Movie directly, which is why two screenings of the same film are comple…
- The aggregation arrows ( o-- ) from BookingService to PricingStrategy and PaymentGateway express collaboration, not ownership — both dependencies are injected interfaces, making the service fully decoupled from any conc…
- - SeatType: GOLD , SILVER , PLATINUM — affects pricing.

*Applies **caching** to the decision above.*

```mermaid
classDiagram
    class City {+String name; +List~Cinema~ cinemas}
    class Cinema {+String name; +List~Screen~ screens}
    class Screen {+int id; +List~Seat~ seats}
    class Movie {+String title; +int durationMinutes}
    class Show {
        +Movie movie
        +Screen screen
        +LocalDateTime startTime
        +synchronized boolean bookSeats(List seats)
    }
    class Seat {
        -SeatStatus status
        +String row
        +int col
        +SeatType type
        +reserve(bookingId)
        +release()
        +confirm()
    }
    class PremiumSeat {
        +boolean hasRecline
        +boolean hasFootrest
    }
    class GroupSeat {
        +String groupReservationId
    }
    class Booking {
        +int id
        +Show show
        +List~Seat~ seats
        +PaymentStatus payment
    }
    class BookingService {
        +reserveSeats(User, Show, List~Seat~)
        +confirmBooking(Booking)
    }
    class PricingStrategy {
        <<interface>>
        +calculatePrice(Seat, Show, Customer) Money
    }
    class PaymentGateway {
        <<interface>>
        +charge(Customer, Money, String) PaymentResult
    }

    City *-- Cinema
    Cinema *-- Screen
    Screen *-- Seat
    Show "1" *-- "many" Seat : contains
    Show --> Screen
    Booking --> Show
    Booking --> Seat
    PremiumSeat --|> Seat : extends
    GroupSeat --|> Seat : extends
    BookingService o-- PricingStrategy : uses (injected)
    BookingService o-- PaymentGateway : uses (injected)
```

**Observable outcome:** - SeatType: GOLD , SILVER , PLATINUM — affects pricing.

## Stage 3 — The 3-State Seat Model: Preventing Double Booking

- The key insight: don't go directly from AVAILABLE to BOOKED.
- Insert a temporary LOCKED state.
- State machine: The booking flow: User B gets a graceful "This seat is currently being held by another user" message — not a race condition with undefined behavior.

*Applies **api-gateway** to the decision above.*

```mermaid
stateDiagram-v2
    [*] --> AVAILABLE
    AVAILABLE --> LOCKED : User selects seat (10 min TTL)
    LOCKED --> BOOKED : Payment success
    LOCKED --> AVAILABLE : Payment timeout / failure
    BOOKED --> [*] : Show complete
```

**Observable outcome:** State machine: The booking flow: User B gets a graceful "This seat is currently being held by another user" message — not a race condition with undefined behavior.

## Stage 4 — Booking Flow: From Seat Selection to Confirmation

- Here is how a booking request moves through the system end-to-end — including both failure paths that keep inventory clean: The flowchart maps the complete booking transaction as a directed decision graph with two disti…
- The first diamond — "All seats AVAILABLE?" — is the cheap early-exit: if any seat is already LOCKED or BOOKED by a concurrent user, the request is rejected before a lock is ever acquired on the current user's behalf, re…
- Only after seats are successfully locked does control reach the payment gateway, whose failure branch explicitly releases the hold and returns inventory to AVAILABLE — this explicit release is what separates a well-desi…
- Two distinct failure paths keep inventory accurate: 1.

*Applies **distributed-locking** to the decision above.*

```mermaid
flowchart TD
    A([User Selects Seats]) --> B{All seats AVAILABLE?}
    B -- No --> C([Error: Seat Already Held by Another User])
    B -- Yes --> D[Lock Seats  10 min TTL applied]
    D --> E([User Redirected to Payment Page])
    E --> F{Payment Successful?}
    F -- Timeout or Failure --> G[Release Lock  Seats set back to AVAILABLE]
    F -- Yes --> H[Set Seats to BOOKED]
    H --> I([Confirmation Email Sent to User])
    G --> J([Error: Payment Failed  Seats Released])
```

**Observable outcome:** Two distinct failure paths keep inventory accurate: 1.

## Stage 5 — Deep Dive: Synchronized Booking Implementation

- synchronized on the Show method ensures that the check-and-lock is atomic — no two threads can interleave between the check ( AVAILABLE ) and the lock ( LOCKED ).
- 📊 Reserve Seats: Booking Sequence The sequence diagram traces the critical path for seat reservation — from the initial lock request (preventing other threads from booking the same seat) through payment confirmation to…
- The synchronized annotation on the BS- SH call marks the boundary of the atomic monitor: every arrow that follows — the status check ( SH- S: status == AVAILABLE?
- ) and the lock ( SH- S: reserve(bookingId) ) — executes inside a single thread-held critical section, making interleaving between the check and the commit impossible.

*Applies **low-level-design-systems** to the decision above.*

```java
public class Show {
    private final int id;
    private final List<Seat> seats;

    public synchronized BookingResult reserveSeats(User user, List<Integer> seatIds) {
        // Phase 1: Check all requested seats are available
        List<Seat> selected = new ArrayList<>();
        for (int id : seatIds) {
            Seat s = findSeat(id);
            if (s.getStatus() != SeatStatus.AVAILABLE) {
                return BookingResult.failure("Seat " + id + " is not available");
            }
            selected.add(s);
        }
        // Phase 2: Lock all seats together (atomic within synchronized block)
        Instant lockExpiry = Instant.now().plusSeconds(600);
        for (Seat s : selected) {
            s.setStatus(SeatStatus.LOCKED);
            s.setLockExpiry(lockExpiry);
        }
        return BookingResult.success(new Booking(user, this, selected));
    }
}
```

```mermaid
sequenceDiagram
    participant U as User
    participant BS as BookingService
    participant SH as Show
    participant S as Seat
    participant PG as PaymentGateway
    U->>BS: reserveSeats(user, show, seatIds)
    BS->>SH: reserveSeats(user, seatIds) synchronized
    SH->>S: status == AVAILABLE?
    S-->>SH: true
    SH->>S: reserve(bookingId)  LOCKED
    SH-->>BS: BookingResult.success(booking)
    BS->>PG: charge(user, amount, bookingId)
    PG-->>BS: PaymentResult.success
    BS->>S: confirm()  BOOKED
    BS-->>U: Booking{id, seats, CONFIRMED}
```

**Observable outcome:** ) and the lock ( SH- S: reserve(bookingId) ) — executes inside a single thread-held critical section, making interleaving between the check and the commit impossible.

## Stage 6 — Pricing Strategy Pattern

- Different shows and seat types need different prices: 📊 Enhanced Booking Domain Class Diagram This enhanced diagram isolates the Seat subsystem with its full type hierarchy and wires in the three Strategy/Gateway inter…
- The enumeration classes SeatType and SeatStatus appear as owned associations of Seat (solid arrows from Seat ), making explicit that price tier and booking state are intrinsic to the seat itself — not to the Booking or…
- The dashed implementation arrows ( ..
- ) from HourlyPricing and DynamicPricing to PricingStrategy are the Strategy pattern in UML form: both are interchangeable at the BookingService injection site, so the active pricing rule switches at Spring configuration…

*Applies **caching** to the decision above.*

```java
public interface PricingStrategy {
    Money calculatePrice(Seat seat, Show show, Customer customer);
}

public class HourlyPricing implements PricingStrategy {
    public Money calculatePrice(Seat seat, Show show, Customer customer) {
        double base = seat.getType() == SeatType.GOLD ? 15.0 : 10.0;
        double multiplier = show.isWeekend() ? 1.2 : 1.0;  // weekend surcharge
        return Money.of(base * multiplier);
    }
}

public class DynamicPricing implements PricingStrategy {
    public Money calculatePrice(Seat seat, Show show, Customer customer) {
        double occupancy = show.getBookedPercent();
        return Money.of(BASE_PRICE * (1 + occupancy));  // price rises with demand
    }
}
```

```mermaid
classDiagram
    class Seat {
        -SeatStatus status
        +String row
        +int col
        +SeatType type
        +reserve(String bookingId) void
        +release() void
        +confirm() void
    }
    class PremiumSeat {
        +boolean hasRecline
        +boolean hasFootrest
    }
    class GroupSeat {
        +String groupReservationId
    }
    class SeatType {
        <<enumeration>>
        PLATINUM
        GOLD
        SILVER
    }
    class SeatStatus {
        <<enumeration>>
        AVAILABLE
        LOCKED
        BOOKED
    }
    class PricingStrategy {
        <<interface>>
        +calculatePrice(Seat, Show, Customer) Money
    }
    class HourlyPricing {
        +calculatePrice(Seat, Show, Customer) Money
    }
    class DynamicPricing {
        +calculatePrice(Seat, Show, Customer) Money
    }
    class SeatSelector {
        <<interface>>
        +findAvailable(Show, SeatType, int) List~Seat~
    }
    class PaymentGateway {
        <<interface>>
        +charge(Customer, Money, String) PaymentResult
    }
    class BookingService {
        -PricingStrategy pricer
        -SeatSelector selector
        -PaymentGateway gateway
        +reserveSeats(User, Show, List~Seat~) Booking
        +confirmBooking(Booking) void
    }
    PremiumSeat --|> Seat : extends
    GroupSeat --|> Seat : extends
    Seat --> SeatStatus : state
    Seat --> SeatType : type
    HourlyPricing ..|> PricingStrategy : implements
    DynamicPricing ..|> PricingStrategy : implements
    BookingService o-- PricingStrategy : uses (injected)
    BookingService o-- SeatSelector : uses (injected)
    BookingService o-- PaymentGateway : uses (injected)
```

**Observable outcome:** ) from HourlyPricing and DynamicPricing to PricingStrategy are the Strategy pattern in UML form: both are interchangeable at the BookingService injection site, so the active pricing rule switches at Spring configuration…

## End-to-end outcome

A Friday night show has 200 seats.

## Alternatives considered

### OOP Decision Guide: Patterns and Extension Points

Start with synchronized on Seat methods and constructor-injected strategies.


## Failure and degraded modes

### OOP Design Trade-offs and Failure Modes in the Booking System

- **Detection:** Failure mode — skipping the LOCKED state: If code transitions directly from AVAILABLE to BOOKED in a single step, any failure mid-payment (timeout, gateway error, network drop) leaves the seat perman…
- **User or operator impact:** Failure mode — skipping the LOCKED state: If code transitions directly from AVAILABLE to BOOKED in a single step, any failure mid-payment (timeout, gateway error, network drop) leaves the seat perman…



## Scenario context

A ride-booking system (Uber/Lyft-style) needs three interleaved sub-systems: real-time driver location tracking (Observer Pattern), nearest-driver matching (geospatial query), and dynamic pricing (Strategy Pattern). Getting state transitions right — Requested → Accepted → InProgress → Completed — is the core LLD challenge.


```architecture
{
  "version": 1,
  "title": "Ride Sharing Platform - Spatial Indexing & Geo…

This walkthrough focuses on **The Matchmaking Problem Behind Every Ride Request**.

Before making a design choice, clarify:

- When a rider taps "Book Ride," a deceptively complex chain of decisions fires within seconds: 1.
- Which drivers are available near the pickup point?
- How does the trip state transition as the ride progresses?

**Concepts in play:** design-patterns-gof, low-level-design-systems, caching, jvm-internals-and-garbage-collection

## Stage 1 — Core Entities and Their Relationships

- Rider → requests a trip, has a current location.
- Driver → has availability status, current location, vehicle info.
- Trip → ties a rider to a driver, from pickup to drop-off.
- TripStatus enum: DriverStatus enum: 📊 Driver Availability State Machine

*Applies **design-patterns-gof** to the decision above.*

```mermaid
classDiagram
    class Rider {
        +String id
        +String name
        +Location location
        +requestRide(Location destination)
    }
    class Driver {
        +String id
        +String name
        +DriverStatus status
        +Location location
        +updateLocation(Location loc)
    }
    class Trip {
        +String tripId
        +Rider rider
        +Driver driver
        +TripStatus status
        +Location pickup
        +Location destination
        +transition(TripEvent event)
    }
    Rider --> Trip : initiates
    Driver --> Trip : fulfills
```

```java
enum TripStatus {
    REQUESTED, ACCEPTED, IN_PROGRESS, COMPLETED, CANCELLED
}
```

**Observable outcome:** TripStatus enum: DriverStatus enum: 📊 Driver Availability State Machine

## Stage 2 — State Transitions: The Trip Lifecycle

- Every transition is triggered by an explicit event.
- Wrong transitions must be rejected.

*Applies **low-level-design-systems** to the decision above.*

```mermaid
stateDiagram-v2
    [*] --> REQUESTED : rider taps Book
    REQUESTED --> ACCEPTED : driver accepts
    REQUESTED --> CANCELLED : no driver found / rider cancels
    ACCEPTED --> IN_PROGRESS : driver arrives at pickup
    IN_PROGRESS --> COMPLETED : destination reached
    IN_PROGRESS --> CANCELLED : rider or driver cancels mid-trip
    COMPLETED --> [*]
    CANCELLED --> [*]
```

```java
// Transition enforcement
public void transition(TripStatus newStatus) {
    if (!isValidTransition(this.status, newStatus)) {
        throw new IllegalStateException(
            "Cannot transition from " + this.status + " to " + newStatus);
    }
    this.status = newStatus;
}

private boolean isValidTransition(TripStatus from, TripStatus to) {
    return switch (from) {
        case REQUESTED   -> to == ACCEPTED   || to == CANCELLED;
        case ACCEPTED    -> to == IN_PROGRESS || to == CANCELLED;
        case IN_PROGRESS -> to == COMPLETED  || to == CANCELLED;
        default          -> false;
    };
}
```

**Observable outcome:** Wrong transitions must be rejected.

## Stage 3 — Real-World Applications: Observer Pattern: Real-Time Driver Location Updates

- Riders, dispatchers, and ETAs all need to react when a driver's location changes.
- The Observer Pattern decouples location updates from their consumers.

*Applies **caching** to the decision above.*

```java
// Observer interface
interface LocationObserver {
    void onLocationUpdate(String driverId, Location newLocation);
}

// Subject (driver location tracker)
class DriverLocationService {
    private Map<String, List<LocationObserver>> subscribers = new HashMap<>();

    public void subscribe(String driverId, LocationObserver observer) {
        subscribers.computeIfAbsent(driverId, k -> new ArrayList<>()).add(observer);
    }

    public void updateLocation(String driverId, Location loc) {
        subscribers.getOrDefault(driverId, List.of())
                   .forEach(obs -> obs.onLocationUpdate(driverId, loc));
    }
}

// Concrete observer
class RiderEtaTracker implements LocationObserver {
    @Override
    public void onLocationUpdate(String driverId, Location loc) {
        // Recalculate ETA and push to rider's app
        System.out.println("ETA updated for driver " + driverId + " at " + loc);
    }
}
```

**Observable outcome:** The Observer Pattern decouples location updates from their consumers.

## Stage 4 — Matching Algorithm: Finding the Nearest Available Driver

- The simplest valid matching algorithm: 1.
- Filter drivers by status = AVAILABLE.
- For each candidate, compute distance to rider pickup.
- Return the driver with minimum distance.

*Applies **jvm-internals-and-garbage-collection** to the decision above.*

```mermaid
graph TD
    A[Ride Request received  pickup location known] --> B[Query driver index: status = AVAILABLE]
    B --> C[For each candidate: compute Haversine distance to pickup]
    C --> D{Any drivers within radius?}
    D -->|No| E[Expand radius or notify rider of no availability]
    D -->|Yes| F[Sort candidates by distance ascending]
    F --> G[Assign nearest driver  send acceptance request]
    G --> H{Driver accepts?}
    H -->|Yes| I[Trip transitions to ACCEPTED]
    H -->|No| F
```

```java
class MatchingService {
    public Optional<Driver> findNearest(Location pickup, List<Driver> drivers) {
        return drivers.stream()
            .filter(d -> d.getStatus() == DriverStatus.AVAILABLE)
            .min(Comparator.comparingDouble(d -> haversine(pickup, d.getLocation())));
    }

    private double haversine(Location a, Location b) {
        double R = 6371.0;
        double dLat = Math.toRadians(b.lat() - a.lat());
        double dLon = Math.toRadians(b.lon() - a.lon());
        double h = Math.sin(dLat/2)*Math.sin(dLat/2)
                 + Math.cos(Math.toRadians(a.lat()))
                 * Math.cos(Math.toRadians(b.lat()))
                 * Math.sin(dLon/2)*Math.sin(dLon/2);
        return 2 * R * Math.asin(Math.sqrt(h));
    }
}
```

**Observable outcome:** Return the driver with minimum distance.

## Stage 5 — Strategy Pattern: Flexible Pricing Rules

- Pricing logic must change at runtime — flat rate, surge, subscription, etc.
- The Strategy Pattern lets you swap rules without modifying TripPricingEngine .

*Applies **design-patterns-gof** to the decision above.*

```java
interface PricingStrategy {
    double calculateFare(double distanceKm, int durationMinutes, double surgeMultiplier);
}

class StandardPricing implements PricingStrategy {
    public double calculateFare(double distKm, int durMin, double surge) {
        return (0.5 + 1.2 * distKm + 0.25 * durMin) * surge;
    }
}

class FlatRatePricing implements PricingStrategy {
    private double flatRate;
    public FlatRatePricing(double rate) { this.flatRate = rate; }
    public double calculateFare(double d, int t, double s) { return flatRate; }
}

class TripPricingEngine {
    private PricingStrategy strategy;
    public TripPricingEngine(PricingStrategy s) { this.strategy = s; }
    public void setStrategy(PricingStrategy s) { this.strategy = s; }
    public double quote(double km, int min, double surge) {
        return strategy.calculateFare(km, min, surge);
    }
}
```

**Observable outcome:** The Strategy Pattern lets you swap rules without modifying TripPricingEngine .

## Stage 6 — OOP Pillars Applied to the Ride-Booking Domain

- Every core class in this design maps directly to one of the four OOP pillars.
- The mapping is explicit, not accidental — each pillar solves a specific design problem in the ride-booking context.
- Driver.status is private — it is only mutated through named domain operations.
- PremiumDriver and EvDriver inherit the full base contract and extend it.

*Applies **low-level-design-systems** to the decision above.*

```mermaid
classDiagram
    class Driver {
        +String id
        +String name
        -DriverStatus status
        +updateLocation(Location loc)
        +acceptRide(TripRequest req)
        +completeRide(Trip trip)
        +isAvailableFor(TripRequest req) bool
    }
    class PremiumDriver {
        +String vehicleClass
        +bool hasWifi
    }
    class EvDriver {
        +double batteryPercent
        +isAvailableFor(TripRequest req) bool
    }
    class MatchingStrategy {
        <<interface>>
        +match(TripRequest req, List~Driver~ available) Optional~Driver~
    }
    class PricingStrategy {
        <<interface>>
        +calculate(TripRequest req, Driver driver) Fare
    }
    class TripRequestService {
        -MatchingStrategy matcher
        -PricingStrategy pricer
        +requestRide(TripRequest req) Trip
    }
    class Trip {
        +String tripId
        +TripStatus status
        +transition(TripStatus next)
    }
    PremiumDriver --|> Driver : extends
    EvDriver --|> Driver : extends
    TripRequestService o-- MatchingStrategy : uses (injected)
    TripRequestService o-- PricingStrategy : uses (injected)
    Driver --> Trip : fulfills
```

```mermaid
classDiagram
    class TripRequest {
        +Location pickup
        +Location dropoff
        +String riderId
    }
    class Trip {
        +String tripId
        -TripStatus status
        +Driver assignedDriver
        +transition(TripStatus) void
    }
    class Driver {
        +String id
        +String name
        -DriverStatus status
        +Location location
        +acceptRide(TripRequest) void
        +completeRide(Trip) void
        +isAvailableFor(TripRequest) boolean
    }
    class PremiumDriver {
        +String vehicleClass
        +boolean hasWifi
    }
    class EvDriver {
        +double batteryPercent
        +isAvailableFor(TripRequest) boolean
    }
    class TripRequestService {
        -MatchingStrategy matcher
        -PricingStrategy pricer
        +requestRide(TripRequest) Trip
    }
    class MatchingStrategy {
        <<interface>>
        +match(TripRequest, List~Driver~) Optional~Driver~
    }
    class PricingStrategy {
        <<interface>>
        +calculate(TripRequest, Driver) Fare
    }
    class LocationObserver {
        <<interface>>
        +onLocationUpdate(String, Location) void
    }
    class DriverLocationService {
        -Map~String,List~ subscribers
        +subscribe(String, LocationObserver) void
        +updateLocation(String, Location) void
    }
    class RiderEtaTracker {
        +onLocationUpdate(String, Location) void
    }
    class TripStatus {
        <<enumeration>>
        REQUESTED
        ACCEPTED
        IN_PROGRESS
        COMPLETED
        CANCELLED
    }
    class DriverStatus {
        <<enumeration>>
        AVAILABLE
        BUSY
        OFFLINE
    }
    PremiumDriver --|> Driver : extends
    EvDriver --|> Driver : extends
    TripRequestService o-- MatchingStrategy : uses (injected)
    TripRequestService o-- PricingStrategy : uses (injected)
    RiderEtaTracker ..|> LocationObserver : implements
    DriverLocationService --> LocationObserver : notifies
    Trip --> TripStatus : state
    Driver --> DriverStatus : state
    Trip --> Driver : assigned to
    TripRequest --> Trip : becomes
```

**Observable outcome:** PremiumDriver and EvDriver inherit the full base contract and extend it.

## End-to-end outcome

When a rider taps "Book Ride," a deceptively complex chain of decisions fires within seconds: 1.

## Alternatives considered

### Decision Guide: LLD Decision Guide for Ride Booking

Decision Guide: LLD Decision Guide for Ride Booking


## Failure and degraded modes

### Trade-offs & Failure Modes: Trade-offs and Production Constraints

- **Detection:** Trade-offs & Failure Modes: Trade-offs and Production Constraints
- **User or operator impact:** Trade-offs & Failure Modes: Trade-offs and Production Constraints



## Scenario context

Tic-Tac-Toe looks trivial — until the interviewer says "make it N×N with P players and pluggable winning rules." The key design decisions: a Board abstracted from piece identity, a Strategy Pattern for win conditions, and a Factory for player creation. Getting these right is the interview objective.

---

A fixed two-player array breaks the moment a third player is added. A `Deque<Player>` implements round-robin rot…

This walkthrough focuses on **Deep Dive: Why the Deque Is the Right Structure for Turn Management**.

Before making a design choice, clarify:

- A fixed two-player array breaks the moment a third player is added.
- A Deque<Player implements round-robin rotation with two operations: pollFirst() takes the current player and offerLast() returns them after their turn.
- This scales to N players without index arithmetic.

**Concepts in play:** low-level-design-systems, design-principles-solid, stack-and-queue-data-structures, jvm-internals-and-garbage-collection

## Stage 1 — The Basics: Object-Oriented Design for Games

- A common interview mistake is designing Tic-Tac-Toe as a 3×3 hardcoded grid.
- The interviewer immediately asks: "What if I want a 10×10 board?
- Or 4-in-a-row instead of 3?" The design that handles this is what we're building.
- Low-level design interviews test whether you can decompose a system into clean, extensible objects.

*Applies **low-level-design-systems** to the decision above.*

**Observable outcome:** Low-level design interviews test whether you can decompose a system into clean, extensible objects.

## Stage 2 — From 3×3 Toy to OOP Interview Test

- Every LLD interview question hides the same trap: the naive solution is obvious, so the interviewer immediately extends it.
- Naive version: a fixed 3×3 grid, two hardcoded players, if-else win check.
- Extended version: N×N board, P players with distinct symbols, swappable winning strategies (row, column, diagonal, custom), and clean state transitions.
- This post builds the extensible version step by step.

*Applies **design-principles-solid** to the decision above.*

**Observable outcome:** This post builds the extensible version step by step.

## Stage 3 — Core Entities — Board, Piece, Player, Game

- A clean OOP model needs exactly four entities: Enums and value objects first:

*Applies **stack-and-queue-data-structures** to the decision above.*

```mermaid
classDiagram
    class PlayingPiece {
        +PieceType type
    }
    class Player {
        +String name
        +PlayingPiece piece
    }
    class Board {
        +int size
        +PlayingPiece[][] grid
        +placePiece(row, col, piece)
        +isFull()
    }
    class Game {
        +Board board
        +Deque players
        +WinningStrategy strategy
        +startGame()
        +checkWinner(row, col, piece)
    }
    Player --> PlayingPiece
    Game --> Board
    Game --> Player
    Game --> WinningStrategy
```

```java
enum PieceType { X, O, STAR, HASH }  // extensible — add symbols without changing Board

class PlayingPiece {
    final PieceType type;
    PlayingPiece(PieceType t) { this.type = t; }
}

class Player {
    final String name;
    final PlayingPiece piece;
    Player(String name, PlayingPiece piece) {
        this.name  = name;
        this.piece = piece;
    }
}
```

**Observable outcome:** A clean OOP model needs exactly four entities: Enums and value objects first:

## Stage 4 — Extending to N×N: Board with Variable Size

- The Board must not hardcode 3.
- Size is a constructor parameter; the grid is a 2D array of nullable PlayingPiece .
- Multiple player support — use a Deque for round-robin turns, regardless of player count: Each turn: poll() from front, play, then offerLast() to back.

*Applies **jvm-internals-and-garbage-collection** to the decision above.*

```java
class Board {
    final int size;
    private final PlayingPiece[][] grid;

    Board(int size) {
        this.size = size;
        this.grid = new PlayingPiece[size][size];
    }

    public boolean placePiece(int row, int col, PlayingPiece piece) {
        if (row < 0 || row >= size || col < 0 || col >= size) return false;
        if (grid[row][col] != null) return false;   // cell occupied
        grid[row][col] = piece;
        return true;
    }

    public PlayingPiece getPiece(int row, int col) { return grid[row][col]; }

    public boolean isFull() {
        for (PlayingPiece[] row : grid)
            for (PlayingPiece p : row)
                if (p == null) return false;
        return true;
    }
}
```

```java
Deque<Player> players = new LinkedList<>();
players.add(new Player("Alice", new PlayingPiece(PieceType.X)));
players.add(new Player("Bob",   new PlayingPiece(PieceType.O)));
players.add(new Player("Carol", new PlayingPiece(PieceType.STAR)));
```

**Observable outcome:** Multiple player support — use a Deque for round-robin turns, regardless of player count: Each turn: poll() from front, play, then offerLast() to back.

## Stage 5 — OOP Pillars Applied in the Game Design

- Each of the four OOP pillars maps directly onto a specific class or interface in this design — not as a textbook exercise, but as a concrete decision that makes the code extensible.
- Encapsulation in practice: Board 's constructor allocates grid as a private field.
- The only public surface is placePiece(row, col, piece) , getPiece(row, col) , and isFull() .
- If the internal representation changes from a 2D array to a Map<Position, Piece , no external class breaks — callers never touch grid[row][col] directly.

*Applies **low-level-design-systems** to the decision above.*

```mermaid
classDiagram
    direction LR
    class Player {
        <<abstract>>
        +Piece piece
        +makeMove(Board) Move*
    }
    class HumanPlayer {
        +makeMove(Board) Move
    }
    class AiPlayer {
        +makeMove(Board) Move
    }
    class WinStrategy {
        <<interface>>
        +checkWin(Board, Piece) bool
    }
    class RowColWinStrategy
    class DiagonalWinStrategy
    HumanPlayer --|> Player : extends
    AiPlayer --|> Player : extends
    RowColWinStrategy ..|> WinStrategy : implements
    DiagonalWinStrategy ..|> WinStrategy : implements
    Game --> Player : uses
    Game --> WinStrategy : depends on
```

**Observable outcome:** If the internal representation changes from a 2D array to a Map<Position, Piece , no external class breaks — callers never touch grid[row][col] directly.

## Stage 6 — SOLID Principles in the Tic-Tac-Toe Design

- Every SOLID principle surfaces in a specific, traceable design decision here — not as abstract advice: OCP in practice: the product team wants a "diagonal-only" win rule for a new game variant.
- You write DiagonalOnlyWinStrategy implements WinStrategy .
- Existing Game , Board , and RowColWinStrategy are untouched.
- The open/closed boundary is the WinStrategy interface.

*Applies **design-principles-solid** to the decision above.*

```java
// Game depends on the abstraction — never on a concrete class
class Game {
    private final WinStrategy strategy;

    Game(Board board, List<Player> players, WinStrategy strategy) {
        this.strategy = strategy;   // injected — any WinStrategy works here
    }
}

// The call site decides which concrete strategy is used — Game never knows
Game standard = new Game(board, players, new RowColWinStrategy());
Game variant  = new Game(board, players, new DiagonalOnlyWinStrategy());
```

**Observable outcome:** The open/closed boundary is the WinStrategy interface.

## End-to-end outcome

A fixed two-player array breaks the moment a third player is added.

## Alternatives considered

### Decision Guide: When to Apply This OOP Pattern

Decision Guide: When to Apply This OOP Pattern


## Failure and degraded modes

### Trade-offs & Failure Modes: Trade-offs and Design Decisions

- **Detection:** Strategy Pattern for win conditions: Passing WinningStrategy into Game via constructor injection means adding a new win rule is a new class — zero changes to Game .
- **User or operator impact:** Strategy Pattern for win conditions: Passing WinningStrategy into Game via constructor injection means adding a new win rule is a new class — zero changes to Game .



Step 1

Solve low-level design system questions: elevator system, parking lot, movie booking, and ride booking.

Object-Oriented Design Exercises