LRU Cache Design And Persistence

What's being tested

This tests LRU cache implementation with O(1) lookup, update, and eviction using a hash map plus doubly linked list. Harder variants add memoization key canonicalization, variable *args/**kwargs, and persistence/crash recovery without losing ordering correctness.

Patterns & templates

• Hash map + doubly linked list — map keys to nodes; list order stores recency; get/put move nodes to front in O(1).

• Sentinel head/tail nodes simplify remove(node) and insert_front(node); avoid special cases for empty, one-item, and tail eviction.

• Capacity eviction happens after insert/update; if size > capacity, remove tail.prev and delete its key from the map.

• Decorator memoization wraps func(*args, **kwargs); key should include function identity plus canonicalized arguments, not just raw positional tuple.

• Canonical argument binding with inspect.signature(func).bind() normalizes defaults and keyword order; convert unhashable structures recursively before hashing.

• Persistence snapshot serializes capacity, key-value pairs, and recency order using pickle, json, or custom encoding; restore list order exactly.

• Crash resilience needs atomic writes: write to temp file, flush/fsync, then os.replace; optionally use an append-only log plus compaction.

Common pitfalls

Pitfall: Updating a value without moving it to most-recent breaks the LRU contract; both cache hits and overwrites count as use.

Pitfall: Using str(args) + str(kwargs) for keys is nondeterministic or ambiguous; keyword order and mutable containers must be canonicalized.

Pitfall: Persisting only the dictionary is insufficient; recovery also needs recency order, capacity, and enough metadata to reject corrupted snapshots.

Practice these

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