Implement Python LRU cache with varargs
Company: HubSpot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement an LRU cache in Python as a decorator cache(maxsize) that memoizes a target function's results. Must support positional args, *args, and **kwargs so that semantically equivalent calls (e.g., f(1, b=
2) and f(1,
2)) map to the same key. Handle unhashable arguments by canonicalizing them into a deterministic, hashable representation. Provide operations: eviction by least recently used, clear(), and cache_info(). Follow-up: add persistence methods save(filepath) and load(filepath) that serialize the cache to JSON (no pickle). Define how you encode keys and values, and how you handle non-JSON-serializable return values and versioning.
Quick Answer: This question evaluates a candidate's ability to implement an LRU caching mechanism in Python, including decorator design, argument canonicalization for positional args, *args, and **kwargs, handling unhashable inputs, eviction semantics, cache metadata operations (clear, cache_info), and JSON-based persistence and versioning.
Implement the core of a Python-style `cache(maxsize)` memoization decorator as a pure simulation.
You are given:
- `maxsize`: the maximum number of distinct cached call-keys to retain (or `None` for unbounded).
- `params`: the ordered list of the target function's positional parameter names, e.g. `['a', 'b']`.
- `calls`: a list of calls, each a dict with optional `args` (a list of positional argument values) and `kwargs` (a dict of keyword argument values).
For each call, build a cache key by **binding** positional `args` to `params` by position and merging in `kwargs`, so that semantically-equivalent invocations map to the same key — e.g. with `params = ['a','b']`, the calls `{'args':[1,2]}` and `{'args':[1],'kwargs':{'b':2}}` must collide. Any positional argument beyond `len(params)` goes into an order-sensitive `*args` bucket. Because argument values may be **unhashable** (lists, dicts, sets), canonicalize each value into a deterministic, hashable representation before keying.
Maintain an LRU cache of at most `maxsize` keys. A call whose key is already present is a **hit** (and refreshes recency); a new key is a **miss** (inserted as most-recently-used, evicting the least-recently-used key if the cache would exceed `maxsize`). When `maxsize` is `None`, never evict.
Return the list of `'hit'` / `'miss'` strings, one per call in order.
Constraints
- 0 <= len(calls) <= 10^4
- 0 <= len(params) <= 50
- maxsize is a positive integer or None (unbounded)
- Argument values may be ints, strings, bools, or nested lists/dicts/sets (possibly unhashable)
- Binding rule: positional args fill params by index; extras form an order-sensitive *args bucket; kwargs override/add by name
Examples
Input: (2, ['a', 'b'], [{'args': [1, 2]}, {'args': [1], 'kwargs': {'b': 2}}])
Expected Output: ['miss', 'hit']
Explanation: Binding positional [1,2] to params [a,b] gives {a:1,b:2}; the second call {a:1, b:2} binds to the same mapping, so it hits.
Input: (2, ['a', 'b'], [{'kwargs': {'b': 2, 'a': 1}}, {'args': [1, 2]}])
Expected Output: ['miss', 'hit']
Explanation: Keyword order does not matter: {b:2,a:1} canonicalizes to the same sorted key as positional [1,2].
Hints
- Two calls are 'the same' only after you bind positional args to parameter names — normalize every call into a single name->value mapping before hashing.
- Lists, dicts and sets are unhashable. Recursively convert them into nested tuples (sort dict items and set elements) so the key is deterministic regardless of insertion order.
- An OrderedDict gives you O(1) LRU: move_to_end on a hit, and popitem(last=False) to drop the least-recently-used key when you exceed maxsize.
- Tag primitives with their type in the key so values like 1 and True (or 1 and '1') don't accidentally collide.