Function-Call LRU Cache: Argument Key Generation and Crash Recovery from a Log

Build an LRU (least recently used) cache that memoizes function calls in Python. When a function is called with arguments whose result is already in the cache, the cached result is returned instead of calling the function again. The cache holds at most `capacity` entries; when it is full, adding a new entry evicts the entry that was used least recently. The interviewer runs test cases against your code. The exact interface was not reported. This one is a reasonable starting point: ```python class LRUCache: def __init__(self, capacity: int, file_path: str | None = None) -> None: ... def get(self, key): ... # the cached value, or a "miss" marker def put(self, key, value) -> None: ... def make_key(func, args: tuple, kwargs: dict): ... def memoize(cache: LRUCache): """Decorator: serve calls of the decorated function from `cache`.""" ``` ### Constraints and Clarifications - One cache may hold results of several different functions. - `get` and `put` should take constant time, apart from the cost of building the key. - In Part 2 you are given a `file_path`; the cache must append its log to that file and write each record to disk. ### Clarifying Questions - Should `f(1, 2)`, `f(1, b=2)` and `f(a=1, b=2)` share one cache entry? What about `f(1)` when `b` defaults to 2? - Can arguments be unhashable values such as lists or dicts? What should happen to a call whose arguments cannot be turned into a key? - Should a call that raises an exception be cached? - Does a cache hit count as a use that must survive a crash, so that the recovered least-recently-used order matches exactly? - How durable must each write be: is surviving a process crash enough, or must it also survive the machine losing power? ### Part 1 — Generate keys for a function and its arguments Implement `make_key`, the LRU cache and the `memoize` decorator. Two calls should map to the same key when they call the same function with equivalent arguments, and must never map to the same key otherwise. ```hint Same call, same key; different call, different key List calls that should share an entry (the same arguments passed in a different style) and calls that must not (equal-looking arguments of different types, or the same arguments to two different functions), and make the key respect both lists. ``` #### What This Part Should Cover - What identifies the function, and how positional, keyword and default arguments are normalized - Handling unhashable or mutable arguments, and arguments that cannot be keyed at all - LRU mechanics with constant-time `get` and `put` - Decorator behavior on misses, on cached `None` results, and on exceptions ### Part 2 — Recover the cache after a crash The cache constructor now receives a `file_path`. Every change to the cache must be appended as a log record to that file and written to disk at the time of the change. If the process crashes, a new cache constructed with the same `file_path` must rebuild the contents it had before the crash. Design the log format. In particular, decide how records are separated so that, after reopening the file, its content can be split back into exactly the records that were written. Then implement logging and recovery. ```hint Where does one record end? Before writing code, decide how a reader finds record boundaries when keys or values may contain arbitrary characters, and what it should do with a last record that was only half written. ``` ```hint Replay, then compare Think about what replaying the log has to reproduce: not only which entries exist, but which one would be evicted next. ``` #### What This Part Should Cover - Record format and framing, and why a boundary can never be confused with data - Which operations are logged, and replay rules that rebuild both contents and recency - Durability (flushing versus forcing to disk) and handling a torn last record - Keys that stay valid across restarts, and keeping the log from growing forever ### What a Strong Answer Covers - Working code whose tests pass, built in a sensible order - Keys that are correct within one process and stable across processes - A recovery path that tolerates a crash in the middle of a write - A clearly stated durability guarantee and its cost - Good time management: core functionality working before refinements ### Follow-up Questions - The log grows without bound. How do you compact it so that a crash during compaction cannot lose data? - Two processes open caches on the same file. What breaks, and how would you prevent it? - How would you add a time-to-live to entries, and how does it interact with recovery? - Some return values cannot be serialized. What should the cache do with them?