Data Structures

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.

Every pricing service ends up with a cache in front of it: symbol metadata, curve snapshots, reference data that is expensive to fetch and mostly read. The classic interview version is the LRU cache, and interviewers like to bolt on a twist once the first version works. Here the twist is announced up front, so design for it.

Implement a class LRUCache(capacity) with 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.

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 recorded for puts.

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: Pythonrun_ops

class LRUCache:
    def __init__(self, capacity):
        """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):
        """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, value):
        """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):
        """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, ops):
    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

Sample tests

Run your code to check it against the sample tests. Results appear here.

Next in Quant Dev 50Ring Buffer From ScratchData Structures