Study Library
31 min read
Data Structures & Algorithms•6,771 words

Staff+ Practical Coding and Object-Oriented Design (Java + Kotlin + Spring)

What this is: the coding round for senior/staff backend engineers is rarely a Two-Sum puzzle anymore. It is "model this in code — cleanly, extensibly, correctly under concurrency, in 45 minutes." Design a cache, a rate limiter, a store, an autocomplete, a scheduler; then absorb the twists — "now make it thread-safe," "now add TTL," "now make it distributed." This guide fully works the canonical design-a-data-structure problems in Kotlin and Java, each with its evolution, and teaches the interface-first method and tradeoff-talk that is the actual signal. Every non-trivial snippet here was compiled and tested before it went in.

Series map: 00 playbook · 01 two-pointers & sliding window · 02 binary search, stacks & intervals · 03 trees & graphs · 04 recursion & backtracking · 05 dynamic programming · 06 Staff+ practical coding & OOD (this file). Companion (separate track): data-structures-java-kotlin-study-guide.md — which collection to reach for, HashMap/ConcurrentHashMap internals, boxing/cache/GC, the equals/hashCode/Comparable contract. This guide uses heaps, tries, deques, and concurrent maps as tools, points there for their internals, and spends its own words on the design. For distributed locks, fencing tokens, and lease semantics it points to your concurrency & locking guides.

The mental model#

At Staff+, the coding round stops being an algorithm quiz and becomes a low-level design exercise: build something real, with a clean interface, the right data structures underneath, correctness under concurrency, and tests — while narrating the tradeoffs. The algorithm is table stakes. The modeling, the tradeoff talk, and how gracefully you absorb the follow-up twists are the signal. The panel is answering one question: would I want to maintain this person's code, and put them on the pager?.

Three consequences everything below derives from:

  1. The interface is the deliverable, not the algorithm. A junior starts typing a HashMap. A senior first writes interface Cache<K, V> { V get(K k); void put(K k, V v); } and names the semantics — is get mutating (LRU touch)? does put overwrite? is it bounded? — before implementing anything behind it. The method signatures are where you win or lose the round, because every follow-up ("add TTL," "make it thread-safe") is a change behind a stable interface if you got the interface right, and a rewrite if you didn't.

  2. You are being graded on the evolution, not the first version. These problems are deliberately multi-part. The interviewer has "now make it ___" in their pocket before you start. The candidates who score well leave seams for the announced-but-unstated next step — an EvictionPolicy interface so LRU→LFU is a swap, an injected Clock so TTL is testable — without gold-plating for twists that never come. Designing for the likely next requirement is senior; building a plugin framework for a 45-minute cache is not.

  3. Correctness under concurrency is the most common twist, and the most common failure. A @Service singleton in Spring is shared across every request thread; a mutable HashMap field in it is a data race, full stop. "When two threads call this at once…" is the question you should raise before they ask it. Naming the race and the fix (an atomic map operation, a lock, immutability, or "this belongs in Redis, not process memory") is where seniors separate from mids.

The rest of this guide is that model instantiated across the problems that actually get asked.

1. What the Staff+ practical round actually is#

The 2025-26 loop shrinks pure-algorithm rounds as level rises (a commonly cited synthesis: senior ≈ 20% coding / 50% design / 30% behavioral; staff+ mostly design + leadership with coding as a sanity check), but the coding that remains tilts hard toward "practical" prompts — especially at infra companies (Snowflake, databases, platform teams). The forms you will actually meet:

FormWhat it looks likeWhat they're really testing
Design-a-data-structure"Implement an LRU cache / rate limiter / min-stack / hit counter with this API."Data-structure choice, clean invariants, O(1) claims you can defend.
Evolving multi-partThe above, then "now make it thread-safe," "now add TTL," "now make it distributed."Whether your first design absorbs change or fights it.
"Simulate the system""Write a class that processes a stream of events / a mini pub-sub / a scheduler."Modeling a real subsystem in code, state management, back-pressure.
Low-level / OOD"Model a parking lot / vending machine / deck of cards / elevator."Interfaces, composition, pragmatic SOLID, enums/state.
Parse / evaluate"Tokenize and evaluate an expression / mini query / config."Stacks, state machines, precedence, edge cases.
Debug / extend existing codeGiven a class, fix the concurrency bug or add a feature.Reading code, minimal-diff changes, spotting races.
Take-home / pairRare at FAANG/Snowflake; common at Stripe/startups. Open-ended, realistic.Production-quality code, tests, README, judgment.

The through-line: less LeetCode-hard, more "build a correct, clean, extensible thing under time pressure." Complete, bug-free, edge-case-clean implementations are expected — a partial clever sketch reads as a miss. Snowflake specifically is reported to lean on concurrency/thread-safety, "simulate the system" coding (crawler/BFS, dependency ordering, stream processing, stack parsing), and to probe language internals; treat that as emphasis, not spec (see guide 00).

Interview line: "Before I code, let me pin the interface and its semantics, pick data structures for the access pattern, and I'll assume you'll want thread-safety and maybe TTL later, so I'll design so those are additive." Saying this in the first two minutes reframes you from coder to designer.

2. The approach — interface-first, then evolve#

One repeatable sequence, run out loud every time:

  1. Clarify the operations and their semantics. Not "what's an LRU" — "get on a miss returns null or throws? does get count as a use for eviction? is capacity fixed at construction? single-threaded to start?" The answers change the data structure.
  2. Nail the API first — signatures + contract. Write the interface before the implementation. This is the single highest-leverage move: it makes the twists additive and gives the interviewer something to react to early.
  3. Choose data structures deliberately, narrating why. "O(1) get and O(1) eviction → hash map for lookup + a doubly-linked list for recency order; the map holds node references so I can splice in O(1)." (Cross-reference the companion guide for why each structure has the complexity you're claiming.)
  4. Code incrementally behind the interface. Get the single-threaded version correct and tested first. Never try to write the thread-safe, TTL'd, distributed version in one shot — you'll produce a buggy mess and narrate nothing.
  5. Test as you go; keep it testable by construction. Inject a Clock instead of calling System.currentTimeMillis(), so time-based logic (TTL, rate limits) is deterministic. State invariants ("size never exceeds capacity") and check them.
  6. Then take the twists, each as a small delta: concurrency, scale, persistence — naming the tradeoff each time.

The design defaults that make step 4 clean: program to interfaces, prefer composition over inheritance, inject dependencies (clock, policy, backing store) rather than newing them inside, and apply SOLID pragmatically — enough structure to absorb the announced twist, not a cathedral (§10).

Here is step 2 for a cache — the interface and a policy seam, before any implementation:

kotlin
// Kotlin — the API is the design. Semantics live in the doc comments. interface Cache<K : Any, V : Any> { operator fun get(key: K): V? // null on miss; may count as a "use" operator fun set(key: K, value: V) // insert or overwrite; may evict fun remove(key: K): V? val size: Int // invariant: size <= capacity, always } // The seam for the announced twist (LRU -> LFU is a policy swap, not a rewrite). interface EvictionPolicy<K> { fun recordAccess(key: K) // called on get/put fun add(key: K) fun evictCandidate(): K // which key to drop when full fun remove(key: K) }
java
// Java — same shape. Interfaces first, implementations later. interface Cache<K, V> { V get(K key); // null on miss; may count as a "use" void put(K key, V value); // insert or overwrite; may evict V remove(K key); int size(); // invariant: size() <= capacity, always } interface EvictionPolicy<K> { void recordAccess(K key); void add(K key); K evictCandidate(); void remove(K key); }

You do not always need the EvictionPolicy seam — for a plain "implement an LRU" with no hint of LFU, it is gold-plating (§10). Introduce it when the interviewer signals the swap is coming, or offer it verbally: "if you later want LFU, I'd factor eviction behind an interface — want me to?" That single sentence demonstrates extensibility thinking without over-building.

3. Cache — LRU from scratch → LinkedHashMap → thread-safe → TTL, and LFU#

The most-asked practical problem, period. Master its full evolution and you have a template for the whole genre.

Recognition cue: "bounded cache," "evict least-recently-used," "O(1) get and put," "most-recently-used at the front." Any capacity-bounded store with a recency or frequency eviction rule.

3.1 LRU from scratch — HashMap + doubly-linked list#

The canonical answer, and the one interviewers want to see you build, not import. The insight: you need O(1) lookup (hash map) and O(1) reordering by recency (doubly-linked list). A DLL gives O(1) splice-to-front and O(1) removal if you already hold the node — so the map stores key → node, not key → value. Sentinel head/tail nodes remove all the null-checking from the edge cases.

kotlin
// Kotlin — HashMap + doubly-linked list. O(1) get/put, size never exceeds cap. class LruCache<K : Any, V : Any>(private val capacity: Int) { private class Node<K, V>(val key: K?, var value: V?) { lateinit var prev: Node<K, V> lateinit var next: Node<K, V> } private val map = HashMap<K, Node<K, V>>() private val head = Node<K, V>(null, null) // MRU sentinel private val tail = Node<K, V>(null, null) // LRU sentinel init { head.next = tail; tail.prev = head } private fun unlink(n: Node<K, V>) { n.prev.next = n.next; n.next.prev = n.prev } private fun pushFront(n: Node<K, V>) { n.next = head.next; n.prev = head head.next.prev = n; head.next = n } fun get(key: K): V? { val n = map[key] ?: return null unlink(n); pushFront(n) // touch: move to MRU return n.value } fun put(key: K, value: V) { map[key]?.let { it.value = value; unlink(it); pushFront(it); return } if (map.size == capacity) { val lru = tail.prev // evict from the LRU end unlink(lru); map.remove(lru.key!!) // lru.key is non-null for real nodes } val fresh = Node(key, value) pushFront(fresh); map[key] = fresh } val size: Int get() = map.size }
java
// Java — same structure, same invariants. class LruCache<K, V> { private static final class Node<K, V> { K key; V value; Node<K, V> prev, next; Node(K k, V v){ key=k; value=v; } } private final int capacity; private final Map<K, Node<K, V>> map = new HashMap<>(); private final Node<K, V> head = new Node<>(null, null); // MRU sentinel private final Node<K, V> tail = new Node<>(null, null); // LRU sentinel LruCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; } private void unlink(Node<K, V> n) { n.prev.next = n.next; n.next.prev = n.prev; } private void pushFront(Node<K, V> n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; } V get(K key) { Node<K, V> n = map.get(key); if (n == null) return null; unlink(n); pushFront(n); // touch: move to MRU return n.value; } void put(K key, V value) { Node<K, V> n = map.get(key); if (n != null) { n.value = value; unlink(n); pushFront(n); return; } if (map.size() == capacity) { Node<K, V> lru = tail.prev; // evict from the LRU end unlink(lru); map.remove(lru.key); } Node<K, V> fresh = new Node<>(key, value); pushFront(fresh); map.put(key, fresh); } int size() { return map.size(); } }
  • Complexity: get/put O(1) time; O(capacity) space.
  • Traps: (1) storing key → value instead of key → node — then removal is O(n) to find the node. (2) Forgetting to remove the evicted key from the map (you unlink the node but the map still points at it → memory leak + wrong size). (3) No sentinels → a thicket of if (head == null) branches and off-by-one bugs at the ends. (4) On put of an existing key, forgetting to touch it (move to front) — a subtle correctness bug the interviewer will test.

3.2 The five-line version — LinkedHashMap in access order#

Once you've shown you can build it, say: "in production I wouldn't hand-roll this — LinkedHashMap in access-order mode is exactly an LRU." It's a HashMap with a built-in linked list threading the entries; accessOrder = true moves an entry to the tail on every get, and removeEldestEntry is the eviction hook. (Internals: companion guide §3.2.)

kotlin
// Kotlin — LRU in five lines via LinkedHashMap access-order. fun <K, V> lruCache(capacity: Int): MutableMap<K, V> = object : LinkedHashMap<K, V>(16, 0.75f, /* accessOrder = */ true) { override fun removeEldestEntry(eldest: Map.Entry<K, V>) = size > capacity }
java
// Java — same, as a subclass. class LinkedLru<K, V> extends LinkedHashMap<K, V> { private final int capacity; LinkedLru(int capacity) { super(16, 0.75f, /* accessOrder = */ true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > capacity; } }

Knowing both — the from-scratch DLL and the stdlib shortcut — and when to use each is the senior signal. Build it to prove you can; reach for LinkedHashMap (or Caffeine, below) because you ship.

3.3 "Now make it thread-safe"#

The first twist, every time. LinkedHashMap is not thread-safe, and — the sharp part — even a read (get) mutates it in access-order mode (it moves the touched entry to the tail). So you cannot use a ReadWriteLock and let readers share a read lock; a "read" is a structural write. The correct simple answer is one exclusive lock around every operation:

kotlin
// Kotlin — one lock; note get() mutates access order, so it CANNOT take a shared read lock. class ConcurrentLru<K, V>(capacity: Int) { private val lock = ReentrantLock() private val map = object : LinkedHashMap<K, V>(16, 0.75f, true) { override fun removeEldestEntry(eldest: Map.Entry<K, V>) = size > capacity } fun get(key: K): V? = lock.withLock { map[key] } fun put(key: K, value: V) = lock.withLock { map[key] = value } val size: Int get() = lock.withLock { map.size } }
java
// Java — same. ReentrantLock (not synchronized) so you could add tryLock/timeouts later. class ConcurrentLru<K, V> { private final ReentrantLock lock = new ReentrantLock(); private final LinkedHashMap<K, V> map; ConcurrentLru(int capacity) { map = new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > capacity; } }; } V get(K key) { lock.lock(); try { return map.get(key); } finally { lock.unlock(); } } void put(K key, V v) { lock.lock(); try { map.put(key, v); } finally { lock.unlock(); } } int size() { lock.lock(); try { return map.size(); } finally { lock.unlock(); } } }
  • Say the tradeoff: one global lock serializes all access — fine for moderate throughput, a bottleneck at high QPS. The next lever is lock striping (partition keys across N independent LRU shards, lock per shard — the pre-Java-8 ConcurrentHashMap trick), or, honestly, "I'd stop hand-rolling and use Caffeine — Window-TinyLFU, concurrent, near-optimal hit rate." Naming Caffeine here reads as "has shipped a cache." (This stress-tests clean: 16 threads × 50k ops, size never exceeds capacity.)
  • Trap: reaching for ReadWriteLock on an access-order LinkedHashMap. Two readers under a shared read lock both mutate the recency list → corruption. Call this out explicitly; it's a favorite gotcha.

3.4 "Now add TTL"#

Give each entry an expiry and treat an expired entry as absent. Two expiry strategies, and you want both: lazy (check on read, evict if stale — cheap, but dead entries linger and hold memory) and active (a background sweep — reclaims memory but costs CPU). Real systems (Redis) do both. Crucially, inject the clock so this is testable (§12).

kotlin
// Kotlin — TTL entry; lazy expiry on read + an active sweep. Clock is injected. class TtlCache<K : Any, V : Any>(private val clock: () -> Long) { private data class Entry<V>(val value: V, val expiresAt: Long) private val map = HashMap<K, Entry<V>>() fun put(key: K, value: V, ttlMs: Long) { map[key] = Entry(value, clock() + ttlMs) } fun get(key: K): V? { val e = map[key] ?: return null if (clock() >= e.expiresAt) { map.remove(key); return null } // lazy expiry return e.value } fun sweep(): Int { // active expiry val now = clock() val it = map.entries.iterator() var removed = 0 while (it.hasNext()) if (now >= it.next().value.expiresAt) { it.remove(); removed++ } return removed } }
java
// Java — record for the entry; identical strategy. class TtlCache<K, V> { private record Entry<V>(V value, long expiresAt) {} private final Map<K, Entry<V>> map = new HashMap<>(); private final LongSupplier clock; // java.util.function.LongSupplier TtlCache(LongSupplier clock) { this.clock = clock; } void put(K key, V value, long ttlMs) { map.put(key, new Entry<>(value, clock.getAsLong() + ttlMs)); } V get(K key) { Entry<V> e = map.get(key); if (e == null) return null; if (clock.getAsLong() >= e.expiresAt()) { map.remove(key); return null; } // lazy return e.value(); } int sweep() { // active: run from a scheduled task long now = clock.getAsLong(); int removed = 0; for (var it = map.entrySet().iterator(); it.hasNext();) if (now >= it.next().getValue().expiresAt()) { it.remove(); removed++; } return removed; } }
  • Interview beat: "Lazy alone leaks memory for keys never read again; active alone wastes CPU scanning live keys. Redis does randomized active sampling plus lazy — I'd run sweep from a scheduled executor, or use a PriorityQueue<(expiry, key)> to pop only entries that are actually due instead of scanning all of them." The min-heap-by-expiry variant is the §8 scheduler pattern applied to eviction.
  • Combining with LRU: in production this is size-bounded LRU + TTL together — exactly what Caffeine gives you (maximumSize + expireAfterWrite). Say so.

3.5 LFU — eviction by frequency, with buckets#

The other cache twist: evict the least-frequently-used, tie-broken by least-recently-used. The trick that makes it O(1): a freq → ordered-set-of-keys structure plus a minFreq pointer. On access, move the key from its freq bucket to freq+1; on eviction, drop the LRU key from the minFreq bucket. A LinkedHashSet per bucket gives O(1) add/remove and LRU order within a frequency.

java
// Java — LFU in O(1) get/put via frequency buckets + a minFreq pointer. class LfuCache { private final int capacity; private int minFreq = 0; private final Map<Integer, int[]> entries = new HashMap<>(); // key -> {value, freq} private final Map<Integer, LinkedHashSet<Integer>> buckets = new HashMap<>(); // freq -> keys (LRU order) LfuCache(int capacity) { this.capacity = capacity; } int get(int key) { int[] e = entries.get(key); if (e == null) return -1; touch(key, e); return e[0]; } void put(int key, int value) { if (capacity == 0) return; int[] e = entries.get(key); if (e != null) { e[0] = value; touch(key, e); return; } if (entries.size() == capacity) { // evict LFU (LRU tie-break) int victim = buckets.get(minFreq).iterator().next(); removeFromBucket(minFreq, victim); entries.remove(victim); } entries.put(key, new int[]{value, 1}); buckets.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key); minFreq = 1; // a fresh key resets minFreq } private void touch(int key, int[] e) { int f = e[1]++; removeFromBucket(f, key); if (buckets.getOrDefault(f, EMPTY).isEmpty() && minFreq == f) minFreq++; buckets.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key); } private void removeFromBucket(int f, int key) { LinkedHashSet<Integer> b = buckets.get(f); b.remove(key); if (b.isEmpty()) buckets.remove(f); } private static final LinkedHashSet<Integer> EMPTY = new LinkedHashSet<>(); }

The Kotlin version is structurally identical — HashMap<Int, IntArray> for {value, freq} and HashMap<Int, LinkedHashSet<Int>> for the buckets; the only idiom change is getOrPut(f + 1) { LinkedHashSet() } in place of computeIfAbsent. Complexity: O(1) get/put; O(capacity) space. Trap: resetting minFreq = 1 on every insert (correct) but forgetting to advance it when the last key leaves the minFreq bucket on a touch — then eviction reads an empty bucket and NPEs. This is the whole reason LFU is a "hard" tag: the minFreq bookkeeping.

This maps to your world: your OCPI session read models are effectively per-version caches over an append pipeline; a maximumSize + expireAfterWrite Caffeine cache with a loader is the shape, and the "lazy vs active expiry" conversation is exactly the one you have about materialized read models going stale.

4. Rate limiting — four in-process algorithms, then distributed#

The second-most-asked practical problem, and a perfect evolving prompt: start in-process, then "now it's 20 pods behind a load balancer." Know all four algorithms cold and when each is right.

Recognition cue: "limit to N requests per window," "throttle," "X per second per user," "smooth out bursts," "429 when over quota."

AlgorithmStateBurst behaviorMemoryVerdict
Fixed windowone counter + window startAllows 2× at the boundary (2N across a window edge)O(1)Simplest; boundary burst is the flaw.
Sliding window logtimestamp per requestExactO(N) per keyPrecise but memory-heavy under load.
Sliding window countertwo countersApproximate, no boundary spikeO(1)Best cost/accuracy — the common production pick.
Token buckettokens + last-refill timeAllows a controlled burst up to bucket sizeO(1)Great when a bounded burst is desirable (APIs).

4.1 Token bucket — the default#

A bucket holds up to capacity tokens, refilled at a steady rate; each request spends one. Refill is computed lazily from elapsed time on each call — no background thread. It permits a burst up to capacity then throttles to the refill rate: usually what you want for an API.

kotlin
// Kotlin — token bucket. Lazy refill from elapsed time; inject the clock via the `now` arg. class TokenBucket(private val capacity: Double, refillPerSecond: Double) { private val refillPerMs = refillPerSecond / 1000.0 private var tokens = capacity private var lastMs = Long.MIN_VALUE fun allow(now: Long, cost: Double = 1.0): Boolean { if (lastMs == Long.MIN_VALUE) lastMs = now tokens = minOf(capacity, tokens + (now - lastMs) * refillPerMs) // refill for elapsed time lastMs = now if (tokens >= cost) { tokens -= cost; return true } return false } }
java
// Java — same. class TokenBucket { private final double capacity, refillPerMs; private double tokens; private long lastMs = Long.MIN_VALUE; TokenBucket(double capacity, double refillPerSecond) { this.capacity = capacity; this.refillPerMs = refillPerSecond / 1000.0; this.tokens = capacity; } boolean allow(long now, double cost) { if (lastMs == Long.MIN_VALUE) lastMs = now; tokens = Math.min(capacity, tokens + (now - lastMs) * refillPerMs); // refill for elapsed time lastMs = now; if (tokens >= cost) { tokens -= cost; return true; } return false; } }

Complexity: O(1) time and space per key. Trap: refilling on a timer thread instead of lazily on read — wastes a thread per bucket and races. Compute refill from now - lastMs.

4.2 Sliding window counter — the production sweet spot#

Fixed window's flaw is the boundary: N requests at 0.999s and N more at 1.001s = 2N in ~2ms. The sliding window counter fixes it cheaply by weighting the previous window's count by how much of it still overlaps the rolling window — O(1) state, no boundary spike.

kotlin
// Kotlin — sliding window counter. estimate = prev*overlap + current. class SlidingWindowCounter(private val windowMs: Long, private val limit: Int) { private var curStart = Long.MIN_VALUE private var curCount = 0L private var prevCount = 0L fun allow(now: Long): Boolean { val ws = now - (now % windowMs) // aligned window start if (ws != curStart) { prevCount = if (ws == curStart + windowMs) curCount else 0L // roll, or reset if we skipped windows curStart = ws; curCount = 0 } val overlap = (windowMs - (now - curStart)).toDouble() / windowMs val estimate = prevCount * overlap + curCount if (estimate + 1 > limit) return false curCount++; return true } }
java
// Java — same weighting. class SlidingWindowCounter { private final long windowMs; private final int limit; private long curStart = Long.MIN_VALUE, curCount = 0, prevCount = 0; SlidingWindowCounter(long windowMs, int limit) { this.windowMs = windowMs; this.limit = limit; } boolean allow(long now) { long ws = now - (now % windowMs); if (ws != curStart) { prevCount = (ws == curStart + windowMs) ? curCount : 0; // roll or reset curStart = ws; curCount = 0; } double overlap = (double) (windowMs - (now - curStart)) / windowMs; double estimate = prevCount * overlap + curCount; if (estimate + 1 > limit) return false; curCount++; return true; } }

Complexity: O(1). Trap: not resetting prevCount to 0 when the clock jumps more than one window (idle key) — you'd carry a stale count forward and under-allow.

4.3 Fixed window and sliding log — know them to reject them#

Show you can state both and their flaws; you rarely ship them. Fixed window is a counter that resets when now / windowMs changes:

java
// Java — fixed window: dead simple, but 2x burst at the boundary. class FixedWindow { private final long windowMs; private final int limit; private long windowStart = -1; private int count; FixedWindow(long windowMs, int limit) { this.windowMs = windowMs; this.limit = limit; } boolean allow(long now) { long ws = now - (now % windowMs); if (ws != windowStart) { windowStart = ws; count = 0; } return count < limit && ++count > 0; } }

Sliding window log keeps a deque of timestamps, evicts those older than the window, and allows if the deque is under the limit — exact, but O(N) memory per key (bad for hot keys). It is the "sliding window" pattern from guide 01 applied to time: while (!log.isEmpty() && log.peekFirst() <= now - windowMs) log.pollFirst(); then if (log.size() < limit) { log.addLast(now); return true; }.

4.4 "Now make it distributed" — the real twist#

The moment there are N pods, a per-process bucket is worthless: each pod enforces the limit independently, so the true limit is N × limit. In-memory state cannot coordinate across machines. The state must move to a shared store, and the read-modify-write must be atomic there. The standard answer is Redis with a Lua script — Redis executes a script atomically (single-threaded), so the "refill, check, decrement" is one indivisible step with no race and one round-trip.

lua
-- token_bucket.lua (KEYS[1] = bucket key; ARGV = capacity, refillPerSec, nowMs, requested) local capacity = tonumber(ARGV[1]) local refill = tonumber(ARGV[2]) local now = tonumber(ARGV[3]) local requested = tonumber(ARGV[4]) local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts') local tokens = tonumber(state[1]) local ts = tonumber(state[2]) if tokens == nil then tokens = capacity; ts = now end local elapsed = math.max(0, now - ts) / 1000.0 tokens = math.min(capacity, tokens + elapsed * refill) -- lazy refill, same math as in-process local allowed = 0 if tokens >= requested then tokens = tokens - requested; allowed = 1 end redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now) redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / refill * 1000)) -- reclaim idle keys return allowed
kotlin
// Kotlin + Spring — call the script atomically. StringRedisTemplate + DefaultRedisScript. @Component class DistributedRateLimiter(private val redis: StringRedisTemplate) { private val script = DefaultRedisScript(TOKEN_BUCKET, Long::class.java) fun allow(key: String, capacity: Long, refillPerSec: Double, cost: Long = 1): Boolean { val now = System.currentTimeMillis() val allowed = redis.execute( script, listOf("rl:$key"), capacity.toString(), refillPerSec.toString(), now.toString(), cost.toString(), ) return allowed == 1L } companion object { private const val TOKEN_BUCKET = "..." /* the Lua script text above */ } }
java
// Java + Spring — same call. RedisScript.of(script, Long.class). @Component class DistributedRateLimiter { private final StringRedisTemplate redis; private final RedisScript<Long> script = RedisScript.of(TOKEN_BUCKET, Long.class); DistributedRateLimiter(StringRedisTemplate redis) { this.redis = redis; } boolean allow(String key, long capacity, double refillPerSec, long cost) { long now = System.currentTimeMillis(); Long allowed = redis.execute(script, List.of("rl:" + key), Long.toString(capacity), Double.toString(refillPerSec), Long.toString(now), Long.toString(cost)); return allowed != null && allowed == 1L; } static final String TOKEN_BUCKET = "..."; // the Lua script text }

Why Lua, not GET-then-SET: two round-trips have a gap where two pods both read "1 token left" and both decrement — the classic check-then-act race, now distributed. The script collapses it into one atomic operation. Tradeoffs to name: Redis becomes a dependency on the hot path (latency + a SPOF — mitigate with a local token-bucket fallback that fails-open or fails-closed per your policy); clock skew across pods (pass now from a single source or use Redis TIME); and for extreme scale you shard limiter keys or accept approximate limits. For distributed correctness beyond a single Redis — multiple Redis nodes, fencing — this is a distributed-lock / consensus conversation; see your concurrency & locking guides for Redlock's caveats and lease/fencing-token semantics. Do not claim a single Redis gives you consensus.

This maps to your world: ONS (your Kafka webhook-notification service) already lives in this space — per-client outbound throttling so one tenant's webhook storm doesn't starve others is exactly per-key token-bucket, and it composes with your circuit breaker + bulkhead (limit → break on downstream failure → isolate per tenant). The sliding-window-counter is what you'd reach for on the inbound side.

5. In-memory key-value store with TTL and expiry#

"Design a mini Redis / a SET/GET/EXPIRE store." It's §3.4's TTL logic promoted to a first-class store, and the interviewer probes expiry strategy and concurrency. Interface first, clock injected, ConcurrentHashMap so it's thread-safe from the start (a store is obviously shared).

kotlin
// Kotlin — KV store with TTL. Concurrent by construction; lazy + active expiry. class KvStore(private val clock: () -> Long) { private data class Entry(val value: String, val expiresAt: Long?) // null = no expiry private val map = ConcurrentHashMap<String, Entry>() fun set(key: String, value: String, ttlMs: Long? = null) { map[key] = Entry(value, ttlMs?.let { clock() + it }) } fun get(key: String): String? { val e = map[key] ?: return null if (isExpired(e)) { map.remove(key, e); return null } // lazy; remove(k,v) avoids racing a fresh set return e.value } fun delete(key: String): Boolean = map.remove(key) != null fun sweep() { // active; schedule this val now = clock() map.forEach { (k, e) -> if (e.expiresAt != null && now >= e.expiresAt) map.remove(k, e) } } private fun isExpired(e: Entry) = e.expiresAt != null && clock() >= e.expiresAt }
java
// Java — same. ConcurrentHashMap.remove(key, value) is the CAS-style safe removal. class KvStore { private record Entry(String value, Long expiresAt) {} // null expiresAt = no expiry private final ConcurrentHashMap<String, Entry> map = new ConcurrentHashMap<>(); private final LongSupplier clock; KvStore(LongSupplier clock) { this.clock = clock; } void set(String key, String value, Long ttlMs) { map.put(key, new Entry(value, ttlMs == null ? null : clock.getAsLong() + ttlMs)); } String get(String key) { Entry e = map.get(key); if (e == null) return null; if (isExpired(e)) { map.remove(key, e); return null; } // lazy; value-conditional remove return e.value(); } boolean delete(String key) { return map.remove(key) != null; } void sweep() { // active; from a scheduled task long now = clock.getAsLong(); map.forEach((k, e) -> { if (e.expiresAt() != null && now >= e.expiresAt()) map.remove(k, e); }); } private boolean isExpired(Entry e) { return e.expiresAt() != null && clock.getAsLong() >= e.expiresAt(); } }
  • The key concurrency subtlety: use map.remove(key, expiredEntry) (the value-conditional removal), not map.remove(key). Otherwise a lazy-expiry delete can race a concurrent set and blow away a fresh value that arrived between your read and your remove. This is exactly the check-then-act lesson, and naming it here is a strong signal.
  • Complexity: O(1) set/get/delete; sweep O(n). Trap: unbounded memory — a store with no size cap plus keys that are set without TTL grows forever. Bound it (add LRU eviction, §3) or document that the caller must.

6. Stacks that answer a query in O(1) — min-stack, max-stack, hit counter#

Recognition cue: "a stack that also returns the min/max in O(1)," "count requests in the last 5 minutes," "running extreme with pushes and pops." The trick is always the same: store the auxiliary answer alongside each element so a pop restores the previous answer for free.

6.1 Min-stack#

Push (value, min-so-far) together. getMin is then the top's second field — O(1), and pop needs no recomputation.

kotlin
// Kotlin — min stack. Each frame carries the running min. Uses Kotlin's ArrayDeque as a stack. class MinStack { private data class Frame(val value: Long, val min: Long) private val st = ArrayDeque<Frame>() fun push(x: Long) { st.addLast(Frame(x, if (st.isEmpty()) x else minOf(x, st.last().min))) } fun pop(): Long = st.removeLast().value fun top(): Long = st.last().value fun getMin(): Long = st.last().min fun isEmpty() = st.isEmpty() }
java
// Java — same; ArrayDeque as the stack, a 2-long array per frame (no boxing of the longs). class MinStack { private final Deque<long[]> st = new ArrayDeque<>(); // {value, minSoFar} void push(long x) { long min = st.isEmpty() ? x : Math.min(x, st.peek()[1]); st.push(new long[]{x, min}); } long pop() { return st.pop()[0]; } long top() { return st.peek()[0]; } long getMin() { return st.peek()[1]; } boolean isEmpty() { return st.isEmpty(); } }

Complexity: all O(1); O(n) space. Max-stack is the same with Math.max; a max-stack that also supports popMax() is harder — that needs a TreeMap-ordered structure or a balanced BST, because popMax removes from the middle. Say that distinction out loud; interviewers probe it. Trap: the "space-optimized" single-stack-plus-scalar version breaks on duplicates of the min — you must push a second copy when x == currentMin and pop when equal, which is fiddly and rarely worth it. The paired-frame version is O(1) and bug-resistant; prefer it under time pressure.

6.2 Hit counter — requests in a trailing window#

"How many hits in the last 300 seconds?" Two designs. The simple one: a deque of timestamps, evict from the front while older than the window, answer is deque.size(). It's O(1) amortized but O(hits) memory. The bounded, senior answer: a circular buffer of per-second buckets — fixed O(window) memory regardless of QPS.

java
// Java — hit counter over a trailing window of `window` seconds, O(window) memory. class HitCounter { private final int window; private final int[] times, hits; // times[i] = the second stored in bucket i HitCounter(int window) { this.window = window; times = new int[window]; hits = new int[window]; } void hit(int t) { // t in seconds, monotonic non-decreasing int i = t % window; if (times[i] != t) { times[i] = t; hits[i] = 1; } // bucket belongs to an old second -> reset else hits[i]++; } int getHits(int t) { int total = 0; for (int i = 0; i < window; i++) if (t - times[i] < window) total += hits[i]; return total; } }

The Kotlin version is a line-for-line translation over two IntArrays. Complexity: hit O(1); getHits O(window) (O(1) for a 300-bucket window — constant). Trap: if hits can arrive out of order, or you need arbitrary window sizes, the bucket approach breaks — fall back to the timestamp deque, or bucket by finer granularity. State the assumption (monotonic time) explicitly.

This maps to your world: the trailing-window count is the same shape as bounded-heap streaming top-k over your session-event stream (guide 02/03 for the heap) — a fixed-memory summary over an unbounded stream, which is the only kind of aggregate that survives a data-lake firehose.

7. Autocomplete / typeahead — trie + cached top-k#

"Design search autocomplete / typeahead." The data structure is a trie (prefix tree; internals in the companion guide §5): O(L) to walk a prefix of length L, independent of dictionary size. The twist that makes it interview-worthy is ranking: return the top-k completions by frequency, fast. Naively you'd DFS the whole subtree under the prefix and sort — O(subtree). The senior move: cache the top-k at every node, updated on insert, so a query is O(L) to walk down + O(k) to copy.

Recognition cue: "suggest completions for a prefix," "typeahead," "top N results as the user types," "prefix search ranked by popularity."

kotlin
// Kotlin — trie with a cached top-k list per node. Query = walk to prefix node, return its cache. class Autocomplete(private val k: Int) { private class Node { val children = HashMap<Char, Node>() val top = ArrayList<String>() // cached best-k completions passing through here } private val root = Node() private val freq = HashMap<String, Int>() fun add(word: String, count: Int = 1) { freq[word] = (freq[word] ?: 0) + count var node = root updateTop(node, word) for (c in word) { node = node.children.getOrPut(c) { Node() }; updateTop(node, word) } } private fun updateTop(node: Node, word: String) { node.top.remove(word) var i = 0 while (i < node.top.size && betterOrEqual(node.top[i], word)) i++ // keep sorted: freq desc, then word asc node.top.add(i, word) if (node.top.size > k) node.top.removeAt(node.top.size - 1) } private fun betterOrEqual(a: String, b: String): Boolean { val fa = freq[a]!!; val fb = freq[b]!! return if (fa != fb) fa > fb else a <= b } fun suggest(prefix: String): List<String> { var node = root for (c in prefix) { node = node.children[c] ?: return emptyList() } return node.top.toList() // defensive copy so callers can't mutate the cache } }
java
// Java — same design. class Autocomplete { private static final class Node { Map<Character, Node> children = new HashMap<>(); List<String> top = new ArrayList<>(); // cached best-k passing through here } private final int k; private final Node root = new Node(); private final Map<String, Integer> freq = new HashMap<>(); Autocomplete(int k) { this.k = k; } void add(String word, int count) { freq.merge(word, count, Integer::sum); Node node = root; updateTop(node, word); for (char c : word.toCharArray()) { node = node.children.computeIfAbsent(c, x -> new Node()); updateTop(node, word); } } private void updateTop(Node node, String word) { node.top.remove(word); int i = 0; while (i < node.top.size() && betterOrEqual(node.top.get(i), word)) i++; node.top.add(i, word); if (node.top.size() > k) node.top.remove(node.top.size() - 1); } private boolean betterOrEqual(String a, String b) { int fa = freq.get(a), fb = freq.get(b); return fa != fb ? fa > fb : a.compareTo(b) <= 0; } List<String> suggest(String prefix) { Node node = root; for (char c : prefix.toCharArray()) { node = node.children.get(c); if (node == null) return List.of(); } return new ArrayList<>(node.top); // defensive copy } }
  • Complexity: add O(L·k) (walk each of L nodes, splice into a k-sized list); suggest O(L + k) — independent of dictionary size, which is the whole point. Space O(total characters + nodes·k).
  • Why this works incrementally: frequencies only increase, so when one word moves up, only that word shifts in each ancestor's cached list; the k-cap correctly drops whatever fell to rank k+1. This is the invariant to state.
  • Traps: (1) DFS-and-sort per query — fine for a whiteboard, but say "O(subtree) per keystroke doesn't scale; I'd cache top-k per node." (2) Returning node.top directly — a caller mutates your cache; return a copy. (3) At real scale (millions of terms) the whole trie won't fit on one box — shard by prefix, precompute suggestions offline, and cache hot prefixes; name this as the system-design continuation.

8. Scheduling — delayed executor with a min-heap#

"Design a task scheduler / delayed job runner / timer." The core is a min-heap keyed by execution time: the next task to run is always the root, so peek is O(1) and the worker sleeps exactly until it's due. A tie-breaking sequence number keeps it stable (FIFO among equal times) and prevents PriorityQueue from comparing the payloads.

Recognition cue: "run this after a delay," "schedule at time T," "process jobs in due-time order," "poll for what's ready," "retry after backoff."

kotlin
// Kotlin — delayed scheduler over a min-heap by run time. `due(now)` drains everything ready. class DelayedScheduler { private data class Task(val runAt: Long, val seq: Long, val job: Runnable) private var seq = 0L private val pq = java.util.PriorityQueue<Task>(compareBy({ it.runAt }, { it.seq })) fun schedule(runAt: Long, job: Runnable) { pq.offer(Task(runAt, seq++, job)) } fun due(now: Long): List<Runnable> { val out = ArrayList<Runnable>() while (pq.isNotEmpty() && pq.peek().runAt <= now) out.add(pq.poll().job) return out } fun nextDelay(now: Long): Long = if (pq.isEmpty()) -1 else maxOf(0, pq.peek().runAt - now) }
java
// Java — same. Comparator by (runAt, seq); seq breaks ties and avoids comparing Runnables. class DelayedScheduler { private record Task(long runAt, long seq, Runnable job) {} private long seq = 0; private final PriorityQueue<Task> pq = new PriorityQueue<>( Comparator.comparingLong(Task::runAt).thenComparingLong(Task::seq)); void schedule(long runAt, Runnable job) { pq.offer(new Task(runAt, seq++, job)); } List<Runnable> due(long now) { List<Runnable> out = new ArrayList<>(); while (!pq.isEmpty() && pq.peek().runAt() <= now) out.add(pq.poll().job()); return out; } long nextDelay(long now) { return pq.isEmpty() ? -1 : Math.max(0, pq.peek().runAt() - now); } }
  • Complexity: schedule O(log n), due O(k log n) for k due tasks, peek/nextDelay O(1). Space O(n).
  • "Now make it run itself / thread-safe": the production version is a ScheduledThreadPoolExecutor (a thread pool backed by exactly this delay-ordered queue) or a DelayQueue<Delayed> (a blocking, thread-safe priority queue whose take() blocks until the head is due — no busy-wait). Name these rather than hand-rolling the locking: "I'd hand this heap to a DelayQueue so a worker take()s and blocks precisely until the next task is due."
  • Traps: (1) no tie-breaker → PriorityQueue tries to compare Tasks (or Runnables) and throws ClassCastException, or reorders equal-time tasks nondeterministically. (2) Busy-polling due(now()) in a tight loop instead of sleeping for nextDelay — burns a core. (3) A single long-running job blocks the whole scheduler — run jobs on a separate pool.

This maps to your world: for durable, distributed delays and retries — the saga world — an in-memory heap is the wrong tool: it dies with the process. That's the case for Temporal.io timers (your contract/account sagas) or a DB-backed due_at table polled transactionally. Say the in-memory heap is the single-node teaching version and the durable timer is the production one.

9. Design-a-data-structure grab bag — iterators, pub/sub, calculator#

Three more that recur; each is a "model this API" prompt.

9.1 Iterator design — flatten a nested list#

"Implement an iterator over a nested list of integers" ([1,[2,[3,4]],5] → 1 2 3 4 5). The clean design is a stack of iterators: push the top-level iterator; to advance, peek the top iterator, and if the next element is a list, push its iterator and recurse; if it's an integer, that's your next. This is lazy — it does no work until asked — which matters for large or infinite nestings and is the property to highlight.

Recognition cue: "implement an Iterator / a hasNext/next API," "flatten," "merge k sorted iterators," "peek without consuming," "zigzag between sequences."

kotlin
// Kotlin — nested iterator via a stack of iterators. Lazy: advances only on demand. interface NestedInteger { fun isInteger(): Boolean; fun getInteger(): Int?; fun getList(): List<NestedInteger>? } class NestedIterator(list: List<NestedInteger>) : Iterator<Int> { private val stack = ArrayDeque<Iterator<NestedInteger>>() private var nextInt: Int? = null init { stack.addLast(list.iterator()); advance() } override fun hasNext(): Boolean = nextInt != null override fun next(): Int { val r = nextInt!!; advance(); return r } private fun advance() { nextInt = null while (stack.isNotEmpty()) { val it = stack.last() if (!it.hasNext()) { stack.removeLast(); continue } val ni = it.next() if (ni.isInteger()) { nextInt = ni.getInteger(); return } stack.addLast(ni.getList()!!.iterator()) } } }
java
// Java — same. Implements java.util.Iterator<Integer>. class NestedIterator implements Iterator<Integer> { private final Deque<Iterator<NestedInteger>> stack = new ArrayDeque<>(); private Integer nextInt = null; NestedIterator(List<NestedInteger> list) { stack.push(list.iterator()); advance(); } public boolean hasNext() { return nextInt != null; } public Integer next() { Integer r = nextInt; advance(); return r; } private void advance() { nextInt = null; while (!stack.isEmpty()) { Iterator<NestedInteger> it = stack.peek(); if (!it.hasNext()) { stack.pop(); continue; } NestedInteger ni = it.next(); if (ni.isInteger()) { nextInt = ni.getInteger(); return; } stack.push(ni.getList().iterator()); } } }

Complexity: each element pushed/popped once → O(total elements) across the whole iteration, O(1) amortized per next; O(depth) stack space. Traps: (1) flattening eagerly into a list in the constructor — correct but not lazy, and O(n) memory upfront; the interviewer usually wants the lazy version. (2) empty sub-lists ([[]]) must yield nothing — the while loop that pops exhausted iterators handles this; test it. (3) next() without checking hasNext() — decide the contract (return null, throw NoSuchElementException).

A PeekingIterator (look at next without consuming) is the same one-slot-lookahead idea: cache the peeked element and a has flag. peek() fills the cache; next() drains it if present, else delegates; hasNext() is has || underlying.hasNext(). It's the building block for merge/zigzag iterators (peek both, emit the smaller / alternate), which are the k-way-merge pattern in iterator clothing.

9.2 In-memory pub/sub with offsets (observer + a log)#

"Design a mini message bus / event emitter." The naive version is the observer pattern (subscribers register callbacks, publish invokes them). The version that impresses adds an append-only log + per-subscriber offsets — i.e. Kafka's model in miniature: publishing appends to a log, each subscriber polls from its own offset, and offsets let a subscriber replay or skip. That decouples producer speed from consumer speed and survives a slow consumer.

kotlin
// Kotlin — a topic as an append-only log with per-subscriber offsets (Kafka in miniature). class Topic<T> { private val log = ArrayList<T>() private val offsets = HashMap<String, Int>() private val lock = ReentrantLock() fun publish(msg: T): Int = lock.withLock { log.add(msg); log.size - 1 } // returns offset fun subscribe(id: String, fromEarliest: Boolean = true) = lock.withLock { offsets.putIfAbsent(id, if (fromEarliest) 0 else log.size) // earliest vs latest } fun poll(id: String): List<T> = lock.withLock { val from = offsets.getOrDefault(id, 0) val batch = ArrayList(log.subList(from, log.size)) offsets[id] = log.size batch } fun seek(id: String, offset: Int) = lock.withLock { offsets[id] = offset } // replay / skip }

The Java version is the same with synchronized methods or a ReentrantLock. Complexity: publish O(1) amortized, poll O(new messages). Traps: (1) push-based observer where a slow/throwing subscriber blocks or breaks publish — isolate consumers (catch per-subscriber, or hand off to a queue/executor). (2) unbounded log growth — real systems retain by time/size (compaction, TTL); say you'd bound it. (3) delivery semantics — this is at-least-once if a consumer re-polls after a crash before committing its offset; name the guarantee.

This maps to your world: this is the shape of your OCPI event pipeline and Kafka consumer-group offsets — the "aggregate events into an accumulative session object" is a fold over the polled log, and CQRS read models are just multiple subscribers at independent offsets projecting into per-OCPI-version views.

9.3 Tokenize and evaluate — a basic calculator#

"Evaluate 2*(5+5*2)/3+(6/2+8)." The classic two-stack algorithm (a values stack and an operators stack, a variant of Dijkstra's shunting-yard): scan left to right; push numbers; on an operator, first apply any stacked operators of ≥ precedence (left-associativity), then push it; ( pushes, ) drains back to the matching (. It handles multi-digit numbers, precedence, and parentheses.

java
// Java — calculator with + - * / and parentheses via two stacks. Left-associative. class Calculator { int evaluate(String s) { Deque<Integer> nums = new ArrayDeque<>(); Deque<Character> ops = new ArrayDeque<>(); int i = 0, n = s.length(); while (i < n) { char c = s.charAt(i); if (c == ' ') { i++; continue; } if (Character.isDigit(c)) { // parse a full multi-digit number int num = 0; while (i < n && Character.isDigit(s.charAt(i))) num = num * 10 + (s.charAt(i++) - '0'); nums.push(num); continue; // i already advanced } if (c == '(') { ops.push(c); i++; } else if (c == ')') { while (ops.peek() != '(') apply(nums, ops.pop()); ops.pop(); i++; } else { // operator: drain >= precedence first while (!ops.isEmpty() && ops.peek() != '(' && prec(ops.peek()) >= prec(c)) apply(nums, ops.pop()); ops.push(c); i++; } } while (!ops.isEmpty()) apply(nums, ops.pop()); return nums.pop(); } private int prec(char op) { return (op == '+' || op == '-') ? 1 : 2; } private void apply(Deque<Integer> nums, char op) { int b = nums.pop(), a = nums.pop(); nums.push(switch (op) { case '+' -> a + b; case '-' -> a - b; case '*' -> a * b; default -> a / b; }); } }

The Kotlin version maps directly onto two ArrayDeques and a when expression in apply. Complexity: O(n) time, O(n) stack space. Traps: (1) precedence direction — using > instead of >= makes subtraction/division right-associative (3-2-1 → 4 instead of 0); test that case. (2) multi-digit numbers — consume the whole run, don't process digit by digit. (3) unary minus and whitespace — clarify whether they're in scope and handle explicitly; a leading - or (-3) needs a guard. The "make it extensible" evolution is to tokenize into a List<Token> first, then evaluate — separating lexing from parsing is the clean seam if they add functions or variables.

10. OOD / LLD in code — pragmatic SOLID, patterns, and NOT gold-plating#

The "model a parking lot / vending machine / deck of cards" round tests object modeling, not algorithms. The rubric rewards interfaces at the seams, composition over inheritance, dependency injection, and just enough pattern — and it penalizes over-engineering.

SOLID, applied pragmatically (not religiously):

  • Single responsibility — a class does one thing; the Cache stores, the EvictionPolicy decides what to drop, the Clock tells time. Splitting these is what made §3's TTL and thread-safe twists additive.
  • Open/closed — open for extension via an interface (add an LfuPolicy without touching the cache), closed for modification. This is literally the "design for the announced follow-up" move.
  • Liskov — a subtype must honor the supertype's contract. The trap: Stack extends Vector, Square extends Rectangle. Prefer composition when "is-a" leaks.
  • Interface segregation — small, role-focused interfaces (Readable, Expirable) over one fat one. A client shouldn't depend on methods it doesn't call.
  • Dependency inversion — depend on abstractions; inject the clock, the store, the policy. This is what makes code testable (§12) and swappable.

When a small dose of a pattern earns its place (and only then):

PatternUse it forIn these problems
Strategypluggable algorithm behind an interfaceEvictionPolicy (LRU/LFU), RateLimitAlgorithm (bucket/window)
Factoryconstruction logic that variesCacheFactory.of(policy); hides which concrete cache you get
Observerfan-out notificationspub/sub §9.2, event emitters
Buildermany optional params, immutable resultCache.builder().maxSize(1000).ttl(5.min).build()
Statebehavior varies by modecircuit breaker (closed/open/half-open), your ONS breaker
Adapterbridge to an incompatible APIwrapping Redis behind your Cache interface

The strategy seam in action — LRU→LFU is a one-line swap because eviction lives behind an interface:

kotlin
// Kotlin — the cache depends on the EvictionPolicy abstraction (from §2), not a concrete rule. class PolicyCache<K : Any, V : Any>( private val capacity: Int, private val policy: EvictionPolicy<K>, // injected: LruPolicy or LfuPolicy ) : Cache<K, V> { private val store = HashMap<K, V>() override fun get(key: K): V? = store[key]?.also { policy.recordAccess(key) } override fun set(key: K, value: V) { if (key !in store && store.size == capacity) store.remove(policy.evictCandidate()) store[key] = value; policy.add(key) } override fun remove(key: K): V? = store.remove(key)?.also { policy.remove(key) } override val size: Int get() = store.size }
java
// Java — same. Swap the policy, not the cache. class PolicyCache<K, V> implements Cache<K, V> { private final int capacity; private final EvictionPolicy<K> policy; // injected private final Map<K, V> store = new HashMap<>(); PolicyCache(int capacity, EvictionPolicy<K> policy) { this.capacity = capacity; this.policy = policy; } public V get(K key) { V v = store.get(key); if (v != null) policy.recordAccess(key); return v; } public void put(K key, V value) { if (!store.containsKey(key) && store.size() == capacity) store.remove(policy.evictCandidate()); store.put(key, value); policy.add(key); } public V remove(K key) { V v = store.remove(key); if (v != null) policy.remove(key); return v; } public int size() { return store.size(); } }

The explicit warning: do not gold-plate. A factory for a single concrete type, a strategy interface with one implementation you invented speculatively, an abstract base class "for the future," a builder for a 2-argument constructor — all of these are negative signal under time pressure. They read as someone who reaches for patterns reflexively rather than deriving structure from requirements. The senior move is the minimum structure that (a) makes the current code clean and (b) absorbs the announced next step. If the interviewer hasn't hinted at LFU, ship the plain LRU and say "I'd factor eviction behind an interface if you want LFU too" — offer the seam verbally, build it on request. YAGNI is a Staff+ virtue.

Interview line: "I'll keep the interface small and inject the pieces that vary — the clock and the eviction policy. I'm not going to add a strategy pattern until we actually need a second strategy; right now it'd be structure without payoff."

11. Concurrency inside the coding round — the frequent Staff twist#

"Now make it thread-safe" arrives in most Staff+ practical rounds. You've seen the concrete fixes above (§3.3 lock-guarded LRU, §4/§5 atomic map ops); here is the consolidated toolkit and the decision order. (For the JVM memory model, lock internals, and ConcurrentHashMap's per-bin design, see the companion guide §4 and your concurrency & locking guides.)

The escalation ladder — cheapest correct tool first:

  1. Immutability / confinement — no shared mutable state, no problem. Prefer immutable values (records, data class with val), copy-on-write, or confine state to one thread. The best lock is the one you don't take.
  2. Atomic map operations — for a shared map, use ConcurrentHashMap and its atomic compound methods (computeIfAbsent, compute, merge) instead of check-then-act. This is how §4's per-key rate limiter stays correct under contention without an explicit lock:
kotlin
// Kotlin — atomic per-key rate limit; compute locks the bin, so refill+check+decrement is indivisible. class PerKeyLimiter(private val capacity: Double, refillPerSec: Double) { private data class Bucket(val tokens: Double, val lastMs: Long) private val buckets = ConcurrentHashMap<String, Bucket>() private val refillPerMs = refillPerSec / 1000.0 fun allow(key: String, now: Long): Boolean { var ok = false buckets.compute(key) { _, b -> // atomic per key val tokens = if (b == null) capacity else minOf(capacity, b.tokens + (now - b.lastMs) * refillPerMs) if (tokens >= 1) { ok = true; Bucket(tokens - 1, now) } else { ok = false; Bucket(tokens, now) } } return ok } }
java
// Java — same. The boolean[] holder carries the decision out of the atomic remapping. class PerKeyLimiter { private record Bucket(double tokens, long lastMs) {} private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>(); private final double capacity, refillPerMs; PerKeyLimiter(double capacity, double refillPerSec) { this.capacity = capacity; this.refillPerMs = refillPerSec / 1000.0; } boolean allow(String key, long now) { boolean[] ok = {false}; buckets.compute(key, (k, b) -> { // atomic per key double tokens = (b == null) ? capacity : Math.min(capacity, b.tokens() + (now - b.lastMs()) * refillPerMs); if (tokens >= 1) { ok[0] = true; return new Bucket(tokens - 1, now); } ok[0] = false; return new Bucket(tokens, now); }); return ok[0]; } }

(Verified: 16 threads × 10k calls on one key with no refill grant exactly capacity permits — no lost updates.)

  1. A lock — when an operation spans multiple structures or a whole compound action (§3.3's LRU touching a map and a list). ReentrantLock (with tryLock/timeout options) or synchronized. Keep the critical section small; never do I/O under a lock. Trap: a ReadWriteLock only helps when reads truly don't mutate — the access-order LinkedHashMap breaks this (§3.3).
  2. Bounded, back-pressured hand-off — a BlockingQueue between producer and consumer so a fast producer blocks instead of OOMing (companion guide §4). The scheduler's DelayQueue (§8) is this.

The Spring reality you must state unprompted: a @Service/@Component is a singleton shared across every request thread. A mutable HashMap/ArrayList/counter field in it is a data race — not occasionally, but by construction under concurrent load. The fix is a concurrent type (ConcurrentHashMap, LongAdder, AtomicReference) or external synchronization. This is a favorite "extend this bean" trap.

kotlin
@Service class QuotaService { // shared across all request threads — MUST be concurrent, never a plain HashMap private val limiters = ConcurrentHashMap<String, PerKeyLimiter>() fun check(tenant: String, now: Long): Boolean = limiters.computeIfAbsent(tenant) { PerKeyLimiter(100.0, 10.0) }.allow(tenant, now) }

The distributed jump — the highest-value sentence in the round: "A local lock or in-memory bucket only coordinates threads in one JVM. With N pods behind a load balancer, each enforces the limit independently, so the real limit is N× — the state has to move to a shared store with an atomic operation (Redis + Lua, §4.4) or a partitioned/consensus system. And a distributed lock isn't a mutex: it needs a lease/TTL for crash safety and a fencing token to survive GC pauses — see the concurrency & locking guides; a single Redis is not consensus." Making that leap before being pushed is the clearest Staff+ signal in the whole genre.

12. Testing in the room — inject the clock, check the invariants#

The rubric scores testing as its own axis, and "would I maintain this?" is largely "is this tested?" Two habits do most of the work.

1. Design for testability: inject the clock. Every §3-§8 snippet takes now as a parameter or a clock supplier instead of calling System.currentTimeMillis() inside. That is not incidental — it's what makes TTL, rate limits, and schedulers deterministically testable. Hard-coding now() inside the logic makes the behavior untestable without Thread.sleep, which is flaky and slow. State this as a design choice out loud.

2. Table-driven tests over the edge cases and invariants. Enumerate cases; assert the invariant that must always hold (a cache's size <= capacity, a limiter never exceeds its rate, an iterator yields exactly the flattened sequence).

kotlin
// Kotlin (kotlin.test) — a fake clock makes TTL deterministic; no sleeps, no flakiness. class TtlCacheTest { @Test fun `entry expires exactly at ttl boundary`() { var now = 1_000L val cache = TtlCache<String, String> { now } // injected clock cache.put("k", "v", ttlMs = 100) now = 1_099; assertEquals("v", cache.get("k")) // just before expiry: present now = 1_100; assertNull(cache.get("k")) // at expiry (>=): gone } @Test fun `cache never exceeds capacity - the invariant`() { val cache = LruCache<Int, Int>(capacity = 3) repeat(100) { cache.put(it, it); assertTrue(cache.size <= 3) } // holds after every op } }
java
// Java (JUnit 5) — same, plus a parameterized (table-driven) rate-limiter test. class RateLimiterTest { @Test void expiresAtBoundary() { long[] now = {1_000}; TtlCache<String, String> cache = new TtlCache<>(() -> now[0]); cache.put("k", "v", 100); now[0] = 1_099; assertEquals("v", cache.get("k")); now[0] = 1_100; assertNull(cache.get("k")); } @ParameterizedTest @CsvSource({ "0,true", "0,true", "0,true", "0,true", "0,true", "0,false" }) // 5 allowed then throttled void tokenBucketThrottlesAfterCapacity(long t, boolean expected) { /* drive a shared bucket, assert allow() */ } @Test void concurrentPutsRespectCapacity() throws Exception { // the invariant under threads var cache = new ConcurrentLru<Integer, Integer>(100); var pool = Executors.newFixedThreadPool(16); /* 16 threads hammering put/get; assert cache.size() <= 100 throughout */ } }

The edge-case checklist to run out loud for these problems: capacity 0 or 1; overwrite of an existing key (does it touch/reorder?); eviction order after a mixed get/put sequence; TTL exactly at the boundary (>= vs >); empty/single input; the concurrency invariant under threads; and the "clock went backwards / jumped forward" case for time-based logic. Property-style thinking — "for any sequence of ops, size never exceeds capacity" — is the senior framing even if you only write a few examples. Trap: Thread.sleep-based timing tests. They're flaky (CI is slow) and slow (real waits); the injected clock eliminates both.

13. How the Staff+ practical round is graded#

The same axes as guide 00, specialized for "build a thing":

AxisWhat "strong" looks like hereWhat tanks it
CorrectnessComplete, compiles, passes the edge cases you enumerated.Off-by-one in eviction; TTL boundary wrong; races.
Code quality / readabilitySmall methods, clear names, invariants stated, no dead abstraction.God class; cleverness over clarity; unreviewable.
Data-structure choiceRight structure for each op, complexity you can defend.List.contains in a loop; unbounded heap/queue.
ExtensibilityThe announced twist is an additive change, not a rewrite.First design fights the follow-up; copy-paste to extend.
Concurrency / production-awarenessNames the race before asked; bounds memory; picks the atomic op."I'll add locks later"; ignores the singleton-sharing trap.
TestingInjected clock, table-driven, invariant-checked."That should work"; sleep-based flaky tests.
CommunicationDrives: clarifies API, narrates tradeoffs, offers seams.Silent coding; waits for hints; over-designs unprompted.

The meta-signal, per the 2026 infra rubrics: "solid, honest, maintainable" beats "clever, hacky, unreviewable," and ties go to whoever handles the twist gracefully. Your first version being simple and correct, then evolving cleanly, outscores a baroque first version every time.

Problems & how to solve them#

Problem: you code for ten minutes, then the interviewer says "that's not quite what I meant." Root cause: you started implementing before pinning the API and its semantics — did get mutate? was it bounded? — so you built the wrong thing. Fix: write the interface first and read the semantics back ("get returns null on miss and counts as a use — yes?"). Get buy-in on signatures before any body. Five minutes here saves the round.

Problem: the "now make it thread-safe" twist forces a rewrite. Root cause: mutable state smeared across the class with no chokepoint, so there's no single place to add synchronization. Fix: from the start, funnel state changes through a few methods and keep the mutable core small; then thread-safety is "wrap these three methods," or "swap HashMap for ConcurrentHashMap and use compute." Design the seam even before you need it.

Problem: the "now add LFU / another policy" twist means editing the cache everywhere. Root cause: the eviction rule is hard-coded into the cache's get/put. Fix: factor the varying decision behind an interface (EvictionPolicy) — if the twist is hinted. Open/closed: extend by adding a class, not editing the core (§10). But don't build the seam speculatively (see the next problem).

Problem: you built a factory, a builder, and three interfaces for a 45-minute cache. Root cause: reaching for patterns reflexively — over-engineering reads as weak judgment, not strong. Fix: YAGNI. Minimum structure for clean current code + the announced next step. Offer further seams verbally ("I'd factor this out if you want X") and build them on request.

Problem: it works single-threaded, corrupts under load, and you didn't mention it. Root cause: treating concurrency as an afterthought — but a @Service singleton is shared across all request threads by construction. Fix: raise "when two threads call this…" yourself, early. Pick the cheapest correct tool (immutability → atomic map op → lock). Name the Spring singleton-sharing trap unprompted.

Problem: the cache grows until OOM. Root cause: no size bound (or TTL without a size cap, plus keys set without expiry) — unbounded memory. Fix: bound everything with mutable, growing state — maximumSize on the cache, bounded queues, fixed-window buckets for counters. "What bounds this?" is a question to ask of every field.

Problem: your TTL / rate-limit test is flaky and slow. Root cause: calling System.currentTimeMillis() inside the logic, then testing with Thread.sleep. Fix: inject the clock. Time becomes a parameter; tests set it directly; no sleeps, no flakiness. This is a design decision, not a test trick.

Problem: the distributed twist stumps you — "it's 20 pods now." Root cause: assuming in-process state coordinates across machines; a local lock/bucket only spans one JVM. Fix: move state to a shared store with an atomic operation (Redis + Lua), name the SPOF/latency/fallback tradeoffs, and distinguish "atomic op in one Redis" from "distributed consensus" — the latter needs leases and fencing (concurrency & locking guides).

Interview framing / how to sound senior#

  • Open with the interface, not the algorithm. "Let me pin the API and semantics first." Reading method signatures back to the interviewer is the single strongest early signal — it reframes you from coder to designer and makes every twist additive.
  • Narrate data-structure choice from the access pattern. "O(1) get and O(1) recency reorder → hash map for lookup plus a doubly-linked list for order; the map holds node refs so splicing is O(1)." Derive it; don't recite it. Point to why the structure has that complexity (companion guide).
  • Pre-empt the twists. "I'll assume you'll want this thread-safe and probably TTL'd, so I'm designing so those are additive — clock injected, state behind a few methods." Anticipating the announced follow-up is exactly what the extensibility axis rewards.
  • Raise concurrency before you're asked. "This is a @Service singleton, shared across request threads, so this field has to be a ConcurrentHashMap and I'll use compute for the read-modify-write." Naming the race unprompted is the mid-vs-staff line.
  • Make the distributed leap. "In one JVM a lock is enough; across pods the state moves to Redis with a Lua script for atomicity — and a distributed lock needs a lease and fencing token, it's not just a mutex." This connects the coding round to system design, which is where staff offers are won.
  • Refuse to gold-plate, out loud. "I won't add a strategy pattern until there's a second strategy — right now it's structure without payoff. I'd factor eviction behind an interface if you want LFU too." Restraint is judgment.
  • Test as design. "I inject the clock so TTL is deterministic, and I assert the invariant size <= capacity after every op." Testability-as-a-design-goal reads as production experience.
  • Tie to real systems when natural. Rate limiting → "this is the per-tenant throttle in our webhook service, composed with a circuit breaker and bulkhead." Scheduling → "in-memory heap for the single-node version; Temporal timers for durable saga delays." Pub/sub → "Kafka consumer-group offsets." Grounding the toy in shipped systems is the Staff+ tell — but keep it to a sentence.

Cheat-sheet#

ProblemCore structure(s)Key ideaUsual follow-up twist
LRU cacheHashMap + doubly-linked list (or access-order LinkedHashMap)map→node for O(1) splice; MRU at head, evict tailthread-safe → TTL → LFU → distributed (Redis/Caffeine)
LFU cachekey→{val,freq} + freq→LinkedHashSet + minFreqmove key between freq buckets in O(1); LRU tie-breakcombine with TTL; minFreq bookkeeping
Rate limitertoken bucket / sliding-window counter (O(1) state)lazy refill from elapsed time; weight prev window"20 pods now" → Redis + Lua (atomic RMW)
KV store + TTLConcurrentHashMap + expiry per entrylazy expiry on read + active sweep; value-conditional removeeviction/size bound; persistence; distributed
Min/Max stackstack of (value, min-so-far) framesstore the answer with each element → O(1) querypopMax in O(log n) → balanced BST / TreeMap
Hit countercircular buckets by second (or timestamp deque)fixed O(window) memory over an unbounded streamarbitrary window; distributed count
Autocompletetrie + cached top-k per nodeO(L) walk, cache dodges per-query subtree sortscale → shard by prefix, precompute, cache hot
Schedulermin-heap by run time (+ seq tie-break)root is next-due; sleep nextDelay, no busy-waitself-running → DelayQueue/ScheduledExecutor; durable → Temporal
Nested iteratorstack of iteratorslazy DFS; push list-iterators, emit integerspeeking / merge / zigzag iterators
Pub/subappend-only log + per-subscriber offsetsdecouple producer/consumer via offsets (Kafka-lite)retention/compaction; delivery semantics; isolation
Calculatortwo stacks (values, ops) — shunting-yarddrain ops of ≥ precedence before pushingtokenize→parse split; variables/functions

Escalation ladder for "make it thread-safe": immutability/confinement → ConcurrentHashMap atomic ops (compute/merge) → a small-critical-section lock → bounded BlockingQueue → shared store (Redis) → distributed lock w/ lease + fence. Reach for the cheapest correct one.

Self-test (say the answers out loud)#

  1. Why does an LRU store key → node rather than key → value, and what breaks if you store the value?
  2. Build an LRU from scratch: what two structures, why sentinel nodes, and where does the evicted key get removed from both?
  3. Why can't you use a ReadWriteLock on an access-order LinkedHashMap LRU — what does a "read" actually do?
  4. Contrast lazy vs active TTL expiry. Which does Redis use, and why both? Where does an unbounded TTL store leak?
  5. Name the four rate-limiting algorithms, each in one line, and say which you'd ship and why. What's fixed-window's specific flaw?
  6. "It's 20 pods now." Why is a per-process token bucket wrong, and why is Redis + Lua the fix rather than Redis GET-then-SET?
  7. In LFU, what's the minFreq pointer for, and what's the exact bug if you don't advance it when a bucket empties?
  8. How does a min-stack answer getMin in O(1) through arbitrary pushes and pops? Why is popMax on a max-stack harder?
  9. Autocomplete: why cache top-k per node instead of DFS-and-sort per query, and what's the resulting suggest complexity?
  10. Why does the scheduler need a sequence tie-breaker in its heap comparator, and what production class replaces the hand-rolled sleep loop?
  11. Walk the nested-iterator's stack-of-iterators advance(). Why is it lazy, and how does it handle [[]]?
  12. In the calculator, why >= (not >) when draining the operator stack? Show the case that exposes the difference.
  13. Why is a mutable HashMap field in a @Service a bug by construction? Give two fixes.
  14. Show two ways to make a per-key rate limiter atomic under threads without an explicit lock. Why is getOrPut/containsKey-then-put wrong?
  15. Why inject a Clock? Write the TTL boundary test it enables, and say why Thread.sleep is the wrong tool.
  16. When is factoring eviction behind an EvictionPolicy interface good design, and when is it gold-plating? What do you say instead of building it?

Lineage / sources#

The interface-first / evolve-the-design method and the "would I want to maintain this?" framing are the practical-interview consensus (Tech Interview Handbook's four axes; the 2026 infra rubrics that add code-quality, extensibility, and production-readiness; interviewing.io's senior-loop guidance) synthesized in the series playbook (00) — treat the round-mix percentages and Snowflake specifics (concurrency emphasis, "simulate the system" prompts) as typical, self-reported emphasis, not spec. The canonical problems are LeetCode staples: 146 LRU, 460 LFU, 362 hit counter, 155 min-stack, 716 max-stack, 642 autocomplete, 341 flatten nested list, 284 peeking iterator, 772 basic calculator III; the rate-limiter algorithms are industry-standard (token bucket / GCRA, sliding-window counter — Cloudflare's write-up is the popular reference; the Redis + Lua token bucket is the widely-used atomic pattern). SOLID is Robert C. Martin; the pattern vocabulary is the Gang of Four (Design Patterns); the doubly-linked-list + hash-map LRU and heap-based scheduling are CLRS. Production libraries named — Caffeine (Window-TinyLFU cache), Redis (Lua scripting, atomic single-threaded execution), Temporal.io (durable timers/sagas), Spring Data Redis (RedisTemplate, DefaultRedisScript) — are current as of 2025-26. Language/version facts (Java 17-21 records, text blocks, switch expressions; Kotlin 2 data class, ArrayDeque, withLock) are verified against OpenJDK 21 and Kotlin 2.0. Every non-trivial snippet was compiled and unit-tested (including 16-thread stress tests asserting the capacity invariant and rate-limiter atomicity) before inclusion. For the internals and complexity of every structure used here as a tool — HashMap/ConcurrentHashMap, LinkedHashMap, ArrayDeque, PriorityQueue, trie — see the companion data-structures-java-kotlin-study-guide.md; for locks, the JVM memory model, and distributed-lock lease/fencing semantics, see your concurrency & locking guides.