Function Call LRU Cache

Instructions

Implement a class that memoizes calls to a function using an LRU cache, built up over two levels:

1. Cache key — turn each call's arguments into a hashable key so repeated calls return the cached result instead of recomputing.
2. Disk persistence — make the cache survive across process restarts using an append-only log.

The LRU mechanics (capacity limit, eviction, and recency updates) are already implemented for you. You may assume that every argument and every return value is JSON-serializable, and that every decorated function has a unique name.

Interfaces

class FunctionCache:
    def __init__(self, func, limit: int): ...
    def _cache_key(self, func_name: str, args: list): ...   # build a hashable cache key
    def get(self, *args): ...                                # cached call: hit refreshes recency, miss computes

Level 1: Build the Cache Key

Implement _cache_key(self, func_name, args) so that it returns a value usable as a dictionary key for the given call.

Hints

• The returned key must be hashable. The raw args list can't be used as a dict key. What if the arguments may themselves contain nested lists or dicts?
• The key must uniquely identify the (func_name, args) pair, and equal argument values must always map to the same key.

Example

calls = []

def add(a, b):
    calls.append((a, b))    
    return a + b

cache = FunctionCache(add, limit=128)

cache.get(1, 2)   # -> 3   miss: computed.  calls == [(1, 2)]
cache.get(1, 2)   # -> 3   hit:  same key.  calls unchanged
cache.get(2, 3)   # -> 5   miss: computed.  calls == [(1, 2), (2, 3)]

Eviction should behave like a standard LRU:

def square(n):
    return n * n

cache = FunctionCache(square, limit=2)

cache.get(1)   # store (LRU -> MRU): 1
cache.get(2)   # 1, 2
cache.get(1)   # hit; 1 becomes most-recent -> 2, 1
cache.get(3)   # miss; over limit, evict LRU (2) -> 1, 3
cache.get(2)   # miss again (2 was evicted) -> recomputes

Result will appear here after submission.

Level 2: Add Disk Persistence

Extend the cache so that it survives across process restarts.

• Add a file_path parameter to __init__ (default "", which means persistence is disabled — behave exactly as in Level 1).
• When persistence is enabled, every access is written to disk, and when a new instance is constructed pointing at an existing file_path, the cache is restored from that file.

Hints

• The cost of a single write must not grow with the cache size. You may not re-serialize and rewrite the entire cache on every access. The intended approach is an append-only log: each access appends one small record.
• After restoring from the log, the cache must reflect the correct state: the most recent value for each key, the correct LRU, then most recent used and then the same capacity/eviction behavior as Level 1.
• Be robust to a truncated final record. A process can crash mid-write. Restoration must tolerate this and recover everything written before it.

Example

# ----- first run -----
c = FunctionCache(square, limit=2, file_path="square.log")

c.get(2)   # miss -> 4, record appended to square.log
c.get(3)   # miss -> 9, record appended to square.log
# process exits

# ----- second run (fresh process, same file) -----
c = FunctionCache(square, limit=2, file_path="square.log")

c.get(2)   # -> 4, restored from disk WITHOUT recomputing
c.get(3)   # -> 9, restored from disk WITHOUT recomputing

The restored cache must also preserve recency. If the log's last write for square(2) came after square(3), then after restore the order should be [3, 2], so the next miss evicts 3 first.

Result will appear here after submission.

Level 3 and More Followups

...