Katkat
Back

Implement Persistent Memoization LRU Cache

AnthropicSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a decorator that memoizes function results using an LRU policy while ensuring the cache survives process restarts via disk serialization.

Problem Statement

Design a Python decorator @persistent_lru_cache(capacity: int, filepath: str) that memoizes the results of a function.

Requirements:

  1. LRU Policy: If the cache exceeds capacity, remove the least recently used entry.
  2. Persistence: The cache state must be saved to a JSON file at filepath after every update so that the cache is recovered when the process restarts.
  3. Cache Keys: You must generate a unique, deterministic key based on the function's positional and keyword arguments. You can assume all arguments are JSON-serializable.
  4. Efficiency: Reads should be O(1) on average. Writing to disk can be done periodically or on update, but ensure the LRU ordering is maintained across restarts.

Signature

def persistent_lru_cache(capacity: int, filepath: str):
    def decorator(func):
        # Implementation here
        return wrapper
    return decorator

Example

@persistent_lru_cache(capacity=2, filepath="cache.json")
def add(a, b):
    print("Computing...")
    return a + b

add(1, 2)  # Prints "Computing...", returns 3
add(1, 2)  # Returns 3 (from cache)
# After process restart, add(1, 2) still returns 3 without recomputing.

Constraints

  • The cache file may grow; assume entries are simple types.
  • Arguments might arrive in different orders (e.g., func(a=1, b=2) vs func(b=2, a=1)), which should result in the same cache key.
  • Handle file I/O errors gracefully.

Hints

Hint 1

Use a `collections.OrderedDict` to maintain the LRU order of keys, where the most recently used items are moved to the end.

Hint 2

For deterministic keys, sort the dictionary items of keyword arguments into a tuple of tuples before creating a hashable key.

Hint 3

Upon initialization of the decorator, read the existing JSON file into memory to repopulate the `OrderedDict`.

Follow-up questions

  • How would you handle non-serializable arguments (like custom class instances) in the cache key?
  • What concurrency issues arise if multiple processes try to write to the same JSON file simultaneously, and how would you fix them?
  • If the cache file grows to several gigabytes, how would you modify the persistence strategy to avoid loading the entire file into memory?