Episode 9 — System Design / 9.6 — LLD Problem Solving

9.6 — Interview Questions

How to use this material (instructions)

  1. Cover the Model Answer and attempt each question on paper or out loud (as if in an interview).
  2. Spend no more than 3-4 minutes per question for verbal answers.
  3. After answering, compare with the model answer and note gaps.
  4. For questions marked (Code), write working code in your editor before checking.
  5. Practice all 11 questions in a single mock-interview session once you feel ready.

Questions

Q1: What is your step-by-step approach for an LLD interview? (Beginner)

Model Answer:

I follow a 6-step approach within 45 minutes:

  1. Clarify requirements (5 min) — Ask functional vs. non-functional, define scope boundaries, confirm what is in/out of scope.
  2. Identify entities (5 min) — Extract nouns from requirements. Each major noun becomes a candidate class.
  3. Define relationships (5 min) — Determine has-a (composition/aggregation), is-a (inheritance), and uses (dependency) between entities.
  4. Design APIs and methods (5 min) — Extract verbs from requirements. Assign each verb to the responsible class as a method.
  5. Apply design patterns (5 min) — Use patterns where they naturally fit: Strategy for varying algorithms, State for lifecycle objects, Singleton for controllers.
  6. Implement and walk through (20 min) — Write clean code, trace one happy path end-to-end, then discuss edge cases.

The key is to not jump to code immediately. The first 20 minutes of analysis save time and produce a cleaner design.

Q2: How do you handle concurrent seat booking in a system like BookMyShow? (Intermediate)

Model Answer:

The core challenge is preventing two users from booking the same seat. I use a temporal locking approach:

  1. When a user selects seats, they are locked (status changes from AVAILABLE to LOCKED) for a timeout period (e.g., 5 minutes).
  2. The lock is associated with the user's session or booking ID.
  3. If the user completes payment within the timeout, seats move from LOCKED to BOOKED.
  4. If the timeout expires or payment fails, seats revert to AVAILABLE.

For the lock itself, in a distributed system:

  • Database-level: SELECT ... FOR UPDATE or optimistic locking with version columns.
  • Application-level: Redis distributed locks (e.g., Redlock) with TTL matching the timeout.
  • Atomic check-and-lock: The lockSeats() method must verify all seats are AVAILABLE and lock them in a single atomic operation (transaction).

This prevents double-booking while not holding locks indefinitely on abandoned carts.

Q3: Why is the State pattern the best fit for a vending machine? What would the code look like without it? (Intermediate)

Model Answer:

Without the State pattern, the VendingMachine class would have massive if-else or switch blocks in every method:

// WITHOUT State pattern (anti-pattern)
insertCoin(coin) {
  if (this.state === 'IDLE') {
    this.balance += coin;
    this.state = 'COIN_INSERTED';
  } else if (this.state === 'COIN_INSERTED') {
    this.balance += coin;
  } else if (this.state === 'DISPENSING') {
    throw new Error('Wait...');
  }
  // ... every method has this switch
}

Problems with this approach:

  • Open/Closed violation: Adding a new state (e.g., MAINTENANCE) requires modifying every method.
  • Error-prone: Easy to forget a state in one method.
  • Hard to read: Business logic is scattered across switch cases.

With the State pattern, each state is its own class. Adding MAINTENANCE means creating one new class with all its rules self-contained. Existing states are untouched.

Q4: In the Parking Lot problem, why use the Strategy pattern for pricing instead of just putting the logic in ParkingLot? (Intermediate)

Model Answer:

If pricing logic lives in ParkingLot, adding new pricing models (hourly, flat, time-of-day, subscription, weekend rates) means modifying the ParkingLot class every time — violating the Open/Closed Principle.

With Strategy:

  • Each pricing model is a separate class implementing calculate(ticket).
  • ParkingLot holds a reference to the current strategy and delegates to it.
  • Switching pricing is one line: lot.setPricingStrategy(new WeekendPricingStrategy()).
  • You can even compose strategies (e.g., a CompositePricingStrategy that applies surge on top of hourly).

The general rule: if an algorithm varies independently from the object using it, extract it as a Strategy.

Q5: How does the Splitwise "simplify debts" algorithm work, and what is its time complexity? (Intermediate)

Model Answer:

The algorithm works in three steps:

  1. Calculate net balances: For each user, sum all amounts they paid and subtract all amounts they owe. This gives a single net number per user.
  2. Separate into creditors (positive) and debtors (negative): Sort each list in descending order of absolute amount.
  3. Greedy matching: Use two pointers — match the largest debtor with the largest creditor. The settlement amount is min(debt, credit). Subtract from both and advance the pointer for whichever reaches zero.

Time complexity: O(N log N) where N is the number of users — dominated by the sorting step. The two-pointer matching is O(N).

Correctness: This greedy approach minimizes the number of transactions but does not guarantee the globally optimal minimum number of transactions (which is NP-hard in the general case). However, for practical group sizes (< 50 people), it works well and the difference is negligible.

Q6: In the Uber/Ola design, how would you find the nearest driver efficiently at scale? (Advanced)

Model Answer:

The naive approach (iterate all drivers, compute Haversine distance) is O(N) per request — fine for interviews but not for millions of drivers.

At scale, use spatial indexing:

  1. Geohashing: Encode lat/lng into a string hash. Nearby locations share a common prefix. Query by prefix to get candidates in the same cell and adjacent cells. Used by Uber.

  2. R-tree / Quadtree: Spatial data structures that partition 2D space. Allow O(log N) range queries ("all points within X km of this point").

  3. PostGIS / Redis Geo: Database-native spatial queries. Redis GEORADIUS returns all members within a radius in O(N+log(M)) where M is the number of stored points.

In practice:

  • Drivers periodically update their location (every 5 seconds).
  • Locations are stored in a geospatial index (Redis Geo or a Quadtree).
  • On a ride request, query the index for drivers within a radius (e.g., 5 km), filter by status=AVAILABLE and rideType, sort by distance, and return the top match.

Q7: The Elevator design uses SCAN and LOOK algorithms. When would you choose FCFS over LOOK? (Intermediate)

Model Answer:

FCFS is preferred when:

  • There are very few elevators (1-2) in a low-traffic building — simplicity wins.
  • Fairness is the priority over efficiency (each request is served in order).
  • The system is a prototype or MVP.

LOOK is preferred when:

  • There are many floors and high traffic — LOOK minimizes total travel distance.
  • Average wait time must be optimized.
  • The building is a commercial high-rise with predictable traffic patterns.

FCFS weakness: An elevator might pass Floor 6 on its way to Floor 10 (an earlier request), even though someone at Floor 6 is waiting. LOOK would stop at Floor 6 on the way.

LOOK weakness: If a new request keeps arriving in the current direction, requests in the opposite direction may wait a long time (starvation, though much less than with naive approaches).

In a real building, most systems use a weighted LOOK that factors in wait time, number of stops, and load to balance efficiency and fairness.

Q8: How would you extend the Parking Lot to support multiple entry/exit points? (Advanced)

Model Answer:

The current design has a single enter()/exit() flow. To support multiple entry/exit points:

  1. Create an EntryGate and ExitGate class: Each gate has an ID and a location (which floor/side it serves).

  2. Gate-aware spot assignment: When a vehicle enters through Gate G1 (near Floor 1), prefer spots on Floor 1. When entering through Gate G2 (near Floor 3), prefer spots on Floor 3. This reduces the vehicle's travel distance inside the lot.

  3. Modify ParkingLot: Instead of enter(vehicle), use enter(vehicle, gateId). The gate determines the search order for available spots.

  4. Exit gate billing: Each exit gate has a payment terminal. exit(ticketId, gateId) calculates the fee and opens the exit barrier.

  5. Capacity per zone: If certain gates serve certain floors, track per-zone capacity separately.

The key design principle: EntryGate and ExitGate are new entities with a reference to the ParkingLot. The ParkingLot itself changes minimally — just the spot search order.

Q9: What is the difference between composition and aggregation, and where do you see each in the problems we solved? (Beginner)

Model Answer:

Composition ("owns, cannot exist independently"):

  • ParkingLot owns ParkingFloors — if the lot is destroyed, floors are gone.
  • Screen owns Seats — seats do not exist without a screen.
  • VendingMachine owns Inventory.

Aggregation ("has, but can exist independently"):

  • Show references a Movie — the movie exists independently of any show.
  • Trip references a Rider and Driver — they exist before and after the trip.
  • Group references Users — users exist outside the group.

Rule of thumb: If deleting the container should delete the contained object, it is composition. If the contained object has its own lifecycle, it is aggregation.

In class diagrams:

  • Composition: filled diamond (container side).
  • Aggregation: hollow diamond (container side).

Q10: How would you handle payment failures in the BookMyShow system? (Intermediate)

Model Answer:

Payment failure handling follows a defensive approach:

  1. Seats are locked, not booked, during payment: This is the critical design decision. If payment fails, we only need to release the lock — no rollback of a "booking" is needed.

  2. On payment failure:

    • confirmBooking() receives a FAILED status from the payment service.
    • Seats are released (releaseSeats()).
    • Booking status is set to CANCELLED (or PAYMENT_FAILED for auditing).
    • User is shown a "Payment failed, please try again" message.

  3. Retry strategy:

    • The lock has a timeout (e.g., 5 minutes). The user can retry payment within this window.
    • Do not release seats on the first payment failure if the lock has not expired — let the user retry.
    • After 2-3 failures or lock expiry, release and cancel.

  4. Idempotency:

    • The payment call should include a unique bookingId as an idempotency key.
    • This prevents double-charging if the user retries or the network is flaky.

  5. Edge case — payment succeeded but our server crashed before marking CONFIRMED:

    • Use a reconciliation job that checks payment gateway records against booking statuses.
    • If payment is SUCCESS on gateway but booking is still PENDING, mark it CONFIRMED.

Q11: You have 45 minutes in a machine-coding round. How do you decide what to implement and what to skip? (Advanced)

Model Answer:

I use a priority-based approach:

Must implement (30 min):

  • Core entities with correct attributes.
  • The primary happy-path flow (e.g., in parking lot: enter -> park -> exit -> fee).
  • At least one design pattern that adds clear value (e.g., Strategy for pricing).
  • Clean, runnable code that I can demo.

Should implement if time permits (10 min):

  • Edge case handling (lot full, invalid ticket, double entry).
  • A second strategy/variation (e.g., flat pricing alongside hourly).
  • Input validation.

Discuss verbally, do not code (5 min):

  • Concurrency handling (locks, transactions).
  • Scalability (database indexes, caching).
  • Future extensions (reservations, EV spots).

Key principles:

  • Working code > perfect code. An 80% solution that runs beats a 100% solution that does not compile.
  • Name things well. Even if logic is incomplete, clear class/method names show design thinking.
  • Demonstrate extensibility by leaving hooks (e.g., setPricingStrategy()) even if you only implement one strategy.
  • Always save 5 minutes at the end to walk through the code with the interviewer.

Continue to -> 9.6-Quick-Revision