Skip to question
ASIC.FYI

Q142FreeComputer Architecture

Implement a simple least-recently-used cache

Difficulty
Medium
Topic
Data Structures
Language
SV
Interview prompt

Question

Implement a fixed-capacity least-recently-used cache. A successful lookup and every insertion or update make the key most recently used; inserting beyond capacity evicts the least-recently-used key.

Capacity-two cache trace showing recency refresh and least-recently-used eviction
A successful lookup refreshes key 1, so inserting key 3 evicts key 2.
Starting point

Question code

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

Trace one case

Input
capacity=2; put(1,10), put(2,20), get(1), put(3,30)
Expected output
get(1)=10; get(2)=MISS; keys from LRU to MRU=[1,3]

Looking up key 1 refreshes it, so the subsequent insertion evicts key 2.

What to cover

Requirements

  1. get(key, value) returns 0 on a miss and 1 with the stored value on a hit.
  2. Updating an existing key changes both its value and recency.
  3. Keep the least-recently-used key at the front and the most-recently-used key at the back.
  4. Treat a nonpositive capacity as zero, making put a no-op.
Continue practicing
Q143 · Data StructuresMake the least-recently-used cache O(1)Q208 · Data StructuresInsert, remove, and sample in average O(1)Q229 · Data StructuresMaintain the top-K most frequent stream values