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

DescriptionQ143

Q143FWArchFollow-up to Q142ASIC interview problem

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

TechniquesSystemVerilogLRUDoubly linked listAssociative array

DifficultyHard

TopicData Structures

LanguageSystemVerilog

Requirements4 checkpoints

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

Class declarationSystemVerilog

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

Use this case to check your interpretation

Input

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

Output

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

Explanation

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

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.