Linked Lists, Pointers, Caches, And In-Memory Stores

What's being tested

These problems test pointer manipulation, hash map + linked list composition, and stateful in-memory data modeling under strict complexity guarantees. Interviewers are probing whether you can preserve invariants, reason about edge cases, and explain tradeoffs like O(1) average access versus extra memory.

Patterns & templates

• Hash map deep copy for copyRandomList — map original nodes to clones in O(n) time/space; handle null random pointers cleanly.

• Interleaved linked-list cloning — weave clone nodes into the original list for O(n) time and O(1) auxiliary space; restore original links.

• Character stream comparison across linked string chunks — implement nextChar() iterators; compare lazily in O(total chars) time.

• LRU cache template — combine dict[key] -> node with a doubly linked list; get and put must both move nodes to front.

• TTL/versioned store design — store per key-field a sorted history of (timestamp, value, expiry); use binary search for historical reads.

• Top-k selection for closest points — use max-heap size k for O(n log k) or Quickselect average O(n); avoid square roots.

• Invariant-first coding — define sentinel head/tail, node ownership, expiration semantics, and tie-breaking before writing update logic.

Common pitfalls

Pitfall: Updating cache values without refreshing recency breaks LRU semantics; every successful get and existing-key put should move the node.

Pitfall: Deep-copying only next pointers creates shared random references; verify cloned nodes never point back into the original structure.

Pitfall: For TTL history, confusing “current value expired” with “historical value never existed” leads to incorrect getAt(timestamp) behavior.

Practice these

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