Episode 9 — System Design / 9.6 — LLD Problem Solving
9.6 — Quick Revision
Print-friendly cheat sheet. Review this before interviews for a fast refresher on LLD problem-solving.
LLD Problem-Solving Template (45 Minutes)
┌──────────────────────────────────────────────────────────────────┐
│ │
│ [5 min] 1. CLARIFY REQUIREMENTS │
│ - Functional: What does it DO? │
│ - Non-functional: Concurrency? Scale? │
│ - Scope: What is OUT? │
│ │
│ [5 min] 2. IDENTIFY ENTITIES (nouns from requirements) │
│ - Each noun = candidate class │
│ - Group related nouns into hierarchies │
│ │
│ [5 min] 3. DEFINE RELATIONSHIPS │
│ - Composition (owns), Aggregation (uses) │
│ - Inheritance (is-a), Dependency (calls) │
│ │
│ [5 min] 4. DESIGN APIs (verbs from requirements) │
│ - Assign each action to a class │
│ - Define method signatures │
│ │
│ [5 min] 5. APPLY DESIGN PATTERNS │
│ - Strategy, State, Observer, Singleton, Factory │
│ - Only where they naturally fit │
│ │
│ [20 min] 6. IMPLEMENT + WALK THROUGH │
│ - Write clean, runnable code │
│ - Trace one happy path │
│ - Discuss 3+ edge cases │
│ │
└──────────────────────────────────────────────────────────────────┘
Common Entities Per Problem
| Problem | Key Entities | Core Enum(s) |
|---|---|---|
| Parking Lot | ParkingLot, ParkingFloor, ParkingSpot, Vehicle, Ticket | VehicleType, SpotType, TicketStatus |
| Vending Machine | VendingMachine, Product, Inventory, State classes | Coin, MachineState |
| BookMyShow | Movie, Theatre, Screen, Show, Seat, Booking, User | SeatType, SeatStatus, BookingStatus |
| Splitwise | User, Group, Expense, Split strategies | SplitType (EQUAL/EXACT/PERCENTAGE) |
| Uber/Ola | Rider, Driver, Trip, Location, FareCalculator | TripStatus, DriverStatus, RideType |
| Elevator | Elevator, ElevatorController, Request, Scheduler | Direction, ElevatorStatus, RequestType |
Design Patterns Used Per Problem
| Problem | Patterns | Why |
|---|---|---|
| Parking Lot | Singleton, Strategy | One lot instance; swappable pricing (Hourly, Flat) |
| Vending Machine | State | Each machine state (Idle, CoinInserted, ...) encapsulates allowed actions |
| BookMyShow | — (Service layer) | BookingService orchestrates locking, payment, confirmation |
| Splitwise | Strategy | Split types (Equal, Exact, Percentage) are interchangeable algorithms |
| Uber/Ola | Strategy | Fare calculators (Standard, Surge) are swappable |
| Elevator | Strategy, State | Scheduling algorithms swappable; Elevator has movement states |
Key Algorithms
Parking Lot: Spot Assignment
For each floor (lowest first):
For each spot on floor:
If spot.canFit(vehicleType) and not occupied:
Return spot
Throw "Lot Full"
Splitwise: Simplify Debts
1. Calculate net balance per user
net[user] = sum(paid) - sum(owes)
2. Separate:
creditors = users where net > 0 (sorted desc)
debtors = users where net < 0 (sorted desc by abs)
3. Two-pointer greedy:
While both lists have entries:
settle = min(creditor.amount, debtor.amount)
Record: debtor pays creditor settle
Subtract settle from both
Advance pointer if amount reaches 0
Elevator: LOOK Algorithm
1. Move in current direction
2. Stop at floors in destination set
3. When no more stops in current direction:
- If stops exist in opposite direction: REVERSE
- Else: go IDLE
4. Unlike SCAN: do NOT go to building extremes
Only travel as far as the farthest actual request
BookMyShow: Seat Locking
lockSeats(seatIds, userId):
1. Check ALL seats are AVAILABLE (atomic check)
2. If any not available: return false
3. Set all to LOCKED with userId and timestamp
4. Start timeout timer
On timeout expiry:
Release seats back to AVAILABLE
Cancel pending booking
State Machines at a Glance
Vending Machine
IDLE ──insertCoin──► COIN_INSERTED ──selectProduct──► PRODUCT_SELECTED ──dispense──► DISPENSING ──auto──► IDLE
▲ │ │
└──────cancel──────────┘──────────────cancel──────────────┘
Trip (Uber/Ola)
REQUESTED ──accept──► ACCEPTED ──start──► IN_PROGRESS ──complete──► COMPLETED
│ │ │
└────cancel──────────┴────cancel────────────┘──► CANCELLED
Elevator
IDLE ──request──► MOVING_UP / MOVING_DOWN ──no more stops──► IDLE
│ │
└──stops in direction────┘
└──reverse if stops in other direction──►
Booking (BookMyShow)
PENDING ──payment success──► CONFIRMED
│ │
│──payment fail / timeout──► CANCELLED ◄──cancel──┘
Interview One-Liners (What to Say)
| Situation | What to Say |
|---|---|
| Starting | "Let me clarify the requirements first. Are we focusing on [X] or the full system?" |
| Choosing entities | "I see these nouns in the requirements: [list]. I will make each a class." |
| Choosing patterns | "Since the [algorithm/behavior] varies, I will use the Strategy pattern." |
| Concurrency question | "I would use temporal locking with a TTL to prevent double-booking." |
| Scale question | "For the LLD, I will keep it single-process. At scale, I would add [index/cache/lock]." |
| Running out of time | "Let me implement the core flow and discuss these extensions verbally." |
| Edge cases | "Three edge cases I would handle: [1], [2], [3]. Let me show [1] in code." |
Entity Relationship Quick Reference
Composition (owns): ParkingLot ◆──── ParkingFloor
Screen ◆──── Seat
VendingMachine ◆──── Inventory
Aggregation (uses): Show ◇──── Movie
Trip ◇──── Rider, Driver
Group ◇──── User
Inheritance (is-a): HourlyPricing ──▷ PricingStrategy
IdleState ──▷ State
LOOKScheduler ──▷ SchedulingStrategy
Dependency (calls): ParkingLot ···► PricingStrategy.calculate()
BookingService ···► PaymentGateway
RideService ···► FareCalculator.calculate()
Checklist Before Submitting Your Design
- All core features from requirements are covered
- Each class has a single, clear responsibility
- Relationships (composition/aggregation/inheritance) are explicit
- At least one design pattern is applied and justified
- Code compiles and runs the happy path
- 3+ edge cases identified (at least 1 handled in code)
- You can walk through the full flow in under 2 minutes
Back to -> README