System Design & DSA Masterclass Advanced +250 XP

LLD Real-World Labs

Designing a Parking Lot System

A standard LLD interview favorite, the **Parking Lot** tests your ability to model class hierarchies, coordinate entity relations, and manage concurrent state variables:

Core Entities & Blueprint

  • ParkingLot: Singleton wrapper containing a collection of Levels.
  • Level: Represents a floor, containing a list of Spots.
  • ParkingSpot: Abstracts physical spaces. Subclasses: `CompactSpot`, `LargeSpot`, `MotorcycleSpot`.
  • Vehicle: Base abstract class. Subclasses: `Car` (needs Compact), `Truck` (needs Large), `Motorcycle`.
  • Ticket: Records entering timestamp, vehicle plate, spot ID, and active fee rates.

Concurrency safety is critical: if two cars enter a single vacant spot simultaneously, the spot selection thread must utilize **synchronized locks** to ensure only one vehicle captures the slot.

Designing an Elevator System

Designing an **Elevator System** requires a clean state machine model and efficient scheduling algorithms:

  • SCAN Algorithm (Elevator Algorithm): The elevator travels in one direction (e.g. up), processing all floor requests in that path until it hits the highest floor request, then reverses direction. Prevents starvation.
  • Class Model:
    • `ElevatorController`: Decides which lift handles which floor request.
    • `ElevatorCar`: Tracks state (`IDLE`, `MOVING_UP`, `MOVING_DOWN`), current floor, and door state.
    • `Request`: Holds target floor and origin direction.

Designing a Concurrent LRU Cache

An **LRU Cache** requires $O(1)$ lookups and $O(1)$ updates/evictions. To achieve this, we combine two data structures:

  • HashMap: Maps keys directly to nodes in the LinkedList, providing $O(1)$ lookup speed.
  • Doubly LinkedList: Stores values in access order. Head is the most recently used; Tail is the least recently used (evicted first).
🔒 Concurrency Safeguard: In multi-threaded environments, use a **ReentrantReadWriteLock**. Allow multiple threads to read simultaneously (`readLock()`), but restrict exclusive access during writes/evictions (`writeLock()`).

Designing a Vending Machine (State Pattern)

A **Vending Machine** is the classic interview question to test the application of the **State Design Pattern**. Swapping states dynamically prevents massive, unmanageable `if/else` hierarchies:

State Blueprint & Lifecycle

  • NoMoneyState: Waiting for money. Actions: `insertCoin()` -> Transitions to `HasMoneyState`.
  • HasMoneyState: Coin accepted. Actions: `selectProduct()` -> If valid, transitions to `DispensingState`; `refundCoin()` -> Transitions back to `NoMoneyState`.
  • DispensingState: Dispenses item. Actions: `dispense()` -> Auto-updates inventory. If items > 0, transitions to `NoMoneyState`. If out of stock, transitions to `SoldOutState`.
  • SoldOutState: Out of stock. Rejects coins.
interface VendingMachineState {
  public void insertCoin();
  public void selectProduct(String code);
  public void dispense();
}

Designing Snake & Ladder (Game Loop Architecture)

Designing **Snake & Ladder** tests your capacity to construct clean, extensible game engines and design loops:

Core Entites & Relationships

  • Board: Holds cells mapped from 1 to 100. Contains a list of Snakes and Ladders.
  • Jump (Base Class): Abstracts transport movements. Subclasses: `Snake` (start > end), `Ladder` (start < end).
  • Player: Holds username and active board position.
  • Dice: Handles random integer generation (1-6). Supports multi-dice configurations.
  • Game: Coordinates the active loop, maintaining a Queue of players.
🔁 The Game Loop:
1. Pop `activePlayer` from Queue.
2. Roll the `Dice` to get value $V$.
3. Calculate new position $P_{new} = P_{old} + V$.
4. If $P_{new}$ matches a `Snake` head or `Ladder` foot, apply `jump.getEndPosition()`.
5. If new position is $100$, declare winner! Else, push `activePlayer` back to tail of Queue and continue.

Designing Splitwise (Debt Simplification)

**Splitwise** tests your domain modeling skills and ability to design complex algorithmic operations:

Blueprints

  • User: ID, name, email.
  • Expense: Abstracts billing. Subclasses: `EqualExpense`, `ExactExpense`, `PercentExpense`.
  • Split: Weak whole-part relationship mapping a User to their specific owed share.
  • BalanceSheetController: Tracks balances between users (UserA owes UserB $X$).
⚡ Debt Simplification Algorithm (Greedy Heap Approach):
To minimize total transaction transfers across a group:
1. Calculate net balances for each user (credit is positive, debit is negative).
2. Separate users into two collections: `creditors` (Max-Heap) and `debtors` (Min-Heap based on absolute owed values).
3. Pop the largest creditor and largest debtor.
4. Calculate transfer amount $T = \min(credit, |debit|)$.
5. Record transaction (Debtor pays Creditor $T$). Update balances, and push back to heaps if they have remaining outstanding balances. Repeat until heaps are empty.

Designing an ATM System

An **ATM System** coordinates secure authentication, inventory counting, and state transitions, and is a perfect match for the **State Pattern** combined with **Chain of Responsibility**:

  • ATM States: `IdleState` -> Card inserted -> `HasCardState` -> PIN entered -> `SelectOptionState` -> Dispensing -> `IdleState`.
  • Cash Dispenser (Chain of Responsibility):
    To dispense cash using the minimum number of notes, the ATM passes the withdrawal request along a chain of cash processors:
    `$2000 Note Processor` -> pass remaining -> `$500 Note Processor` -> pass remaining -> `$100 Note Processor`.