Implement a crash-resilient LRU cache
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Onsite
Implement an LRU-based memoization helper with behavior similar to a standard Python LRU cache.
You are given an interface like this:
```python
class LRU:
def __init__(self, capacity: int, persistence_path: str):
...
def generate_key(self, func, *args, **kwargs):
# return a deterministic, hashable cache key
pass
def call(self, func, *args, **kwargs):
# if the result for this function call is cached, return it
# otherwise compute it, cache it, and return it
pass
```
Requirements:
1. Cache results of pure function calls.
2. The cache key must include the function identity and its arguments.
3. `generate_key` must handle both positional and keyword arguments.
4. Different keyword argument orders must produce the same key.
5. When the cache exceeds `capacity`, evict the least recently used entry.
6. Assume arguments and return values are serializable.
Follow-up: if the process crashes and the in-memory cache is lost, how would you persist enough information to restore the cache after restart while keeping the cache correct? Describe the data you would write, when you would write it, and how recovery would work.
Quick Answer: This question evaluates knowledge of cache design, least-recently-used (LRU) eviction policies, deterministic memoization key construction for function identity and arguments, and persistence mechanisms for crash resilience in the Coding & Algorithms domain.
Part 1: Implement an in-memory LRU-based memoization helper
You are given a sequence of function calls and must simulate an in-memory LRU memoization cache. Each call is represented as (func_name, args, kwargs). The cache key must include the function identity, positional arguments, and keyword arguments. Keyword argument order must not matter: calls with the same keyword pairs in different orders must map to the same cache entry. If a call is already cached, return the cached value and mark it as most recently used. Otherwise, compute the value, store it if capacity > 0, and evict the least recently used entry when the cache exceeds capacity. Supported pure functions are: 'add'(a, b) = a + b, 'mul'(a, b) = a * b, 'pow'(base, exp) = base ** exp, and 'affine'(x, scale=1, bias=0) = scale * x + bias. Return both the list of call results and the number of times a real computation was performed.
Constraints
- 0 <= capacity <= 100000
- 0 <= len(calls) <= 100000
- func_name is one of 'add', 'mul', 'pow', 'affine'
- All provided calls are valid for the named function
- All argument values are integers and keyword arguments are hashable