Skip to question

Q094FreeComputer 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.

Candidate starting point

Implementation scaffold

// Implement here: Explain why the full predicate is captured before insertion.

class LRUCache;
  int capacity;
  int value_by_key[int];
  int recency[$]; // LRU at front, MRU at back

  function new(int capacity);
    this.capacity = (capacity > 0) ? capacity : 0;
  endfunction

  function void touch(int key);
    // Implement here: move this existing key to MRU.
  endfunction

  function bit get(int key, output int value);
    // Implement here: report a hit and return its value while updating recency.
  endfunction

  function void put(int key, int value);
    int evict_key;
    bit full_before_insert;
    // Implement here: insert or update and enforce capacity.
  endfunction
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
Q139 · Data StructuresMake the least-recently-used cache O(1)HardQ195 · Data StructuresAssociative-array traversalEasyQ169 · Data StructuresInsert, remove, and sample in average O(1)MediumQ203 · Data StructuresImplement an O(1) LRU cacheHardPQ071 · Data StructuresDynamic arrays and queuesEasy