Core Data Structures, Caches, And Clean Implementation

What's being tested

Implementing an LRU-style cache with support for pinned entries tests mastery of combining a hash map and doubly-linked list to get average O(1) get/put and eviction. Interviewers probe correctness under edge cases (capacity zero, all items pinned), invariants maintenance, and simple performance-aware implementation choices.

Patterns & templates

• Hash map + doubly-linked list — map key→node for O(1) lookup; list orders recency; move_to_front on access, pop_tail on eviction.

• Use sentinel head/tail nodes to simplify insert/remove logic and avoid null checks in unlink/insert_front.

• Maintain a per-node pinned flag; evict must skip pinned nodes and continue to next tail candidate.

• Track current size vs capacity; decrement size only when evicting an unpinned node; handle capacity==0 early.

• Provide get(key) → return value and move_to_front(node); put(key, val, pinned=False) → update or insert with possible eviction.

• To avoid O(n) scans for eviction when many pinned items, maintain an unpinned-count or separate unpinned list to short-circuit eviction failures.

• For concurrent access, wrap get/put in a single coarse lock or use ConcurrentHashMap + lock striping; always protect list mutations.

Common pitfalls

Pitfall: Scanning from tail until an unpinned node is found can be O(n) if most nodes are pinned — maintain auxiliary bookkeeping to avoid linear scans.

Pitfall: Forgetting to update the hash map when moving or replacing nodes leads to stale pointers and memory leaks.

Pitfall: Not handling capacity==0 or "all entries pinned" cases — explicitly fail put or return an error/boolean.

Practice these

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