Anthropic: Implement Python LRU cache with args and persistence

Quick Overview

This question evaluates a candidate's ability to design and implement an LRU cache in Python that supports variable-length positional and keyword arguments with canonical, deterministic hashing for semantically equivalent calls and O(1) get/put via a hash map plus a doubly linked list; it falls under the Coding & Algorithms domain and primarily tests practical implementation skills, API robustness, hashing/equality subtleties, and algorithmic complexity guarantees. The persistence follow-up evaluates understanding of serialization and storage design — on-disk formats, versioning, and atomic write strategies — and compares trade-offs between binary pickle and JSON-based serialization in terms of security, compatibility, and performance, reflecting both conceptual design and practical system-level considerations.

Implement Python LRU cache with args and persistence

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement an LRU cache in Python as a decorator or class that correctly supports variable-length positional arguments and keyword arguments. Ensure that calls are keyed canonically so keyword ordering does not matter, unhashable arguments are converted to deterministic, hashable representations, and semantically equivalent calls map to the same cache entry. Provide O( 1) get/put using a hash map plus a doubly linked list. Follow-up: add persistence so the cache can be snapshotted to disk and restored on process start. Specify an on-disk format, versioning, and atomic write strategy; compare trade-offs between pickle and a JSON-based manual serialization (security, compatibility, performance); and implement a simple, safe approach.

Overview: This question evaluates a candidate's ability to design and implement an LRU cache in Python that supports variable-length positional and keyword arguments with canonical, deterministic hashing for semantically equivalent calls and O(1) get/put via a hash map plus a doubly linked list; it falls under the Coding & Algorithms domain and primarily tests practical implementation skills, API robustness, hashing/equality subtleties, and algorithmic complexity guarantees. The persistence follow-up evaluates understanding of serialization and storage design — on-disk formats, versioning, and atomic write strategies — and compares trade-offs between binary pickle and JSON-based serialization in terms of security, compatibility, and performance, reflecting both conceptual design and practical system-level considerations.

Part 1: Canonical-Argument LRU Cache

Implement an LRU memoization cache for a fixed function signature f(a, b=0, *extra, **kw). Each request is a call described by positional args and keyword args. Two calls must map to the same cache entry if they are semantically the same after Python-style binding for this signature: explicit b=0 equals omitted b, providing a or b by keyword is equivalent to providing them positionally, keyword order does not matter, dict order does not matter, set order does not matter, and nested lists/tuples with the same contents are considered equivalent sequences. Sequence order still matters. The cached function value is defined as the recursive sum of all integers contained in bound a, b, extra, and kw values; dict keys do not contribute to the sum. Use a hash map plus a doubly linked list for O(1) average cache get/put operations. Do not use functools.lru_cache or OrderedDict.

Constraints

0 <= capacity <= 10^4
0 <= len(calls) <= 2 * 10^4
Each call is valid for the signature f(a, b=0, *extra, **kw)
Argument trees contain only hashable atoms or nested lists, tuples, dicts, and sets; total nested elements across all calls is at most 2 * 10^5

Examples

Input: {'capacity': 2, 'calls': [{'args': [1], 'kwargs': {'b': 2, 'x': [3, 4]}}, {'args': [], 'kwargs': {'x': (3, 4), 'a': 1, 'b': 2}}, {'args': [5], 'kwargs': {}}, {'args': [6], 'kwargs': {}}, {'args': [1], 'kwargs': {'x': (3, 4), 'b': 2}}]}

Expected Output: {'results': [10, 10, 5, 6, 10], 'hit_miss': [False, True, False, False, False], 'exec_count': 4}

Explanation: The first two calls are semantically identical, so the second is a hit. Later, capacity 2 forces eviction, so the final repeated call is a miss.

Input: {'capacity': 0, 'calls': [{'args': [1], 'kwargs': {}}, {'args': [], 'kwargs': {'a': 1, 'b': 0}}]}

Expected Output: {'results': [1, 1], 'hit_miss': [False, False], 'exec_count': 2}

Explanation: Edge case: with capacity 0, nothing is stored, so every call misses even if the keys are equivalent.

Hints

First bind every call to the canonical form (a, b, extra, kw) and apply the default b=0 before building a cache key.
Recursively convert unhashable objects into immutable tagged tuples so that dict key order and set order stop mattering.

Part 2: Persistent LRU Cache with Versioned JSON Snapshots

Implement an LRU cache with snapshot and restore. Keys are strings and values are JSON-compatible data. Support put, get, snapshot, and restore operations. A snapshot must use this exact logical schema: {'version': 1, 'capacity': <int>, 'items': [{'key': <string>, 'value': <json>} ...]} where items are listed from least recently used to most recently used. Serialize snapshots deterministically with json.dumps(..., sort_keys=True, separators=(',', ':')). On restore, reject malformed JSON, unsupported versions, duplicate keys, or snapshots with more items than capacity; in all such cases, leave the current cache unchanged and return False. In a real file-backed system, the safe atomic write strategy would be: write to a temporary file, fsync, then rename/replace. For this problem, snapshot and restore work with strings instead of real files. Use JSON rather than pickle: pickle is flexible and often faster for arbitrary Python objects, but unsafe for untrusted data and less portable across environments; JSON is safer and more interoperable when you define an explicit schema.

Constraints

0 <= capacity <= 10^4
0 <= len(ops) <= 2 * 10^4
Keys used by put/get are strings
Values stored by put are JSON-compatible (null/boolean/number/string/list/object)
If restore receives an invalid snapshot, the cache state must remain unchanged

Examples

Input: {'capacity': 2, 'ops': [['put', 'a', 1], ['put', 'b', 2], ['get', 'a'], ['snapshot'], ['put', 'c', 3], ['restore', '{"capacity":2,"items":[{"key":"b","value":2},{"key":"a","value":1}],"version":1}'], ['get', 'b']]}

Expected Output: {'outputs': [None, None, {'found': True, 'value': 1}, '{"capacity":2,"items":[{"key":"b","value":2},{"key":"a","value":1}],"version":1}', None, True, {'found': True, 'value': 2}]}

Explanation: After get('a'), the LRU order becomes b then a, so the snapshot stores items in that order. Restoring brings b back after it was evicted by putting c.

Input: {'capacity': 1, 'ops': [['put', 'x', {'n': 1}], ['snapshot'], ['restore', '{"version":2,"capacity":1,"items":[]}'], ['get', 'x'], ['restore', 'not json'], ['get', 'y']]}

Expected Output: {'outputs': [None, '{"capacity":1,"items":[{"key":"x","value":{"n":1}}],"version":1}', False, {'found': True, 'value': {'n': 1}}, False, {'found': False}]}

Explanation: Unsupported version and malformed JSON must both fail without changing the existing cache.

Approach

The cache is a classic hash map + doubly linked list. self.map maps each key to a Node; the linked list orders nodes from least-recently-used (near head) to most-recently-used (near tail), using two sentinel nodes (head, tail) so insertion and removal never need null checks. Core ops - get(key): if absent, return {'found': False}. If present, unlink the node and re-append it just before tail (marking it MRU), then return its value. Both list edits are O(1). - put(key, value): if the key exists, update the value and move the node to MRU. Otherwise (capacity > 0) create a node, append at MRU, and if len(map) > capacity evict head.next (the true LRU) and delete it from the map. Capacity 0 stores nothing. Persistence - snapshot(): walk the list head→tail collecting {'key','value'} in LRU→MRU order into the fixed schema {'version':1,'capacity':...,'items':[...]}, then json.dumps(..., sort_keys=True, separators=(',', ':')) for a deterministic, compact string. - restore(text): validates first, mutates last (atomicity). It rejects non-JSON, any object whose keys aren't exactly {version, capacity, items}, version != 1, a non-int/negative capacity, a non-list items, len(items) > capacity, malformed item dicts, non-string keys, and duplicate keys — returning False and leaving the cache untouched. Only after all checks pass does it set capacity, _reset() the list, and rebuild nodes in order, returning True. The driver constructs the LRU, replays ops, and collects one output per op (None for put). Correctness rests on every access reordering the list and eviction always taking head.next.

Time complexity: O(1) average for each get/put (hash lookup + constant linked-list splice). snapshot is O(n) to walk n cached items plus the cost of serializing the JSON string; restore is O(m) to validate/rebuild m items (bounded by capacity). Replaying k ops is O(k) plus the snapshot/restore work performed.

Space complexity: O(capacity) for the map and linked list holding at most `capacity` nodes. snapshot/restore additionally use O(n) transient space for the items list and the JSON string, where n is the number of cached items.

Hints

Store cache items in LRU order so snapshot can be emitted directly from least recent to most recent.
Validate the entire snapshot before mutating the cache. In production, pair this with temp-file plus rename for atomic persistence.

Approach

The solution treats each call as a memoized invocation of f(a, b=0, *extra, **kw) and must make semantically equal calls collide on one cache entry.

1. Argument binding (bind) — mirrors Python's binding rules. a comes from args[0] or the a keyword; b from args[1] or the b keyword, defaulting to 0 (so an omitted b and an explicit b=0 produce the same value). Positional overflow args[2:] becomes extra; whatever keywords remain become kw. This is why "by position" and "by keyword" forms unify.

2. Canonicalization (freeze) — builds a hashable, order-normalized key:

dict → items sorted by repr of the frozen key, so key/order differences don't matter (and dict keys are kept only for identity, not summed).
set → frozen elements sorted by repr, erasing set order.
list/tuple → both tagged 'seq', so a list and tuple with equal contents are equivalent, but order is preserved.
atoms → ('atom', x).

The cache key is (freeze(a), freeze(b), freeze(extra), freeze(kw)).

3. Value (sum_ints) — recursively sums every int inside the bound values, descending into list/tuple/set elements and dict values (keys excluded).

4. LRU — a cache dict maps keys to Nodes in a doubly linked list with head/tail sentinels. A hit moves the node to MRU (remove+append_mru) and returns its stored value. A miss computes the value, and if capacity > 0 inserts at MRU, evicting head.next (the LRU) when size exceeds capacity. capacity == 0 records the result but stores nothing. All list splices are O(1), so get/put are O(1) average.

Space complexity:

O(capacity * S) where S is the average frozen-key size, for the bounded cache and its linked-list nodes, plus O(k) transient space per call to build the frozen key. Output arrays add O(N).