LLD exercises

A low-level design interview hands you a system small enough to fit on a whiteboard and asks for its classes: what they are, what each is responsible for, how they talk, and how the design changes when a requirement changes. The four exercises here are the classic set, and each is worked the way an interviewer wants to see it — requirements first, then the entities and their invariants, then the interfaces, then the one hard question the exercise exists to ask. The last section is how to run the forty minutes.

#Parking lot

Clarify. Levels and spots; spot sizes (motorcycle, compact, large); vehicle sizes; a vehicle takes the smallest spot that fits it; tickets on entry, payment on exit by time; several entrances. Out of scope unless asked: reservations, EV charging, payment providers.

Entities. ParkingLot (the aggregate root, holds Levels), Level (holds Spots), Spot (a size, a level, an occupant or empty), Vehicle (a size, a plate — and a sealed hierarchy Motorcycle | Car | Truck only if behaviour differs by type; a VehicleSize enum if only the size does), Ticket (spot, vehicle, entry time), Fee policy.

Invariants. A spot holds at most one vehicle; a vehicle occupies at most one spot; a ticket is issued only for an assigned spot. All three live in ParkingLot.park(Vehicle), which finds a spot, assigns it and issues the ticket in one synchronised step — the hard question.

The hard question is concurrency: two entrances, one spot left, both cars. The naive findFreeSpot() then assign() is the check-then-act race from the concurrency course. The answers, in order of preference: a lock per level (coarse, simple, correct — an entrance rarely contends with another for the same level); a per-spot AtomicReference<Vehicle> with compareAndSet(null, vehicle), retrying the next spot on failure (fine-grained, and the interviewer will ask you to explain ABA does not apply); or, if the lot is a database, SELECT ... FOR UPDATE SKIP LOCKED on the spots table, which the SQL course's locking lesson gave you. Say which and why.

Extensions they will add: pricing by vehicle type (a FeePolicy strategy), a display of free spots per level (a counter maintained under the same lock, not a scan), and a full lot (park returns an Optional<Ticket> or throws a domain exception, and you say which and why).

#Rate limiter

Clarify. Per client (an API key, a user, an IP); a limit like 100 requests per minute; what happens over the limit (reject with 429 and a Retry-After); a single process or a cluster.

Entities. RateLimiter with boolean tryAcquire(ClientId); a Bucket per client; a Clock injected for tests; a Policy (limit, window).

The design. The token bucket from the microservices course: a bucket per client with tokens and lastRefill; on each request, refill elapsed × rate tokens up to the capacity, then take one if available. Store buckets in a ConcurrentHashMap<ClientId, Bucket> and make tryAcquire per bucket atomic — a synchronized on the bucket, or compute on the map, which is atomic per key. Evict idle buckets, or the map is the memory leak the JVM course found. Compare with the fixed window (simpler, and it lets 200 requests through at a window boundary) and the sliding log (exact, and O(requests) memory per client); the interviewer wants to hear why the bucket is the usual choice.

The hard question is the cluster: ten instances each with their own map is a limit of 1,000, not 100. The answers: a shared store — the Redis course's rate limiter in one Lua script (INCR + EXPIRE, atomic on the server), which is what most real systems do; or a local bucket per instance with a share of the global limit, which is approximate and survives Redis being down. Say the trade-off: exact and dependent on a network hop, or approximate and local.

#LRU cache

Clarify. Capacity in entries; get and put in O(1); evict the least recently used on overflow; single-threaded or concurrent.

The design. A HashMap<K, Node> for O(1) lookup and a doubly linked list of nodes for O(1) reordering: get moves the node to the head, put inserts at the head and, over capacity, removes the tail. Write the Node class, the moveToHead and removeTail methods, and then say the thing that shows you know the library: LinkedHashMap with accessOrder = true and an overridden removeEldestEntry is this structure, in fifteen lines, and in an interview you write the linked list once to prove you can and then say you would use the map.

The hard question is concurrency. A synchronized wrapper serialises every get, which for a cache is the whole workload. The answers: a ConcurrentHashMap for the lookups with a lock only around the list reordering (and the admission that the ordering is then approximate under contention); or sharding the cache into N independent LRU segments by key hash, which is what production caches do; or Caffeine, whose window-TinyLFU beats LRU on real workloads, which is the answer for production and the sentence that ends the exercise well. Mention the stampede: two threads missing the same key both compute it, and computeIfAbsent is the fix, from the concurrency and caching courses.

#Notification system

Clarify. Kinds of notification (order shipped, password reset); channels (email, SMS, push); user preferences per kind and channel; retries when a provider fails; must not send twice; volume.

Entities. Notification (a kind, a recipient, a payload, an id); Channel interface with send(Notification); EmailChannel, SmsChannel, PushChannel; Preferences per user; Template per kind per channel; NotificationService.notify(UserId, Kind, Payload), which resolves preferences, renders templates, and dispatches.

The design is the patterns lessons applied: Channel is strategy; a ChannelRegistry map from ChannelType to implementation is the Spring-injected Map<String, Channel>; the preferences lookup is a policy object; rendering is a template method or a Function<Payload, Rendered> per kind; adding a channel is a new class and a registration, which is open/closed. Dispatch is asynchronous — notify enqueues, workers send — because a user-facing request must not wait for an SMS provider, and the queue is the bridge pattern's channel with a retry policy per channel.

The hard question is delivery guarantees. At-least-once from the queue means the worker may run twice for one notification; the idempotency lesson's answer is a sent record keyed by notification id and channel, checked before the send and written after, in the same transaction as the outbox when there is one. Retries with backoff for the provider's 5xx, a dead-letter for the 4xx, and a per-provider circuit breaker so one provider's outage does not fill the queue with retries. Then say what "exactly once" would cost and why nobody pays it.

#How to present

The forty minutes, in order, with the minutes that fit:

1. Clarify (5): ask the questions above out loud; write the answers; state what is out of scope. An interviewer marks this as much as the design.
2. Entities and invariants (10): the nouns, which one is the root, what must always be true. Draw boxes, not UML.
3. Interfaces (10): the two or three public methods that matter, with signatures; say what each returns on failure.
4. The hard question (10): raise it before they do — "the interesting part is two entrances and one spot" — and give the options with the trade-off, then pick.
5. Extensions (5): name two the design absorbs and one it does not, and what would change.

Throughout: name the pattern when you use it and say its cost; say Optional versus exception at every boundary; and when you write code, write the invariant-checking method, not the getters. The mistakes that lose the round: designing the whole system before clarifying, a class per noun with no behaviour (the anaemic model from the last lesson, on a whiteboard), and getting the concurrency question only when the interviewer forces it.