Practical Coding and Design Interviews

Learning Objectives

Follow a repeatable structure for OO design interviews.

Implement classic exercises (LRU cache, rate limiter) cleanly with tests.

Practise common prompts: parking lot, elevator, vending machine, library, chess/card game, notifications, logging, rate limiter, cache, file system, cluster mode controller.

Prerequisites: Modules 25, 83–85.

Intuition and Definition

A design-interview answer, in order:

Clarify requirements and assumptions (scale, concurrency, persistence, failure).

Use cases — main and alternative flows.

Class model — core entities, value objects, interfaces; a quick UML sketch.

API and invariants — public methods, what always holds.

Implementation of the core — clean, compilable.

Tests — happy path, boundaries, failures.

Error handling — what fails and how it's reported.

Complexity and resources — time/space, threads.

Trade-offs — what you'd do differently at 10× scale.

Extensions — how the design absorbs new requirements.

Why It Matters

Interviewers grade the *process* — clarifying, structuring, communicating trade-offs — as much as the code.

Syntax and Language Notes

Use the language you're strongest in; keep code compilable; name classes and methods in the domain's language.

Complete Example

LRU cache — O(1) get/put with a hash map + doubly linked list, plus token-bucket rate limiter — with tests:

#include <cassert>
#include <iostream>
#include <list>
#include <optional>
#include <string>
#include <unordered_map>

template <class K, class V>
class LruCache {
    size_t cap_;
    std::list<std::pair<K, V>> items_;                                  // front = most recently used
    std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> index_;
public:
    explicit LruCache(size_t cap) : cap_(cap) { if (cap == 0) throw std::invalid_argument("capacity must be > 0"); }
    std::optional<V> get(const K& k) {
        auto it = index_.find(k);
        if (it == index_.end()) return std::nullopt;
        items_.splice(items_.begin(), items_, it->second);             // move to front, O(1)
        return it->second->second;
    }
    void put(const K& k, V v) {
        if (auto it = index_.find(k); it != index_.end()) {
            it->second->second = std::move(v);
            items_.splice(items_.begin(), items_, it->second);
            return;
        }
        if (items_.size() == cap_) {                                   // evict least recently used
            index_.erase(items_.back().first);
            items_.pop_back();
        }
        items_.emplace_front(k
…

LRU tests passed
rate limiter decisions: YYYnnYYn

Step-by-Step Walkthrough

LRU: the list keeps recency order; the map points into the list so both lookup and "move to front" are O(1); eviction removes the list's tail and its map entry.

Tests cover hit, miss, eviction order and update-in-place.

Token bucket: tokens refill continuously at 1/s up to the burst capacity of 3. The burst of three passes (t=0, 0.1, 0.2), leaving 0.2 tokens; t=0.3 and t=0.9 are refused (0.3 and 0.9 tokens); by t=1.4 a full token has accumulated (pass), by t=2.5 another (pass), and t=2.6 is refused again.

Time is a parameter, so the limiter is deterministic and testable (Module 67).

Common Mistakes

Jumping into code before clarifying requirements.

Inheritance hierarchies for data that only differs by a field (vehicle types, piece colours).

Ignoring concurrency when the prompt implies it (shared cache, rate limiter per user).

No tests or invariants mentioned.

Over-engineering: twelve patterns for a 45-minute exercise.

Trade-offs and Alternatives

For the cache: a thread-safe version needs a lock (or sharding); a distributed cache needs eviction coordination and consistency decisions. For rate limiting: token bucket allows bursts, leaky bucket smooths output, sliding windows trade memory for accuracy; distributed limiters need a shared store (Redis) or approximate per-node limits.

Real-World Use

Practice prompts and the key design idea for each:

spot allocation by size, tickets, pricing strategy, no vehicle hierarchy (Modules 25, 84) state machine per car, scheduling policy (SCAN), request queues, invariants (Module 85) states (Idle, HasMoney, Dispensing), inventory, change-making, cancel/refund (Module 43)

Book vs copy, Loan as association class, holds queue, fines (Module 83) Chess / card game

Board/Deck value types, Move as command (undo), rules per piece (strategy), game state machine channel interface, preferences, retries, outbox, rate limits (Module 84) levels, sinks, decorators, async queue, shutdown flush (Module 85) token bucket, per-key buckets, clock injection, concurrency (this module)

LRU/LFU, TTL, thread safety, stampede protection (this module, Module 60)

Composite (directories/files), paths, permissions, iterators (Modules 35, 46) Cluster mode controller modes as states, signal validity, warning priorities, HAL port (Module 85)

Practice

Q1. (Easy) Why does the LRU cache use a linked list and a map instead of only a map?

Answer: The map gives O(1) lookup but no order; the list keeps recency order with O(1) moves via splice; together both operations are O(1).

Q2. (Medium) How would you make the cache thread-safe?

Answer: Protect get/put with one mutex (note that get mutates order, so it can't be a shared/read lock), or shard the cache into N independent caches by key hash to reduce contention.

Q3. (Advanced) Design a per-user rate limiter for an API with millions of users.

Answer: A token bucket per user key stored in a shared fast store (Redis) with atomic updates (Lua script or INCR with expiry for fixed windows), lazy creation and TTL eviction of idle keys, a fallback policy if the store is unavailable (fail open vs closed), and headers reporting remaining quota; inject the clock for tests.

Interview Question

Q1. "Design a vending machine." Answer: Clarify (coins/cards? change? multiple items per purchase?). Classes: VendingMachine (context), State (Idle, HasMoney, Dispensing, OutOfService) or a transition table, Inventory (slot → product, count), Money/Coin value types, ChangeMaker (greedy for canonical coin systems, DP otherwise), Display port. API: insert(coin), select(slot), cancel(). Invariants: never dispense without sufficient credit, never sell an empty slot, return exact change or refuse the sale beforehand. Tests: every state × event, insufficient change, sold-out, cancel refunds all credit. Extensions: card payments (new payment strategy), remote telemetry (observer/outbox).

Quick Quiz

Q1. First step in a design interview?

Answer: Clarify requirements and assumptions.

Q2. Complexity of LRU get with map + list?

Answer: O(1) average.

Q3. Why pass time into the rate limiter?

Answer: Determinism and testability.

Summary

Clarify → model → API/invariants → code → tests → trade-offs → extensions.

Practise the classic prompts; keep designs proportionate.

Related: Modules 25, 43, 60, 67, 83–85.