LRU Cache, Then Extend It

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 {
public:
    explicit LRUCache(std::size_t capacity);
    long long get(long long key);
    void put(long long key, long long value);
    long long get_stale() const;
};

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 std::optional<long long> per op: the result of a get or get_stale, and std::nullopt for a put.

Examples

LRUCache cache(2);
cache.put(1, 10);
cache.put(2, 20);
cache.get(1);        // 10, and key 1 is now the most recently used
cache.get_stale();   // 2, the key the next new insert evicts
cache.put(3, 30);    // evicts key 2
cache.get(2);        // -1
cache.get(3);        // 30

LRUCache other(2);
other.get_stale();   // -1, the cache is empty
other.put(1, 1);
other.put(2, 2);
other.put(1, 99);    // an update refreshes key 1
other.put(3, 3);     // so this evicts key 2
other.get(1);        // 99
other.get(2);        // -1
other.get_stale();   // 3

Constraints

• 1 <= capacity <= 50000.
• Up to \(2 \times 10^6\) 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.