1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ142

Page ↗

Q142FWArchASIC interview problem

Implement a simple least-recently-used cache

TechniquesSystemVerilogLRUAssociative arrayQueue

DifficultyMedium

TopicData Structures

LanguageSystemVerilog

Requirements4 checkpoints

Problem

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.

Class declarationSystemVerilog

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

Example input and output

Use this case to check your interpretation

Input

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

Output

get(1)=10; get(2)=MISS; keys from LRU to MRU=[1,3]

Explanation

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

Requirements (4)

get(key, value) returns 0 on a miss and 1 with the stored value on a hit.
Updating an existing key changes both its value and recency.
Keep the least-recently-used key at the front and the most-recently-used key at the back.
Treat a nonpositive capacity as zero, making put a no-op.