LRU Cache, Then Extend It

Difficulty

Asked at Jane Street, Citadel Securities

Theory: Data Structures You Implement, Not Import

Read the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.

Available in Python and C++. You are solving it in Python. Switch to C++

Implement a class LRUCache, built with a capacity. It is a least-recently-used cache, extended with a method that reports the key that would be evicted next. A pricing service puts a cache like this in front of data that is expensive to fetch and mostly read, such as symbol metadata or curve snapshots. The class has three methods: get(key): return the value stored under key and mark the key most recently used, or -1 if the key is absent. put(key, value): insert or update key; an update also marks the key most recently used. If inserting a new key would exceed capacity, evict the least-recently-used key first. get_stale(): return the least-recently-used key, the one put would evict next, without evicting it and without changing any recency order. Return -1 if the cache is empty. class LRUCache: def __init__(self, capacity: int) -> None: ... def get(self, key: int) -> int: ... def put(self, key: int, value: int) -> None: ... def get_stale(self) -> int: ... The tests drive your class through the run_ops(capacity, ops) driver already in the scaffold (do not modify it). Each op is ("get", key), ("put", key, value) or ("get_stale",), and the driver records one output per op, with None for a put. Examples run_ops(2, [("put", 1, 10), ("put", 2, 20), ("get", 1), ("get_stale",), ("put", 3, 30), ("get", 2), ("get", 3)]) # [None, None, 10, 2, None, -1, 30] # get(1) refreshes key 1, so key 2 is the stale one and gets evicted by put(3, 30) run_ops(2, [("get_stale",), ("put", 1, 1), ("put", 2, 2), ("put", 1, 99), ("put", 3, 3), ("get", 1), ("get", 2), ("get_stale",)]) # [-1, None, None, None, None, 99, -1, 3] # get_stale on an empty cache is -1; updating key 1 refreshes it, so put(3, 3) # evicts key 2; after get(1) the least-recently-used key is 3 Constraints 1 <= capacity <= 50000. Up to \(2 \times 10^5\) operations. Keys and values are non-negative integers, so -1 is unambiguous. Every operation must run in \(O(1)\) time. Any design that scans a list to find or refresh recency order is \(O(capacity)\) per operation and will not finish the largest hidden test.

Rate this problem

Language:

Python 3.12 C++23

run_ops

from typing import Any

class LRUCache:
    def __init__(self, capacity: int) -> None:
        """Cache holding at most capacity entries, evicting the least
        recently used key when a new insert would exceed capacity."""
        # Your code here
        pass

def get(self, key: int) -> int:
        """Return the value under key and mark it most recently used,
        or -1 if the key is absent."""
        # Your code here
        pass

def put(self, key: int, value: int) -> None:
        """Insert or update key (updates also refresh recency), evicting
        the least-recently-used key first if the cache is full."""
        # Your code here
        pass

def get_stale(self) -> int:
        """Return the least-recently-used key without evicting it and
        without changing recency, or -1 if the cache is empty."""
        # Your code here
        pass

# Test driver: applies ops to a fresh cache. Do not modify.
def run_ops(capacity: int, ops: list[tuple[Any, ...]]) -> list[int | None]:
    cache = LRUCache(capacity)
    out = []
    for op in ops:
        if op[0] == "get":
            out.append(cache.get(op[1]))
        elif op[0] == "put":
            cache.put(op[1], op[2])
            out.append(None)
        else:
            out.append(cache.get_stale())
    return out

Rate this problem