Low-Level Design

Clarify requirements, identify entities and their relationships, define interfaces and behaviours, pick patterns only where variation exists, then code the core flow and discuss concurrency and extensions.

1. Requirements: functional scope, what is out of scope, scale (single JVM vs distributed).
2. Entities: nouns become classes, verbs become methods; draw ownership (has-a) and inheritance (is-a).
3. Contracts: interfaces for the parts that vary (pricing, strategy, state).
4. Core flow: write the happy path end to end, then edge cases.
5. Concurrency and extensibility: where is shared mutable state, what changes next.

SOLID is five guidelines that keep classes small, replaceable and open to extension.

• S Single Responsibility: InvoicePrinter prints, InvoiceCalculator computes; one reason to change.
• O Open/Closed: add a new DiscountStrategy implementation instead of editing an if/else chain.
• L Liskov Substitution: a Square extends Rectangle that breaks setWidth semantics violates it; subtypes must honour the supertype contract.
• I Interface Segregation: split Worker into Workable and Eatable so robots are not forced to implement eat().
• D Dependency Inversion: OrderService depends on PaymentGateway (interface), injected via constructor.

Prefer composition for reuse and runtime flexibility; use inheritance only for a genuine is-a relationship with a stable contract.

• Inheritance couples subclass to parent internals (fragile base class) and is fixed at compile time.
• Composition lets you swap behaviour at runtime (Vehicle has a FeeStrategy).
• Java has single class inheritance, so composition plus interfaces avoids hierarchy explosions (ElectricSUV, ElectricSedan...).
• Sealed classes (Java 17) give controlled hierarchies when inheritance is appropriate.

Factory for choosing a concrete type from input, Builder for objects with many optional fields, Singleton for a single shared coordinator (use sparingly).

• Factory Method/Simple Factory: VehicleFactory.create(type) hides new.
• Abstract Factory: families of related objects (e.g., Windows vs Mac widgets).
• Builder: immutable Booking with optional fields; avoids telescoping constructors.
• Singleton: prefer an enum or DI-managed single bean; a hand-rolled one needs volatile double-checked locking.

public enum Registry { INSTANCE; private final Map<String,Object> m = new ConcurrentHashMap<>(); public Map<String,Object> map(){ return m; } }

Strategy swaps algorithms, State models lifecycle-dependent behaviour, Observer broadcasts events, Command encapsulates requests, Template Method fixes a skeleton.

• Strategy: pricing, eviction policy, payment methods.
• State: vending machine, ATM, elevator, order lifecycle; each state class handles the same events differently.
• Observer: notification fan-out, pub-sub, stock price listeners.
• Command: undo/redo, task queues, schedulers.
• Chain of Responsibility: logger levels, ATM cash dispensers, approval flows.

Adapter converts an incompatible interface, Decorator adds behaviour by wrapping, Facade simplifies a subsystem, Composite treats trees uniformly, Proxy controls access.

• Adapter: wrap a third-party StripeClient behind your PaymentGateway.
• Decorator: BufferedInputStream(new FileInputStream(..)), toppings on a pizza, rate-limiting wrapper.
• Composite: file system (Directory and File share Node).
• Proxy: lazy loading, caching, access control.
• Facade: BookingService hiding seat, payment and notification calls.

Identify the invariant that spans multiple fields, protect it with the narrowest lock that covers it, and prefer lock-free structures for single-variable state.

• synchronized/ReentrantLock for compound invariants (seat booking, balance transfer).
• ConcurrentHashMap.compute/merge for atomic per-key updates.
• AtomicInteger/LongAdder for counters; CAS loops for simple state.
• ReadWriteLock/StampedLock for read-heavy structures.
• Always acquire multiple locks in a consistent order (e.g., by account id) to avoid deadlock.

Use records for immutable value objects, enums (with fields/behaviour) for closed sets, sealed interfaces for closed type hierarchies, and mutable classes only for entities with identity and lifecycle.

public record Money(long cents, String currency) {
    public Money { if (cents < 0) throw new IllegalArgumentException(); }
    public Money plus(Money o) { return new Money(cents + o.cents, currency); }
}
public sealed interface Shape permits Circle, Rect {}
public record Circle(double r) implements Shape {}
public record Rect(double w, double h) implements Shape {}

• Never use double for money; use long minor units or BigDecimal.
• Override equals/hashCode only for value semantics (records do it for you).

Show that a good seam already exists: add an implementation of an interface or a new state class rather than modifying core logic. If no seam exists, say so, refactor minimally, and explain the cost.

• Typical extensions: new vehicle type, new payment method, new eviction policy, new notification channel.
• Point to the specific interface you would implement and the registry/factory that wires it.
• Mention backward compatibility (defaults, enum additions) and tests.

Inject dependencies (clock, ID generator, strategies, repositories) so unit tests can use fakes, and name the 3-4 scenarios you would test, including a concurrency test.

• Inject Clock instead of calling Instant.now(); makes parking fees and TTL deterministic.
• Keep pure logic (pricing, move validation) in side-effect-free methods.
• Concurrency test: ExecutorService with N threads and CountDownLatch hammering book(seat); assert exactly one success.

Model ParkingLot with floors of typed spots, issue a Ticket on entry, compute a fee by strategy on exit.

• Requirements: multiple floors, vehicle types (bike, car, truck), spot types, entry/exit gates, hourly pricing, full-lot handling.
• Entities: ParkingLot, Floor, Spot (type, occupied), Vehicle, Ticket, FeeStrategy, SpotAllocationStrategy (nearest, lowest floor).
• Concurrency: two cars must not get the same spot; use an atomic tryOccupy() per spot (CAS) or a lock per floor.
• Extensions: EV charging spots, reservations, payment, display boards (Observer).

class Spot {
    private final AtomicBoolean taken = new AtomicBoolean();
    final SpotType type;
    Spot(SpotType t){ type = t; }
    boolean tryOccupy(){ return taken.compareAndSet(false, true); }
    void free(){ taken.set(false); }
}
class ParkingLot {
    Optional<Ticket> park(Vehicle v, Instant now) {
        for (Floor f : floors)
            for (Spot s : f.spotsFor(v.type()))
                if (s.tryOccupy()) return Optional.of(new Ticket(UUID.randomUUID(), v, s, now));
        return Optional.empty();
    }
}

• Fee: FeeStrategy.compute(Duration) with hourly slabs; pick via vehicle type.
• Keep free spots in a queue per type for O(1) allocation instead of scanning.

Model each Elevator as a state machine (IDLE, MOVING_UP, MOVING_DOWN, DOOR_OPEN) with sorted stop sets, and a Dispatcher that assigns hall calls using a scheduling strategy.

• Requirements: N elevators, M floors, hall calls (up/down) and cab calls (floor), capacity, door open/close.
• SCAN (elevator) algorithm: continue in current direction serving stops via TreeSet, then reverse.
• Dispatcher strategy: nearest car moving in the same direction, else idle nearest; pluggable DispatchStrategy.
• Concurrency: each elevator runs a single-threaded loop consuming a queue of requests; dispatcher only enqueues.

class Elevator {
    int floor; Direction dir = Direction.IDLE;
    final TreeSet<Integer> up = new TreeSet<>(), down = new TreeSet<>();
    void addStop(int f) { (f >= floor ? up : down).add(f); }
    Integer nextStop() {
        if (dir != Direction.DOWN && !up.isEmpty()) { dir = Direction.UP; return up.first(); }
        if (!down.isEmpty()) { dir = Direction.DOWN; return down.last(); }
        dir = Direction.IDLE; return null;
    }
}

Use the State pattern: Idle, HasMoney, Dispensing, OutOfService, each handling insertCoin, select, cancel differently.

• Entities: VendingMachine, Inventory (slot -> product, qty), Product, Coin enum, State.
• Rules: dispense only when balance >= price, return change, refund on cancel, reject when sold out.
• Change-making: greedy works for canonical coin sets; otherwise DP.

interface State {
    default void insert(VendingMachine m, int cents){ throw new IllegalStateException(); }
    default void select(VendingMachine m, String slot){ throw new IllegalStateException(); }
}
class Idle implements State {
    public void insert(VendingMachine m, int c){ m.addBalance(c); m.setState(new HasMoney()); }
}
class HasMoney implements State {
    public void insert(VendingMachine m, int c){ m.addBalance(c); }
    public void select(VendingMachine m, String slot){ m.dispense(slot); }
}

• Make operations synchronized on the machine: it is one physical device.

Combine a hash map for lookup with a doubly linked list for recency order; both get and put are O(1). In Java, LinkedHashMap with access order does this in a few lines.

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LRUCache(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > capacity; }
}

• Interviewers often want the manual version: Map<K, Node> plus head/tail sentinels; get moves the node to head, put evicts tail when full.
• Not thread-safe; wrap with Collections.synchronizedMap or a lock (even get mutates order).

Define a RateLimiter.allow(key) interface and implement algorithms behind it; token bucket is the usual default because it allows bursts with a steady refill rate.

• Algorithms: fixed window (boundary bursts), sliding window log (exact, memory heavy), sliding window counter (approximate), token bucket, leaky bucket.
• Lazy refill: compute tokens from elapsed time on each call; no background thread.

class TokenBucket {
    private final long capacity; private final double refillPerNano;
    private double tokens; private long last;
    TokenBucket(long cap, double perSec){ capacity=cap; refillPerNano=perSec/1e9; tokens=cap; last=System.nanoTime(); }
    synchronized boolean tryAcquire() {
        long now = System.nanoTime();
        tokens = Math.min(capacity, tokens + (now - last) * refillPerNano);
        last = now;
        if (tokens >= 1) { tokens -= 1; return true; }
        return false;
    }
}

• Keep a ConcurrentHashMap<String, TokenBucket> per user/IP and evict idle entries.

Logger creates LogRecords, filters by level, and hands them to Appenders (console, file, async) that format with a Formatter.

• Entities: Level enum (DEBUG<INFO<WARN<ERROR), Logger (name, level, appenders), Appender, Formatter, LoggerFactory (cached per name).
• Patterns: Strategy (formatter), Observer-style appenders, Chain of Responsibility for level handlers, Singleton-ish factory.
• Performance: check isEnabled(level) before building messages; async appender with a bounded BlockingQueue and a drainer thread; define the overflow policy (drop or block).

enum Level { DEBUG, INFO, WARN, ERROR }
interface Appender { void append(LogRecord r); }
class Logger {
    private final List<Appender> appenders = new CopyOnWriteArrayList<>();
    private volatile Level level = Level.INFO;
    void log(Level l, String msg) {
        if (l.compareTo(level) < 0) return;
        LogRecord r = new LogRecord(l, msg, Instant.now());
        appenders.forEach(a -> a.append(r));
    }
}

Record each expense with a split strategy (equal, exact, percent), update a net balance per user pair, and simplify debts by reducing net balances with a greedy matching.

• Entities: User, Group, Expense (payer, amount, splits), Split, SplitStrategy, BalanceSheet.
• Validation: exact splits sum to total; percentages sum to 100; use long cents and assign the rounding remainder to the payer.
• Simplify: compute each user's net (owed minus owes); repeatedly match the max creditor with the max debtor via two heaps; at most n-1 transactions.

interface SplitStrategy { Map<String, Long> split(long total, List<String> users, Map<String, Long> params); }
class EqualSplit implements SplitStrategy {
    public Map<String, Long> split(long total, List<String> u, Map<String, Long> p) {
        long each = total / u.size(), rem = total % u.size();
        Map<String, Long> m = new LinkedHashMap<>();
        for (int i = 0; i < u.size(); i++) m.put(u.get(i), each + (i < rem ? 1 : 0));
        return m;
    }
}

Model City -> Theatre -> Screen -> Show -> ShowSeat, with seat status AVAILABLE/LOCKED/BOOKED; locking a seat with a TTL during payment prevents double booking.

• Entities: Movie, Theatre, Screen, Show, Seat, ShowSeat (per show state), Booking, Payment.
• Flow: search shows, pick seats, lockSeats (all or nothing), pay, confirm; unpaid locks expire.
• Lock acquisition must be atomic across multiple seats; sort seat ids and lock in order to avoid deadlock.

class ShowSeat {
    enum S { AVAILABLE, LOCKED, BOOKED }
    S status = S.AVAILABLE; Instant lockedUntil;
    synchronized boolean tryLock(Instant now, Duration ttl) {
        if (status == S.LOCKED && now.isAfter(lockedUntil)) status = S.AVAILABLE;
        if (status != S.AVAILABLE) return false;
        status = S.LOCKED; lockedUntil = now.plus(ttl); return true;
    }
}

• If locking seat 3 of 4 fails, release 1-2 (rollback). In the distributed version this is a DB row update with WHERE status='AVAILABLE' or a Redis lock with TTL.

Separate the catalog (Book metadata) from physical copies (BookItem), with Member, Loan and Fine entities; policies for loan length and fines are strategies.

• Requirements: search by title/author/ISBN, checkout/return, reservations, fines, max 5 books per member.
• Book (isbn, title, authors) has many BookItem (barcode, status AVAILABLE/LOANED/RESERVED).
• Checkout: validate member limit, item availability, create Loan(due = now + 14d).
• Return: compute fine daysLate * rate; if reservations exist, notify the first (Observer).
• Search: index by title/author maps (or an inverted index) rather than scanning.

class Loan {
    final BookItem item; final Member member; final LocalDate due;
    long fine(LocalDate returned, long perDayCents) {
        return Math.max(0, ChronoUnit.DAYS.between(due, returned)) * perDayCents;
    }
}

An ATM is a state machine (IDLE, CARD_INSERTED, PIN_VERIFIED, TRANSACTION) talking to a BankService interface; cash dispensing uses Chain of Responsibility over denominations.

• Flow: insert card, verify PIN (3 attempts then retain card), choose operation, execute, eject card.
• Entities: Card, Account, CashDispenser, Transaction (withdraw, balance, deposit).
• Withdrawal must be atomic: debit account first with a transaction id, dispense cash, and reverse the debit if the dispenser fails.
• Dispense: Handler500 -> Handler200 -> Handler100, each takes as many notes as possible and passes on the remainder.

abstract class NoteHandler {
    NoteHandler next; final int denom;
    NoteHandler(int d){ denom = d; }
    void dispense(int amount, Map<Integer,Integer> out) {
        if (amount >= denom) { out.put(denom, amount / denom); amount %= denom; }
        if (amount > 0 && next != null) next.dispense(amount, out);
    }
}

Model Board (8x8 of Square), an abstract Piece with canMove(board, from, to) per subclass, and a Game that enforces turns, check and checkmate.

• Entities: Game, Board, Piece (King, Queen, Rook, Bishop, Knight, Pawn), Player, Move.
• Polymorphism: each piece implements its movement; sliding pieces share a path-clear check in a base class.
• Game rules: turn order, cannot leave own king in check, special moves (castling, en passant, promotion), draw/stalemate.
• Check detection: after a tentative move, test whether any opponent piece attacks the king; undo if so. Store Move history for undo (Command).

abstract class Piece {
    final Color color;
    Piece(Color c){ color = c; }
    abstract boolean canMove(Board b, int fr, int fc, int tr, int tc);
}
class Knight extends Piece {
    Knight(Color c){ super(c); }
    boolean canMove(Board b, int fr, int fc, int tr, int tc) {
        int dr = Math.abs(fr - tr), dc = Math.abs(fc - tc);
        return dr * dc == 2 && !b.isOwn(tr, tc, color);
    }
}

A NotificationService accepts an event, resolves user preferences, renders a template, and sends via channel strategies (email, SMS, push), asynchronously with retries.

• Entities: Notification, Channel interface, Template, UserPreference, NotificationService.
• Adding a channel means implementing Channel and registering it; no change to the service (OCP).
• Reliability: send via a thread pool or queue; retry with backoff; record status; dedupe via an idempotency key.

interface Channel { void send(String to, String body) throws Exception; }
class NotificationService {
    private final Map<String, Channel> channels; private final ExecutorService pool = Executors.newFixedThreadPool(8);
    NotificationService(Map<String, Channel> c){ channels = c; }
    void notify(User u, String body) {
        for (String ch : u.enabledChannels())
            pool.submit(() -> {
                try { channels.get(ch).send(u.addressFor(ch), body); }
                catch (Exception e) { /* retry/backoff, record failure */ }
            });
    }
}

A Broker maps topics to subscribers; publishing appends to a per-topic log and each subscriber consumes at its own offset via its own thread or queue, so slow consumers do not block publishers.

• Entities: Topic, Message, Publisher, Subscriber (functional interface), Broker.
• Simple version: ConcurrentHashMap<String, CopyOnWriteArrayList<Subscriber>>, publish iterates and dispatches on an executor.
• Better: per-subscriber BlockingQueue + worker, giving ordering per subscriber and isolation.
• Optional: consumer groups, message offsets for replay, acknowledgments, dead-letter queue.

class Broker {
    private final Map<String, List<BlockingQueue<String>>> subs = new ConcurrentHashMap<>();
    BlockingQueue<String> subscribe(String topic) {
        BlockingQueue<String> q = new LinkedBlockingQueue<>();
        subs.computeIfAbsent(topic, t -> new CopyOnWriteArrayList<>()).add(q);
        return q;
    }
    void publish(String topic, String msg) {
        subs.getOrDefault(topic, List.of()).forEach(q -> q.offer(msg));
    }
}

Use the Composite pattern: Node is either a Directory (map of children) or a File (content); path operations walk the tree by splitting on /.

• Operations: mkdir -p, ls, addContentToFile, readContentFromFile, rm, optionally find.
• Directory keeps a TreeMap<String, Node> so ls is lexicographic.
• Each operation resolves the path in O(depth); thread safety via a ReadWriteLock on the tree or per-directory locks.

abstract class Node { final String name; Node(String n){ name = n; } }
class FileNode extends Node { StringBuilder data = new StringBuilder(); FileNode(String n){ super(n); } }
class Dir extends Node {
    final TreeMap<String, Node> kids = new TreeMap<>();
    Dir(String n){ super(n); }
    Dir mkdir(String name) { return (Dir) kids.computeIfAbsent(name, Dir::new); }
}

Keep counters per row, column and both diagonals per player; a player wins when any counter reaches N. Each move is O(1).

class TicTacToe {
    private final int n; private final int[] rows, cols; private int diag, anti;
    TicTacToe(int n){ this.n = n; rows = new int[n]; cols = new int[n]; }
    // player 1 adds +1, player 2 adds -1; returns winner or 0
    int move(int r, int c, int player) {
        int d = player == 1 ? 1 : -1;
        rows[r] += d; cols[c] += d;
        if (r == c) diag += d;
        if (r + c == n - 1) anti += d;
        if (Math.abs(rows[r]) == n || Math.abs(cols[c]) == n
            || Math.abs(diag) == n || Math.abs(anti) == n) return player;
        return 0;
    }
}

• Still validate bounds and occupied cells in a Board class; this snippet shows only the win check.
• Draw: moves == n*n with no winner.

Model Board with a jump map (snake heads and ladder bottoms to destinations), Dice, Player and a Game loop with turn queue.

• Setup: 100 cells; validate no cell is both a snake head and ladder start and that no snake ends beyond start loops.
• Turn: roll dice, if pos + roll > 100 stay; else move, apply jump once (and follow chains if rules say so); win when exactly 100.
• Extensibility: Dice interface (one/two dice, loaded dice for tests), configurable board size and win rules.

class Board {
    private final int size; private final Map<Integer, Integer> jumps;
    Board(int size, Map<Integer, Integer> jumps){ this.size = size; this.jumps = jumps; }
    int next(int pos, int roll) {
        int p = pos + roll;
        if (p > size) return pos;
        return jumps.getOrDefault(p, p);
    }
}

• Use ArrayDeque<Player>: poll, play, offer back unless won.

UrlShortener coordinates a KeyGenerator (strategy: counter+base62, hash, random), a UrlRepository and optional expiry; HLD concerns (sharding, caching) sit behind the repository interface.

• API: String shorten(String longUrl, Duration ttl), Optional<String> resolve(String code).
• Base62 of an atomic counter is collision free and short; hashing needs collision checks.
• Custom aliases: reject if taken (putIfAbsent).

class Base62 {
    private static final String A = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    static String encode(long n) {
        StringBuilder sb = new StringBuilder();
        do { sb.append(A.charAt((int) (n % 62))); n /= 62; } while (n > 0);
        return sb.reverse().toString();
    }
}
class UrlShortener {
    private final AtomicLong counter = new AtomicLong(1_000_000);
    private final ConcurrentMap<String, String> store = new ConcurrentHashMap<>();
    String shorten(String url) { String c = Base62.encode(counter.getAndIncrement()); store.put(c, url); return c; }
}

RideService finds nearby available drivers via a MatchingStrategy, offers the trip, and drives a Trip through states REQUESTED, ACCEPTED, STARTED, COMPLETED/CANCELLED; FareStrategy computes the price.

• Entities: Rider, Driver (location, status), Cab, Trip, Location, Payment.
• Matching: nearest available driver by haversine distance (or a geo-grid index); offer sequentially with a timeout.
• Concurrency: marking a driver unavailable must be atomic so two riders do not claim him (compareAndSet on status).
• Fare: base + per-km + per-minute, times surge multiplier from SurgeStrategy.

class Driver {
    private final AtomicReference<Status> status = new AtomicReference<>(Status.AVAILABLE);
    boolean tryReserve() { return status.compareAndSet(Status.AVAILABLE, Status.RESERVED); }
    void release() { status.set(Status.AVAILABLE); }
}
interface MatchingStrategy { Optional<Driver> match(Location pickup, Collection<Driver> candidates); }

Keep tasks in a PriorityQueue ordered by next run time; a single dispatcher thread waits until the earliest is due and submits it to a worker pool. This is what ScheduledThreadPoolExecutor does internally.

• Use DelayQueue<ScheduledTask> (implements getDelay and compareTo) so take() blocks until the head is due.
• Recurring tasks: after execution, compute the next time and re-insert (fixed rate vs fixed delay).
• Worker pool isolates slow tasks from the dispatcher; catch exceptions so one failure does not kill the loop.

class ScheduledTask implements Delayed {
    final Runnable r; final long at;
    ScheduledTask(Runnable r, long delayMs){ this.r = r; at = System.currentTimeMillis() + delayMs; }
    public long getDelay(TimeUnit u){ return u.convert(at - System.currentTimeMillis(), TimeUnit.MILLISECONDS); }
    public int compareTo(Delayed o){ return Long.compare(at, ((ScheduledTask) o).at); }
}
// dispatcher: while (true) pool.submit(queue.take().r);

Use ConcurrentHashMap entries holding value plus expiry, lazy expiry on read, a background sweeper, and atomic loading with computeIfAbsent to prevent stampedes.

• Per-key atomic load: map.compute(key, ...) runs the loader once for concurrent misses (keep loaders short; it holds a bin lock).
• Eviction: size bound with an LRU/LFU structure guarded by a lock, or delegate to Caffeine in real code.
• Expiry: check expiresAt on get; a ScheduledExecutorService removes stale entries periodically.
• Metrics: hit/miss counters in LongAdder.

class TtlCache<K, V> {
    private record Entry<V>(V value, long expiresAt) {}
    private final ConcurrentHashMap<K, Entry<V>> map = new ConcurrentHashMap<>();
    private final long ttlNanos;
    TtlCache(Duration ttl){ ttlNanos = ttl.toNanos(); }
    V get(K key, Function<K, V> loader) {
        long now = System.nanoTime();
        return map.compute(key, (k, e) ->
            e != null && e.expiresAt() > now ? e : new Entry<>(loader.apply(k), now + ttlNanos)).value();
    }
}