LRU Cache Design and Canonical Keys

What's being tested

Candidates must show correctness and engineering rigor for an LRU cache: O(1) recency updates, deterministic memoization key construction across argument spelling/order, and safe persistence for crash resilience. Interviewers probe data-structure choice, canonicalization of function signatures, handling of non-hashable/nested inputs, and trade-offs between latency and durability.

Patterns & templates

• Doubly-linked list + hashmap — O(1) get/set/evict; implement nodes with key/value and move-to-front on access.

• collections.OrderedDict for quick Python prototype — popitem(last=False) for LRU eviction, O(1) average.

• Canonical signature binding with inspect.signature + Signature.bind — normalize positional/keyword into parameter-name order.

• Freeze supported values into immutable, type-tagged tuples (e.g., ("list", (..)), ("dict", (("k",v),..))) so lists/dicts are distinguished and hashable.

• Avoid caching exceptions — re-raise without storing failed results; only cache successful return values.

• Crash-resilience: append-only log or write-ahead log for mutations; persist both key→value mapping and recency order (or timestamps) and fsync at chosen durability points.

• Deterministic function identity — include function module + __qualname__ (or explicit id) in cache key to avoid cross-function collisions.

• Space/time tradeoff: persisting recency per operation increases p99 latency; batch checkpoints or async WAL flushes reduce latency but increase potential data loss.

Common pitfalls

Pitfall: Building keys from raw args/kwargs order — misses canonical binding and treats equivalent calls as different.

Pitfall: Using naive json.dumps for keys — loses type distinctions (tuple vs list) and can reorder dict keys unless sorted.