Q143FreeComputer Architecture

Make the least-recently-used cache O(1)

Interview prompt

Question

Redesign the LRU cache so successful get, put, recency updates, and eviction all take average O(1) time.

Starting point

class LRUCacheO1;
  function new(int capacity);
  function bit get(int key, output int value);
  function void put(int key, int value);
endclass

Reviewed example

Input

capacity=2; put(1,10), put(2,20), get(1), put(3,30)

Expected output

key 2 is evicted; node-map entries are {1,3}; LRU-to-MRU list is [1,3]

Direct node lookup and constant-time unlink/append preserve the same LRU behavior without a scan.

What to cover

Preserve the lookup, update, insertion, and eviction behavior of the simple LRU cache.
Map each key directly to its recency node.
Unlink and append a node without scanning the cache.
Evict the head/LRU key from the value map, node map, and linked list together.

Continue practicing