How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anthropic during technical interviews.

Implement a crash-resilient LRU cache | Anthropic Coding Question

Quick Overview

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.

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

Examples

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

Expected Output: ([3, 3], 1)

Explanation: The second call is a cache hit.

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

Expected Output: ([11, 11], 1)

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

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

Expected Output: ([3, 2, 3, 8, 2], 4)

Explanation: After 'pow' is inserted, the least recently used entry is evicted. 'add' and 'mul' use different cache keys even with the same positional arguments.

Input: (3, [])

Expected Output: ([], 0)

Explanation: Edge case: no calls.

Input: (0, [('add', [1, 1], {}), ('add', [1, 1], {})])

Expected Output: ([2, 2], 2)

Explanation: Edge case: capacity 0 means nothing is stored, so every call is recomputed.

Hints

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

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

A cache uses this persistence strategy: before an operation is considered successful, it writes a durable journal record. A cache miss writes ('PUT', func_name, args, kwargs, value), which means the computed value for that key is now stored and becomes the most recently used entry. A cache hit writes ('HIT', func_name, args, kwargs), which means that existing key becomes the most recently used entry. Keys are deterministic and must be built as (func_name, tuple(args), tuple(sorted(kwargs.items()))), so different keyword argument orders represent the same key. After a crash, only the journal prefix given in the input survived. Reconstruct the exact recovered cache state by replaying the journal in order with LRU eviction. If a 'HIT' references a key that is not currently present during replay, ignore it. Return the recovered cache contents from most-recently-used to least-recently-used as a list of (canonical_key, value).

Constraints

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

Examples

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

Expected Output: [(('add', (1, 2), ()), 3), (('mul', (2, 3), ()), 6)]

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

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

Expected 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.

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

Expected Output: [(('affine', (5,), (('bias', 1), ('scale', 2))), 11), (('add', (1, 1), ()), 2)]

Explanation: Keyword argument order is normalized during recovery, so the hit matches the existing 'affine' entry.

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

Expected Output: []

Explanation: Edge case: capacity 0 means the recovered cache is empty.

Input: (3, [])

Expected Output: []

Explanation: Edge case: an empty durable journal recovers an empty cache.

Hints

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

Quick Overview