Low-Level Design (Machine Coding) Problems — Interview Questions

How to use this lesson

A 45–90 minute LLD round is scored on:

1. Clarifying requirements (scope in and out, scale, concurrency);
2. Core entities and relationships;
3. Class design that follows SOLID, with fitting patterns (not patterns for their own sake);
4. Working code for the core flows;
5. Extensibility (a new vehicle type, a new payment method);
6. Thread safety where state is shared.

Say what you're leaving out. Below, each problem gives the design skeleton and the points interviewers probe; the linked pages have full walkthroughs.

Q1. Design a parking lot.

Short answer:

• Entities: ParkingLot → Levels → ParkingSpots (with a type: compact, regular, large, EV, disabled); Vehicle (an abstract class, or a type enum); Ticket; EntryGate and ExitGate; Payment.
• Patterns:
  • Strategy for the spot allocation (nearest to the entrance, by level, by type) and for the pricing (hourly, flat rate, weekend);
  • Factory for vehicles and spots;
  • Singleton (or a single DI bean) for the lot;
  • Observer for the display boards (free-spot counts).
• Concurrency: two gates must not allocate the same spot. Keep per-type free-spot queues (ConcurrentLinkedDeque), or claim spots atomically (CAS on the spot status, or a lock per level). Persisted versions use a conditional database update.

interface SpotAllocationStrategy { Optional<ParkingSpot> allocate(VehicleType type); }
interface PricingStrategy { Money price(Ticket t, Instant exit); }

class ParkingSpot {
    private final String id; private final SpotType type;
    private final AtomicReference<Vehicle> occupant = new AtomicReference<>();
    boolean tryOccupy(Vehicle v) { return occupant.compareAndSet(null, v); }   // atomic claim
    void release() { occupant.set(null); }
}

Learn it in depth → Parking Lot

Q2. Design an elevator system.

Short answer:

• Entities: ElevatorController (the dispatcher), Elevator (current floor, direction, state: idle, moving up, moving down, doors open, maintenance), Request (hall calls, with a direction, and car calls), Door, Display.
• Patterns:
  • the State pattern for elevator behaviour;
  • Strategy for dispatching (nearest car, the SCAN/LOOK algorithm, zoning, destination dispatch);
  • Observer for displays;
  • Command for requests.
• Scheduling: each elevator keeps two sorted sets (floors to visit upwards and downwards: TreeSets), and serves in its current direction before reversing (LOOK), which avoids starvation.
• Concurrency: requests arrive from many threads, so use a thread-safe request queue; one control loop per elevator (a single writer per elevator's state).

Learn it in depth → Elevator System

Q3. Design BookMyShow (movie ticket booking).

Short answer:

• Entities: City → Cinema → Screen → Seat (row, number, type); Movie; Show (a movie on a screen at a time); ShowSeat (the seat state per show: available, locked, booked, with its price); Booking; Payment; User.
• The core problem: no double booking under concurrency:
  • temporary seat locks with a TTL (for example 10 minutes) while the user pays: a ShowSeat status plus a lock expiry, updated atomically (UPDATE show_seat SET status='LOCKED', locked_by=?, lock_until=? WHERE show_id=? AND seat_id IN (...) AND status='AVAILABLE', then check that the row count equals the seats requested; or a Redis SET NX PX per seat);
  • confirm on payment success; release on expiry or failure.
• Patterns: Strategy for pricing (seat type, time, dynamic) and payment methods; Observer for notifications; Factory for payments.
• Extensibility: offers and coupons (Decorator or Chain), several payment gateways.

Learn it in depth → Movie Ticket Booking System

Q4. Design a URL shortener (the LLD view).

Short answer:

• Components: a ShortenerService (shorten(longUrl, alias?, expiry?), resolve(code)), a CodeGenerator strategy, a UrlRepository, a cache, and analytics events.
• Code generation options:
  • Base62 encoding of a unique ID (from a counter, a range-allocated ID block, or a Snowflake ID): short and collision-free;
  • a hash (MD5 or SHA-256 of the URL, truncated) with collision handling;
  • random 7-character codes with a uniqueness check.
  • Seven Base62 characters give 62⁷ ≈ 3.5 trillion codes.
• Details:
  • custom aliases (validated, and reserved words blocked);
  • expiry;
  • 301 versus 302 (301 is cached by browsers, which loses analytics; use 302 or 307 when you track clicks);
  • rate limiting;
  • malicious-URL checks;
  • an idempotent option (the same long URL returns the same code, per user).

final class Base62 {
    private static final char[] ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
    static String encode(long id) {
        StringBuilder sb = new StringBuilder();
        do { sb.append(ALPHABET[(int) (id % 62)]); id /= 62; } while (id > 0);
        return sb.reverse().toString();
    }
}

Learn it in depth → Design a URL Shortener

Q5. Design a file system (in memory).

Short answer:

• The Composite pattern: an abstract Entry (name, parent, created and modified times, permissions), with File (content, size) and Directory (children: Map<String, Entry>, and its size is the sum of its children's).
• Operations: mkdir -p, ls (sorted), addContentToFile, readContentFromFile, rm, mv, and find (with a Visitor, or recursive search filtered by a Specification or predicate: name pattern, size, extension).
• Path resolution: split on /, and walk from the root (handling . and ..).
• Extensibility: symlinks (a Proxy entry), permissions (ACL checks), quotas.
• Concurrency: a lock per directory, or a ReadWriteLock for the tree; ConcurrentHashMap children for simple cases.

abstract sealed class Entry permits File, Directory {
    final String name; Directory parent;
    Entry(String name) { this.name = name; }
    abstract long size();
}
final class File extends Entry {
    private final StringBuilder content = new StringBuilder();
    File(String n) { super(n); }
    long size() { return content.length(); }
    void append(String s) { content.append(s); }
}
final class Directory extends Entry {
    final Map<String, Entry> children = new TreeMap<>();           // sorted for ls
    Directory(String n) { super(n); }
    long size() { return children.values().stream().mapToLong(Entry::size).sum(); }
}

Learn it in depth → Composite & Proxy

Q6. Design Splitwise.

Short answer:

• Entities: User, Group, Expense (the payer or payers, the amount, participants, and a split type), Split (per user: an owed amount), BalanceSheet.
• The Strategy pattern for splits: EqualSplit, ExactSplit, PercentSplit, ShareSplit, each validating the input (the percentages sum to 100; the exact amounts sum to the total), and handling rounding (give the remainder paisa or cent to someone deterministically; use BigDecimal or long minor units).
• Balances: a map of (debtor, creditor) → amount, or a net balance per user.
• Simplify debts: compute each user's net balance; greedily match the largest creditor with the largest debtor (two heaps), which gives at most n−1 transactions. (The true minimum number of transactions is NP-hard, but greedy is the standard answer.)

Learn it in depth → Splitwise Expense Sharing

Q7. Design a vending machine.

Short answer:

• The State pattern is the core. The states are Idle, HasMoney, Dispensing, OutOfStock and Maintenance, and each handles insertCoin, selectProduct, dispense and refund differently, so there are no giant if/else blocks.
• Entities: Inventory (slot → product and count), Product (price), a Coin or Note enum, and a CashBox, with a change-making algorithm (greedy for canonical coin systems; DP in general).
• Edge cases: insufficient money; product out of stock; unable to make change (refuse or refund); cancellation refunds; concurrency (usually one user at a time, so synchronise the machine's operations).

interface VendingState {
    void insertMoney(VendingMachine m, int amount);
    void select(VendingMachine m, String slot);
    void cancel(VendingMachine m);
}
final class IdleState implements VendingState {
    public void insertMoney(VendingMachine m, int amount) { m.addBalance(amount); m.setState(new HasMoneyState()); }
    public void select(VendingMachine m, String slot) { throw new IllegalStateException("Insert money first"); }
    public void cancel(VendingMachine m) { }
}

Learn it in depth → Vending Machine

Q8. Design a chess game.

Short answer:

• Entities: Game (players, board, turn, status, move history), Board (an 8×8 grid of Cells), an abstract Piece (colour) with subclasses King, Queen, Rook, Bishop, Knight and Pawn, Move (from, to, piece, captured piece, promotion), Player (human or AI strategy).
• Movement rules: polymorphic piece.legalMoves(board, from). Sliding pieces share direction-based logic. Then filter out moves that leave your own king in check (simulate them on a copy, or apply and undo).
• Special rules: castling (the king and rook haven't moved; the squares between aren't attacked), en passant, promotion, and draw rules (stalemate, the 50-move rule, threefold repetition).
• Patterns:
  • the Command pattern for moves (which makes undo easy);
  • Memento or the history, for undo and repetition detection;
  • Strategy for AI players;
  • Observer for the UI.

Learn it in depth → Chess Engine Design

Q9. Design an ATM machine.

Short answer:

• Entities: ATM (cash dispenser, card reader, keypad, screen, printer), Card, Account, BankService (an interface to the bank: authentication, balance, debit), Transaction (withdrawal, deposit, balance inquiry, transfer).
• The State pattern: Idle → CardInserted → Authenticated → TransactionSelected → Dispensing → Idle, with a PIN-retry limit (then retain the card).
• The cash dispenser: a Chain of Responsibility over note denominations (2000 → 500 → 200 → 100), each dispensing what it can and passing the remainder on; validate that it's possible before debiting.
• Consistency: debit the account before dispensing, idempotently (a transaction ID). If the dispenser fails after the debit, reverse it (a compensating transaction), and log everything for reconciliation.
• Security: don't store PINs (they're verified by the bank or HSM); timeouts; audit logs.

Learn it in depth → ATM System

Q10. Design a logging framework.

Short answer:

• Components:
  • a Logger (named, and hierarchical: com.app.booking inherits from com.app);
  • Level (TRACE < DEBUG < INFO < WARN < ERROR), with a level check first (cheap when disabled; lazy Supplier<String> messages);
  • LogEvent (timestamp, level, logger, thread, message, exception, MDC context);
  • Appenders (console, file with rolling, remote), each with a Layout or Formatter (pattern, JSON);
  • Filters.
• Patterns:
  • Chain of Responsibility or Observer (an event goes to several appenders);
  • Strategy for the layouts;
  • Factory for loggers (a cached LoggerFactory.getLogger(name));
  • Singleton for the configuration.
• Performance and concurrency:
  • asynchronous appenders (a bounded ring buffer, with a policy when it's full: block, drop DEBUG, or discard);
  • thread-safe appenders (one writer thread);
  • flush on shutdown (a shutdown hook);
  • no string formatting when the level is disabled.

Learn it in depth → Design a Logging Framework

Q11. Design a notification system (LLD).

Short answer:

• Entities: Notification (recipient, template ID and parameters, channel preferences, priority), Channel (an interface: EmailChannel, SmsChannel, PushChannel), TemplateEngine, UserPreferenceService, NotificationService.
• Patterns:
  • Strategy for the channels (add WhatsApp without touching the existing code: open/closed);
  • Observer or pub/sub (domain events trigger notifications);
  • Factory for channel selection;
  • Decorator for cross-cutting behaviour (retry, rate limiting, logging around send);
  • Template Method for the common send flow (render, validate, send, record).
• Reliability: asynchronous dispatch through queues; retries with backoff; idempotency keys (no duplicates); per-user rate limits; quiet hours; a delivery status record.

Learn it in depth → Notification Observer / PubSub Design

Q12. Design a cache with eviction.

Short answer:

• The interface: Cache<K, V> with get, put, remove, an optional TTL, and statistics (hits, misses, evictions).
• The eviction policy as a Strategy: EvictionPolicy<K> with keyAccessed(k), keyAdded(k), keyRemoved(k) and evict(). Implementations:
  • LRU: a HashMap plus a doubly linked list;
  • LFU: frequency buckets;
  • FIFO.
  • All are O(1).
• TTL: store the expiry per entry; expire lazily on read, plus a periodic cleaner (or a timer wheel or priority queue of expiries).
• Thread safety: a simple global lock, striping (several segments, each with its own policy), or read-mostly designs. Production-grade: Caffeine (W-TinyLFU, buffered policy updates).
• Extras: a loader for read-through (computeIfAbsent-style, with single-flight protection against a stampede), a maximum size or weight, and eviction listeners.

Learn it in depth → Cache with Pluggable Eviction Policy

Q13. Design a ride-sharing app (LLD).

Short answer:

• Entities: Rider, Driver (a vehicle, location, and status: offline, available, on trip), Location, RideRequest, Trip (a state machine: REQUESTED → DRIVER_ASSIGNED → ARRIVED → IN_PROGRESS → COMPLETED / CANCELLED), Fare, Payment, Rating.
• Strategies:
  • driver matching (nearest available; best rated; batched matching);
  • pricing (base + distance + time, surge multipliers by zone);
  • payment methods.
• Finding nearby drivers: a spatial index (a geohash or H3 grid cell → a set of available drivers; a quadtree), updated from location pings.
• Concurrency: a driver must be assigned to one ride only: an atomic status transition (CAS AVAILABLE → RESERVED) with a timeout if the driver doesn't accept, then offer the ride to the next driver.
• Patterns: State (trip), Observer (notifying the rider and driver of trip updates), Strategy (matching and pricing), Factory (vehicle types: auto, mini, sedan).

Learn it in depth → Ride Booking Class Model

Q14. Design a distributed ID generator.

Short answer:

• Requirements: unique across nodes, roughly time-ordered (good for database index locality), 64-bit, very high throughput, and no central bottleneck.
• A Snowflake-style layout: 1 unused sign bit, a 41-bit timestamp (milliseconds since a custom epoch, about 69 years), a 10-bit machine ID (1,024 nodes), and a 12-bit sequence (4,096 IDs per millisecond per node).
  • A synchronized nextId() increments the sequence within the same millisecond, and waits for the next millisecond when the sequence overflows.
  • Clock moving backwards: refuse, or wait until it catches up (or use a logical clock).
  • Machine IDs are assigned through configuration, ZooKeeper or etcd leases, or derived from the pod ordinal.
• Alternatives:
  • UUIDv7 (128-bit and time-ordered, no coordination needed; standardised in RFC 9562);
  • database segment allocation (each node reserves blocks of 1,000 IDs from a table: simple, and dense);
  • ULID.

public final class SnowflakeIdGenerator {
    private static final long EPOCH = 1_704_067_200_000L;          // 2024-01-01T00:00:00Z
    private final long machineId; private long lastMs = -1, sequence = 0;
    public SnowflakeIdGenerator(long machineId) {
        if (machineId < 0 || machineId > 1023) throw new IllegalArgumentException("machineId 0..1023");
        this.machineId = machineId;
    }
    public synchronized long nextId() {
        long now = System.currentTimeMillis();
        if (now < lastMs) throw new IllegalStateException("clock moved backwards by " + (lastMs - now) + " ms");
        if (now == lastMs) {
            sequence = (sequence + 1) & 0xFFF;                       // 12 bits
            if (sequence == 0) while ((now = System.currentTimeMillis()) <= lastMs) Thread.onSpinWait();
        } else sequence = 0;
        lastMs = now;
        return ((now - EPOCH) << 22) | (machineId << 12) | sequence;
    }
}

Learn it in depth → Design a Distributed ID Generator

Follow-up questions this topic invites — and their answers

Q: How do you avoid over-engineering in an LLD round? A: Start with the minimal classes for the core use cases, apply a pattern only where it removes a real conditional or enables a stated extension, and verbally note further extensions instead of coding them all.

Q: Where should concurrency control live in these designs? A: At the point of contention: the spot, seat or driver being claimed. Use an atomic state transition (CAS, a conditional database update) rather than a global lock, so unrelated operations proceed in parallel.

Q: Interface or abstract class for entities like Piece or Vehicle? A: Use an abstract class (or a sealed hierarchy) when there's shared state and behaviour (position, colour); interfaces for capabilities and strategies (PricingStrategy, Channel). Sealed classes (Java 17) let pattern-matching switch be exhaustive.

Q: How do you make an LLD testable? A: Depend on interfaces (clock, ID generator, repositories, payment gateway), inject them through constructors, and keep the domain logic pure, so tests use fakes (a fixed Clock, an in-memory repository).