Implement a crash-resilient LRU cache

Implement an LRU-based memoization helper with behavior similar to a standard Python LRU cache.

You are given an interface like this:

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.

Part 1: Implement an in-memory LRU-based memoization helper

Simulate an in-memory LRU (Least Recently Used) memoization cache over a sequence of pure-function calls, and report each call's result together with how many real computations were actually performed.

What to implement

def solution(capacity, calls):
    ...

Process the calls in order against a cache that can hold at most capacity distinct entries. For each call, either return its cached result (a hit) or compute it fresh and cache it (a miss), evicting the least recently used entry whenever the cache would exceed capacity.

Input

• capacity — a non-negative integer, the maximum number of entries the cache may hold.
• calls — a list of calls, each a 3-tuple (func_name, args, kwargs):
  • func_name — a string naming the function to invoke (see below).
  • args — a list of positional arguments.
  • kwargs — a dict of keyword arguments.

Supported functions

func_name is always one of:

Name	Signature	Result
'add'	add(a, b)	a + b
'mul'	mul(a, b)	a * b
'pow'	pow(base, exp)	base ** exp
'affine'	affine(x, scale=1, bias=0)	scale * x + bias

Every call's args/kwargs are valid for the named function (so scale and bias may be passed positionally or by keyword, or omitted to use their defaults).

Cache key

A cache entry is identified by the combination of:

1. the function name,
2. the positional arguments (args, in order), and
3. the keyword arguments (kwargs).

Keyword order must not matter. Two calls with the same keyword pairs in a different order refer to the same cache entry — e.g. affine(5, scale=2, bias=1) and affine(5, bias=1, scale=2) share one entry.

Per-call behavior

For each call, in order:

• Hit — if its key is already in the cache: return the cached value and mark that entry as most recently used (do not recompute).
• Miss — otherwise: invoke the function to compute the value, count this as one real computation, and return the value. Then, only if capacity > 0, store the value under its key as the most recently used entry; if this makes the cache size exceed capacity, evict the least recently used entry.

Note that when capacity == 0, nothing is ever stored, so every call is a miss and is recomputed.

Output

Return a tuple (results, computed_count) where:

• results — the list of returned values, one per call, in call order.
• computed_count — the total number of misses, i.e. the number of times a value was actually computed (cache hits are not counted).

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

Examples

Example 1

Input: (2, [('add', [1, 2], {}), ('add', [1, 2], {})])
Output: ([3, 3], 1)

Explanation: The second call is a cache hit.

Example 2

Input: (2, [('affine', [5], {'scale': 2, 'bias': 1}), ('affine', [5], {'bias': 1, 'scale': 2})])
Output: ([11, 11], 1)

Explanation: Keyword argument order should not change the cache key.

Hints

1. Use a canonical key like (func_name, tuple(args), tuple(sorted(kwargs.items()))).
2. A hash map plus an OrderedDict-style structure makes LRU updates efficient.

Approach

Approach: LRU cache built on OrderedDict.

The solution simulates an LRU-memoized dispatcher over four pure functions (add, mul, pow, affine), held in a functions lookup dict so a func_name string maps to the right callable.

Cache key. For each call it normalizes inputs into a hashable key: Sorting kwargs.items() is the crux of correctness: it makes keyword order irrelevant, so {'scale':2,'bias':1} and {'bias':1,'scale':2} produce the same key and share one cache entry.

LRU bookkeeping. An OrderedDict tracks recency — front = least recently used, back = most recently used.

• Hit (key in cache): call move_to_end(key) to mark it MRU, append the cached value, and skip computation.
• Miss: invoke functions[func_name](*args, **kwargs), increment computed_count, and append the value. Then, only if capacity > 0, insert the entry and move_to_end; if len(cache) > capacity, evict the LRU with popitem(last=False).

Why it's correct. Every access (hit or insert) refreshes the entry to the back, so the front is always the genuine LRU candidate — standard LRU semantics. With capacity == 0 nothing is ever stored, so repeated calls each recompute (matching test 5, where two identical add calls yield computed_count == 2). computed_count counts only real computations, i.e. misses.

The function returns [results, computed_count].

• Time complexity: O(n * k log k), where n = number of calls and k = max keyword args per call (from sorting kwargs each call); OrderedDict get/insert/move_to_end/popitem are all O(1).
• Space complexity: O(capacity + n): the cache holds at most capacity entries, plus O(n) for the results list returned.

Part 2: Recover a crash-resilient LRU cache from a write-ahead journal

Reconstruct the exact state of an LRU cache after a crash by replaying its write-ahead journal.

Background

The cache persists durably: before any operation is considered successful, it appends a journal record describing that operation. After a crash, only a prefix of the journal survived (passed to you as journal). Replaying that surviving prefix in order, with LRU eviction, reproduces the exact recovered cache state.

Implement:

def solution(capacity, journal):
    ...

Input

• capacity — the maximum number of entries the cache may hold.
• journal — a list of records, already in durable (chronological) order. Each record is a tuple/list of one of two forms:
  • PUT: ('PUT', func_name, args, kwargs, value) — the computed value for this key is now stored, and the key becomes the most-recently-used (MRU) entry.
  • HIT: ('HIT', func_name, args, kwargs) — an existing key was read, so it becomes the MRU entry.

In every record, func_name is a string, args is a list, and kwargs is a dict.

Canonical key

Each record identifies a cache entry by a canonical key built as:

(func_name, tuple(args), tuple(sorted(kwargs.items())))

Sorting the kwargs items by name means different keyword-argument orders map to the same key (e.g. {'scale': 2, 'bias': 1} and {'bias': 1, 'scale': 2} are identical).

Replay rules

Process records in order, maintaining LRU recency:

• PUT: Store the value under the canonical key and mark that key as MRU. If this makes the number of stored entries exceed capacity, evict the least-recently-used (LRU) entry.
• HIT: If the canonical key is currently present, mark it as MRU. If the key is not present during replay, ignore the record (no insertion, no error).

Output

Return the recovered cache contents ordered from most-recently-used to least-recently-used, as a list of (canonical_key, value) pairs, where canonical_key is the tuple described above.

Edge cases

• If capacity is 0, no entry can ever be stored — return an empty list.
• If journal is empty, return an empty list.

Constraints

• 0 <= capacity <= 100000
• 0 <= len(journal) <= 100000
• Each record's operation is either 'PUT' or 'HIT'.
• All argument values and stored values are integers.
• Records are already in durable journal order.

Examples

Example 1

Input: (2, [('PUT', 'add', [1, 2], {}, 3), ('PUT', 'mul', [2, 3], {}, 6), ('HIT', 'add', [1, 2], {})])
Output: [(('add', (1, 2), ()), 3), (('mul', (2, 3), ()), 6)]

Explanation: The hit on 'add' makes it the most recently used entry.

Example 2

Input: (2, [('PUT', 'add', [1, 2], {}, 3), ('PUT', 'mul', [2, 3], {}, 6), ('PUT', 'pow', [2, 5], {}, 32), ('HIT', 'add', [1, 2], {})])
Output: [(('pow', (2, 5), ()), 32), (('mul', (2, 3), ()), 6)]

Explanation: When 'pow' is inserted, 'add' is evicted as the least recently used entry. The later hit on 'add' is ignored because that key is no longer present.

Hints

1. Replay the journal exactly in order; a durable log is only as good as its replay rules.
2. Use the same normalized key for both 'PUT' and 'HIT', and keep LRU order in an OrderedDict-style structure.

Approach

Approach. The recovered cache is just the result of replaying the surviving journal prefix in order, so the code simulates an LRU cache record by record. An OrderedDict is the natural data structure: insertion order is preserved, and we treat the rightmost end as most-recently-used (MRU) and the leftmost as least-recently-used (LRU).

Canonical key. Every record's key is normalized via make_key to (func_name, tuple(args), tuple(sorted(kwargs.items()))). Sorting the kwargs items makes {scale:2, bias:1} and {bias:1, scale:2} collapse to the same key, which is why test 3's HIT with reordered kwargs correctly refreshes the existing entry.

Replay rules.

• HIT: only move_to_end(key) if the key is present; a HIT on a missing key is silently ignored, exactly as required.

Edge handling. capacity <= 0 short-circuits to [], so the capacity-0 case (test 4) never stores anything.

Output. OrderedDict holds entries LRU→MRU; the code copies items() and reverse()s them so the result is MRU→LRU as (canonical_key, value) pairs.

Correctness. Because the journal records the durable order of operations and each replay step reproduces the cache's own LRU bookkeeping, replaying yields the exact crash-recovered state.

• Time complexity: O(r * k log k)
• Space complexity: O(capacity)