Caching And Stateful Data Structure Design

What's being tested

This tests stateful data structure design: maintaining mutable state with precise API semantics, predictable complexity, and correct behavior under edge cases. Expect variants involving LRU eviction, sliding-window expiration, streaming order statistics, versioned storage, and buffered stream parsing.

Patterns & templates

• Hash map + doubly linked list for LRUCache.get/put — O(1) average time; always move touched nodes to the head.

• Circular bucket array for rolling counters — store (timestamp, count) per slot; O(1) space for fixed windows like 300 seconds.

• Queue of events for exact sliding windows — enqueue timestamps, evict while ts <= now - window; O(k) space for recent hits.

• Two heaps for MedianFinder — max-heap lower half, min-heap upper half; rebalance sizes so median is O(1).

• Versioned key histories for snapshot KV stores — map key to sorted (snap_id, value) list; get uses binary search in O(log v).

• Internal byte buffer for socket readers — accumulate chunks, parse complete frames, retain leftovers; handle EOF, partial reads, and max-size limits.

• API-first reasoning — define get, put, snapshot, readMessage, hit, getHits semantics before coding; complexity follows from invariants.

Common pitfalls

Pitfall: Treating streams like message queues. A socket read() can return partial messages, multiple messages, or zero bytes before EOF.

Pitfall: Forgetting stale-state cleanup. Rolling counters, LRU nodes, and snapshot histories all require explicit rules for expiration or version visibility.

Pitfall: Giving only the happy path. Apple interviewers often probe empty inputs, duplicate timestamps, overwrite semantics, capacity zero, and boundary times.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.