Knowledge Guide
Home › OO & Low-Level Design › OO Design Problems

OO Design Problems — Arming the Senior Follow-ups (Deep Dive)

OO Design Problems — Arming the Senior Follow-ups (Connections, Concurrency, Holds & Rules) (Deep Dive)

The five OO design solution pages in this guide (LinkedIn, Parking Lot, Stack Overflow, Movie Ticket Booking, Blackjack) each nail the base class model and the headline mechanism — but a senior interviewer's job is to keep pulling on the thread until something specific breaks, and each page leaves at least one thread hanging. This page arms those exact follow-ups: not "how would you scale it" in the abstract, but the concrete mechanism, code, and trade-off for the question that actually gets asked next.

A closing section adds a judgment layer none of the five pages needed until now: a database-native way to make overlapping bookings physically impossible, and when to reach for the Visitor pattern versus a streaming fold when an interviewer asks for five different summaries of the same data.

1. LinkedIn — Nth-degree connections and mutual connections, for real

Mechanism: the connection graph is unweighted, so BFS's own layer number is the degree — a member discovered when the queue is at layer k is exactly k hops away — and when you only need the distance between two specific members (not everyone's), expanding a search frontier from both ends and stopping the moment they touch explores far fewer nodes than a one-directional search out to the same depth.

Single-source, "show me everyone within N hops": standard BFS, tagging each member with the layer at which it was first reached, and refusing to expand past the cap.

Java

// All members within N hops of start (BFS, level = degree).
public Map<Member, Integer> connectionsWithinDegree(Member start, int maxDegree) {
    Map<Member, Integer> degreeOf = new HashMap<>();
    Queue<Member> queue = new ArrayDeque<>();
    degreeOf.put(start, 0);
    queue.add(start);
    while (!queue.isEmpty()) {
        Member cur = queue.poll();
        int d = degreeOf.get(cur);
        if (d == maxDegree) continue;            // do not expand past the cap
        for (Member nbr : cur.getConnections()) {
            if (!degreeOf.containsKey(nbr)) {    // mark visited BEFORE enqueue
                degreeOf.put(nbr, d + 1);
                queue.add(nbr);
            }
        }
    }
    degreeOf.remove(start);
    return degreeOf;
}

Go

// All members within N hops of start (BFS, level = degree).
func connectionsWithinDegree(start *Member, maxDegree int) map[*Member]int {
    degreeOf := map[*Member]int{start: 0}
    queue := []*Member{start}
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        d := degreeOf[cur]
        if d == maxDegree {
            continue // do not expand past the cap
        }
        for _, nbr := range cur.Connections {
            if _, seen := degreeOf[nbr]; !seen { // mark visited before enqueue
                degreeOf[nbr] = d + 1
                queue = append(queue, nbr)
            }
        }
    }
    delete(degreeOf, start)
    return degreeOf
}

Point-to-point, "how far apart are Dev and Zoe?" — bidirectional BFS. Explore one layer outward from Dev, then one layer outward from Zoe, checking after each half-step whether the two explored sets now overlap. The moment they do, the answer is the sum of the two half-depths — you never had to explore anywhere near the full depth from either side.

Bidirectional BFS from Dev and Zoe meeting at Kai and Mo after two rounds each way
Bidirectional BFS from Dev and Zoe meeting at Kai and Mo after two rounds each way

Traced: Dev to Zoe over a real adjacency

Extend the base LinkedIn page's adjacency with two more hops: Dev-{Ada,Sam}, Ada-Kai, Sam-Mo, Kai-Ray, Mo-Ray, Ray-Zoe. The shortest path from Dev to Zoe is 4 hops long (there are two equally-short paths, via Kai and via Mo). Bidirectional BFS finds this without ever exploring 4 layers from one side:

RoundExpand from Dev (forward)Expand from Zoe (backward)Intersection?
1frontier → {Ada, Sam} at depth 1frontier → {Ray} at depth 1none yet
2frontier → {Kai, Mo} at depth 2frontier → {Kai, Mo} at depth 2 (Ray's neighbors)Kai and Mo both seen from Zoe's side → stop

The backward expansion at round 2 lands on Kai and Mo — both already known to the forward search at depth 2 — so the answer is 2 + 2 = 4. A one-directional BFS from Dev alone would have had to fully expand 4 layers before ever reaching Zoe; bidirectional search only ever expanded 2 layers from each side.

// Degree of separation between two members, or -1 if not connected within maxDegree.
public int degreeOfSeparation(Member a, Member b, int maxDegree) {
    if (a.equals(b)) return 0;
    Map<Member,Integer> distA = new HashMap<>(); distA.put(a, 0);
    Map<Member,Integer> distB = new HashMap<>(); distB.put(b, 0);
    Set<Member> frontierA = Set.of(a);
    Set<Member> frontierB = Set.of(b);
    for (int round = 1; round <= maxDegree; round++) {
        frontierA = expandFrontier(frontierA, distA, round);
        for (Member m : frontierA) if (distB.containsKey(m)) return round + distB.get(m);
        frontierB = expandFrontier(frontierB, distB, round);
        for (Member m : frontierB) if (distA.containsKey(m)) return distA.get(m) + round;
    }
    return -1;
}

private Set<Member> expandFrontier(Set<Member> frontier, Map<Member,Integer> dist, int depth) {
    Set<Member> next = new HashSet<>();
    for (Member cur : frontier)
        for (Member nbr : cur.getConnections())
            if (!dist.containsKey(nbr)) { dist.put(nbr, depth); next.add(nbr); }
    return next;
}

Why cap at 2nd or 3rd degree

The cost is exponential in the branching factor b (average connections per member — a few hundred on LinkedIn): a one-directional search to depth d touches roughly b^d nodes, while bidirectional search to the same total distance touches roughly 2·b^(d/2) — a huge reduction, but still exponential in d. At b≈300, degree 2 already touches on the order of 300² = 90,000 nodes and degree 4 is already 300⁴ ≈ 8×10⁹. Past 2nd or 3rd degree the graph is so densely connected (small-world effect) that almost every member is reachable anyway, so the count stops being a meaningful signal of closeness — LinkedIn's UI literally caps the displayed badge at "3rd+" rather than computing an exact degree past that point. It is a relevance and cost decision, not an algorithmic limitation.

Mutual connections

Mechanism: mutual connections is a set intersection of the two members' adjacency sets, not a second graph traversal — scan the smaller set and probe the larger one by hash lookup.

Java

// O(min(|A|,|B|)) hash lookups, not O(|A|*|B|).
public Set<Member> mutualConnections(Member x, Member y) {
    Set<Member> a = x.getConnectionSet(), b = y.getConnectionSet();
    Set<Member> small = a.size() <= b.size() ? a : b;
    Set<Member> large = small == a ? b : a;
    Set<Member> mutual = new HashSet<>();
    for (Member m : small) if (large.contains(m)) mutual.add(m);
    return mutual;
}

Go

// O(min(|A|,|B|))
func mutualConnections(x, y *Member) map[*Member]bool {
    small, large := x.ConnectionSet, y.ConnectionSet
    if len(large) < len(small) {
        small, large = large, small
    }
    mutual := map[*Member]bool{}
    for m := range small {
        if large[m] {
            mutual[m] = true
        }
    }
    return mutual
}

2. Parking Lot — finding WHICH spot in O(1), not a scan

Mechanism: the base page's isFull(type) answers "is there room?" from an aggregate counter in O(1) — but admission also needs to name an actual spot, and scanning the floor's seat array for the first free one is O(n). Keep a free-list (or a bitset) per (floor, spotType) so both allocate and release are O(1) (or O(log n) if you want the spots ranked, not just any free one).

The structure — a stack of free spot ids per type:

Java

// Per (floor, spotType): O(1) allocate/free via a free-list of spot ids.
public class FreeSpotIndex {
    private final Map<SpotType, Deque<Integer>> freeSpots = new EnumMap<>(SpotType.class);

    public FreeSpotIndex(Map<SpotType, List<Integer>> allSpotIdsByType) {
        for (var e : allSpotIdsByType.entrySet())
            freeSpots.put(e.getKey(), new ArrayDeque<>(e.getValue()));
    }

    /** O(1): pop any free spot id of this type, or null if none. */
    public synchronized Integer allocate(SpotType type) {
        Deque<Integer> free = freeSpots.get(type);
        return (free == null || free.isEmpty()) ? null : free.pop();
    }

    /** O(1): return a spot to the pool on vehicle exit. */
    public synchronized void release(SpotType type, int spotId) {
        freeSpots.get(type).push(spotId);
    }
}

Go

type FreeSpotIndex struct {
    mu        sync.Mutex
    freeSpots map[SpotType][]int // used as a stack
}

func (f *FreeSpotIndex) Allocate(t SpotType) (int, bool) {
    f.mu.Lock()
    defer f.mu.Unlock()
    ids := f.freeSpots[t]
    if len(ids) == 0 {
        return 0, false
    }
    last := ids[len(ids)-1]
    f.freeSpots[t] = ids[:len(ids)-1] // O(1)
    return last, true
}

func (f *FreeSpotIndex) Release(t SpotType, spotID int) {
    f.mu.Lock()
    defer f.mu.Unlock()
    f.freeSpots[t] = append(f.freeSpots[t], spotID) // O(1)
}

Two variants worth knowing: if a floor has few enough spots per type to fit in one machine word, a bitset (1 bit per spot, 0 = free) makes "find any free spot" a single CPU instruction:

// Bitset variant: find-first-free via trailing-zero count.
long freeMask = ~occupiedMask;              // 1 = free
if (freeMask != 0) {
    int spotIndex = Long.numberOfTrailingZeros(freeMask); // O(1)
    occupiedMask |= (1L << spotIndex);
}

If instead you want the best spot (closest to the entrance, not just any free one), swap the stack for a min-heap keyed by distance-to-entrance: allocate becomes peek-then-pop and release becomes push, both O(log n) — you trade the free-list's O(1) for a ranked assignment. Use a bare free-list when any free spot is equally good; use the heap the moment "closest available spot" is a real product requirement.

3. Stack Overflow — the single writer still needs an atomic increment

Mechanism: routing every reputation change through one ReputationService class fixes where the logic lives, but it does not by itself fix concurrent writes to the same member's score — the base page's applyDelta does this.reputation = Math.max(1, this.reputation + delta), which is a read, a compute, and a write as three separate steps. Two threads racing through those three steps on the same Member can both read the same starting value, and whichever writes last silently erases the other's change — a classic lost update, the same shape of bug the Movie Ticket Booking page already fixed for seat availability.

Traced: two simultaneous votes on the same answer

Dev's answer sits at reputation 69. An upvote (+10) and a downvote (−2) land on it in the same instant, both routed through the unsynchronized applyDelta:

tThread T1 (upvote, +10)Thread T2 (downvote, −2)reputation field
t0——69
t1reads reputation = 69—69
t2—reads reputation = 6969
t3computes 69+10=79, writes 79—79
t4—computes 69−2=67, writes 6767

The correct final value is 69 + 10 - 2 = 77; the actual result is 67 — T1's +10 vanished entirely, overwritten by a write that started from a value that was already stale.

Two correct fixes

Fix 1 (single JVM/process): guard the read-modify-write with a lock. Cheap and correct as long as there is exactly one shared Member object for this user in one process:

// FIX: was unsynchronized. Serializes the read-modify-write per Member instance.
public synchronized void applyDelta(int delta) {
    this.reputation = Math.max(1, this.reputation + delta);
}

Fix 2 (durable and cross-process — the real fix at scale): push the whole read-modify-write into one atomic database statement. A synchronized method is invisible to a second app-server process; once you run more than one instance (the normal case), the lock must move to the one thing every instance shares — the database row.

-- One atomic statement: the engine holds the row's write lock for its own duration,
-- so two concurrent UPDATEs to the same row serialize inside the database itself.
UPDATE member
SET    reputation = GREATEST(1, reputation + :delta)
WHERE  id = :memberId;

Go (same fix, one round trip, no read-then-write in application code):

_, err := db.Exec(
    `UPDATE member SET reputation = GREATEST(1, reputation + $1) WHERE id = $2`,
    delta, memberID)

4. Booking idempotency — the double-click and the timed-out retry

Mechanism: a double-click or a client retry after a perceived timeout re-sends the same logical "book these seats" request; without a way to recognize "I've already handled this exact request," the server's seat-locking transaction runs twice and books two sets of seats (or fails the second attempt confusingly) for one intent. The fix is the same idempotency-key mechanism covered on this guide's Idempotency & "Exactly-Once Is a Myth" page: the client generates one key per logical booking attempt and sends it on the original request and every retry; the server records "key → result" and, on seeing the key again, returns the stored result instead of re-running the seat-locking transaction.

The detail specific to booking: the key must be generated once, client-side, at the moment the user commits to booking (e.g. when the Book button is pressed and immediately disabled) — not once per HTTP call. A double-click that fires two requests must carry the same key on both, and a client-side retry after a timeout must reuse that same key rather than minting a new one; only then does the idempotency check actually catch the duplicate.

Java

// Wraps the Movie Ticket Booking page's FOR-UPDATE transaction with a dedup layer.
public BookingResult makeBooking(String idempotencyKey, Booking booking) throws SQLException {
    BookingResult existing = idempotencyStore.putIfAbsent(idempotencyKey, BookingResult.PENDING);
    if (existing != null) {
        return existing == BookingResult.PENDING
            ? BookingResult.PENDING           // first attempt still in flight
            : existing;                       // already decided -- never redo the seat lock
    }
    BookingResult result = doMakeBooking(booking);  // the FOR UPDATE transaction
    idempotencyStore.put(idempotencyKey, result);
    return result;
}

Go

// sync.Map's LoadOrStore is the atomic putIfAbsent equivalent.
func makeBooking(idempotencyKey string, booking Booking) BookingResult {
    if existing, loaded := idempotencyStore.LoadOrStore(idempotencyKey, Pending); loaded {
        return existing.(BookingResult) // in flight, or already decided
    }
    result := doMakeBooking(booking) // the FOR UPDATE transaction
    idempotencyStore.Store(idempotencyKey, result)
    return result
}

In production the dedup table is a durable store keyed by (user_id, idempotency_key) with a unique constraint — not the in-memory map above — because a plain process-local map is invisible to a second app-server instance and disappears on restart, which reopens exactly the race the key was meant to close.

5. Seat-hold TTL — the payment-window race

Mechanism: the moment a customer selects seat 14C, the seat moves from AVAILABLE to a HELD state stamped with a held_until expiry; if payment succeeds before that timestamp the hold becomes CONFIRMED, and if it doesn't — the customer abandons the tab, the payment gateway hangs, anything — a background reaper (or a lazy check on next read) flips the seat back to AVAILABLE once held_until passes, so a single distracted customer can never lock a seat forever.

Traced timeline: the abandoned checkout

tEventSeat state
t=0:00Customer selects seat 14C; hold created, TTL = 10 minHELD, held_until = 0:10
t=0:02Customer reaches payment screen, then walks awayHELD
t=0:10TTL expires; reaper releases the rowAVAILABLE
t=0:12A different customer selects and confirms 14CCONFIRMED (new customer)
t=0:14Original customer's browser finally submits the stale paymentconfirm re-checks status='HELD' AND held_until>now() → 0 rows → rejected, not double-booked

The event at t=0:14 is the load-bearing detail: a successful payment does not by itself mean CONFIRM. The confirm write must re-verify the hold is still alive inside the same transaction that flips the state — if it only checked validity once, back when the payment screen loaded, this exact interleaving would silently confirm a seat that had already been reassigned.

State machine: AVAILABLE to HELD on seat selection with a TTL, HELD to CONFIRMED on payment before expiry, HELD back to AVAILABLE on TTL expiry or explicit cancel
State machine: AVAILABLE to HELD on seat selection with a TTL, HELD to CONFIRMED on payment before expiry, HELD back to AVAILABLE on TTL expiry or explicit cancel
-- Confirm must re-verify the hold is still alive INSIDE the same transaction that flips state.
UPDATE reservation
SET    status = 'CONFIRMED'
WHERE  id = :reservationId
  AND  status = 'HELD'
  AND  held_until > now();          -- fails closed if the reaper already released it
-- application checks affected-row count == 1; 0 rows => "your hold expired, seat released"

6. Blackjack — does the dealer hit or stand on soft 17?

Mechanism: the base Blackjack page's dealer rule — shouldHit(Hand h) { return h.resolveScore() <= 16; } — silently hard-codes stand on all 17s (S17), because resolveScore() collapses a hand down to one number and never distinguishes a soft 17 (A+6, the Ace counted as 11) from a hard 17 (10+7). Real casinos vary on this exact rule — it is the single most-asked Blackjack follow-up — so the correct model treats it as a configurable table rule, not a fixed comparison, and needs a way to detect whether a specific 17 is soft.

Detecting soft 17: recompute the hand's total treating every Ace as 1 ("hard total"); if the hand contains an Ace and hardTotal + 10 equals the resolved score, that score was reached by counting one Ace as 11 — it is soft.

Java

public enum DealerRule { H17, S17 } // hit soft 17, or stand on all 17s

public class Hand {
    // ... existing fields/methods (getCards, resolveScore) unchanged ...

    /** True if the resolved 17 was reached using an Ace counted as 11. */
    public boolean isSoft17() {
        if (resolveScore() != 17) return false;
        int hardTotal = 0;                             // every Ace counted as 1
        boolean hasAce = false;
        for (BlackjackCard c : getCards()) {
            hardTotal += c.getGameValue();
            hasAce = hasAce || c.isAce();
        }
        return hasAce && hardTotal + 10 == 17;          // e.g. A+6: hard=7, 7+10=17 -> soft
    }
}

public class Dealer extends BasePlayer {
    private final DealerRule rule;
    public Dealer(DealerRule rule) { this.rule = rule; }

    public boolean shouldHit(Hand h) {
        int score = h.resolveScore();
        if (score == 0)  return false;                  // already bust
        if (score <= 16) return true;
        if (score == 17) return rule == DealerRule.H17 && h.isSoft17();
        return false;                                    // 18-21: stand
    }
}

Go

type DealerRule int

const (
    S17 DealerRule = iota // stand on all 17s (soft and hard)
    H17                   // hit on soft 17
)

// True if the resolved 17 was reached using an Ace counted as 11.
func (h *Hand) IsSoft17() bool {
    if h.ResolveScore() != 17 {
        return false
    }
    hardTotal, hasAce := 0, false
    for _, c := range h.Cards {
        hardTotal += c.GameValue() // every Ace counted as 1
        hasAce = hasAce || c.IsAce()
    }
    return hasAce && hardTotal+10 == 17 // e.g. A+6: hard=7, 7+10=17 -> soft
}

func (d *Dealer) ShouldHit(h *Hand) bool {
    score := h.ResolveScore()
    switch {
    case score == 0:
        return false // already bust
    case score <= 16:
        return true
    case score == 17:
        return d.Rule == H17 && h.IsSoft17()
    default:
        return false // 18-21: stand
    }
}

Why it matters: H17 raises the house edge by roughly 0.2 percentage points versus S17 — small per hand, material over a casino's volume, which is why it is posted on the table placard. A candidate whose shouldHit only ever checks resolveScore() <= 16 has silently chosen S17 without realizing there was a choice to make; naming the rule and making it a constructor parameter is what turns an implicit assumption into a deliberate, testable decision.

7. Judgment layer

App-level check vs. a DB-native exclusion constraint

Mechanism: the Movie Ticket Booking page closes the double-booking race with an application-level transaction (SELECT ... FOR UPDATE). PostgreSQL can enforce the same non-overlap guarantee natively: model the reservation as a range (a time interval, or a discrete numeric range) tied to a resource id, and declare an exclusion constraint over a GiST index — the database then physically refuses any insert or update whose range overlaps an existing one for the same resource, regardless of which application code path wrote it.

CREATE EXTENSION IF NOT EXISTS btree_gist;

CREATE TABLE room_booking (
    id      bigserial PRIMARY KEY,
    room_id int NOT NULL,
    during  tstzrange NOT NULL,
    EXCLUDE USING gist (room_id WITH =, during WITH &&)
);

-- This INSERT is rejected by the DATABASE ITSELF if it overlaps an existing
-- booking for the same room_id -- no application check required, and no way
-- for a second microservice or an admin script to forget the guard.
INSERT INTO room_booking (room_id, during)
VALUES (12, '[2026-07-10 14:00, 2026-07-10 15:00)');

This fits a continuous resource-plus-time-interval shape (meeting rooms, courts, equipment, appointment slots) more naturally than the Movie Ticket Booking page's discrete ShowSeat rows, since a range type is exactly what a room-and-timespan booking already is.

ApproachWhat you gainWhat it costs
App-level transaction (SELECT ... FOR UPDATE / conditional UPDATE)Works for any resource shape, not just ranges; portable across database engines.Must be remembered and written correctly in every code path that can write a reservation — a new admin tool, bulk-import script, or second service that skips the check silently reopens the race.
DB exclusion constraint (range + GiST)Enforced by the database on every writer, forever — physically impossible to forget; the engine does the overlap math, not your code.PostgreSQL-specific (range types + GiST); doesn't help once the table is sharded across databases; a violation surfaces as a raw constraint error your application must translate into a friendly message.

Decision: the app-level transaction is the portable default; add the exclusion constraint as a second, defense-in-depth layer specifically when the resource is naturally a time range and you don't fully trust every future writer (multiple services, admin tools, one-off migrations) to remember the check — belt-and-suspenders, not either-or.

Visitor pattern vs. streaming folds — computing many stats over an immutable structure

Both answer "I need five different reports over the same data" without editing the underlying model for each new report — but they fit different data shapes.

Concretely, for Stack Overflow: "average reputation gained per day across all members" is a fold over the flat vote log — reach for a stream reduction. "Render this post tree as HTML, then as a moderation-report JSON, then as a plaintext export" is Visitor territory — a stable Question/Answer/Comment hierarchy with growing output formats. Using Visitor on a flat vote log adds indirection for no benefit; using a fold across a heterogeneous class hierarchy forces an awkward common interface that a real Visitor already provides for free.

Pitfalls

Takeaways

Related pages

🤖 Don't fully get this? Learn it with Claude

Stuck on OO Design Problems — Arming the Senior Follow-ups (Deep Dive)? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **OO Design Problems — Arming the Senior Follow-ups (Deep Dive)** (OO & Low-Level Design) and want to truly understand it. Explain OO Design Problems — Arming the Senior Follow-ups (Deep Dive) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **OO Design Problems — Arming the Senior Follow-ups (Deep Dive)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **OO Design Problems — Arming the Senior Follow-ups (Deep Dive)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **OO Design Problems — Arming the Senior Follow-ups (Deep Dive)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Design a Parking Lot — LLD Walkthr