LRU Cache

Reported in interviews at Alibaba Anthropic AQR Capital Management Balyasny Asset Management Citadel OpenAI

Problem statement

Design and implement a Least Recently Used (LRU) cache and drive it with a sequence of operations.

Implement the function run_ops(capacity, ops):

  • capacity is the maximum number of key-value pairs the cache holds.
  • ops is a list of operations, each of the form ["get", key] or ["put", key, value].

Replay the operations in order against an LRU cache of the given capacity and return a list containing one entry for every "get" operation (in order): the value stored for that key, or -1 if the key is absent. "put" operations produce no output.

The underlying cache supports two operations:

  • get(key) -- Return the value associated with key if it exists, otherwise -1. Accessing a key marks it as most recently used.
  • put(key, value) -- Insert or update the key-value pair. If the cache is already at capacity, evict the least recently used entry before inserting the new one.

Both cache operations must run in $O(1)$ average time, using $O(C)$ space where $C$ is the capacity.

Constraints:

  • $1 \leq C \leq 3000$
  • $0 \leq \text{key} \leq 10^4$
  • $0 \leq \text{value} \leq 10^5$
  • At most $2 \times 10^5$ calls to get and put combined

Example

run_ops(2, [["put", 1, 1], ["put", 2, 2], ["get", 1], ["put", 3, 3],
            ["get", 2], ["get", 3], ["put", 4, 4], ["get", 1],
            ["get", 3], ["get", 4]]) -> [1, -1, 3, -1, 3, 4]

Only the six "get" operations produce output. get(1) returns 1; inserting key 3 evicts key 2 (the LRU), so get(2) returns -1; get(3) returns 3; inserting key 4 evicts key 1, so get(1) returns -1; then get(3) and get(4) return 3 and 4.

Show hint

What does each operation need to find quickly, and can any single standard structure provide all of it?

Relevant roles: ML Engineer, AI Engineer, MLOps Engineer, Forward Deployed Engineer and LLM Engineer.

Related free problems