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

DescriptionQ217

Page ↗

Q217FWDVASIC interview problem

Expiring Key-Value Store

TechniquesDVFWArchTTLPriority queueLazy invalidation

DifficultyHard

TopicData Structures

LanguageSystemVerilog

Requirements4 checkpoints

Problem

Design a cycle-based key-value store in which every entry has a time-to-live (TTL). Expired values must never be returned, and expiration processing must avoid scanning the entire map every cycle.

Class declarationSystemVerilog

class ExpiringStore #(type key_t = int, type value_t = int);
  void put(key_t key, value_t value, int unsigned ttl);
  bit get(key_t key, output value_t value);
  bit erase(key_t key);
  void tick();
endclass

Example input and output

Use this case to check your interpretation

Input

t=10: put(key=7, value=0xAA, ttl=5)
t=14: get(7)
t=15: get(7)

Output

t=14 -> 0xAA
t=15 -> MISS

Explanation

The value is readable before its absolute expiry time and is removed or ignored exactly at expiry.

Requirements (4)

Define precisely whether ttl=1 survives the current cycle or the next cycle.
Updating an existing key replaces both its value and expiration time.
Ignore stale expiration records created by prior updates to the same key.
Make expiration work proportional to entries that actually expire plus scheduling overhead, not a full-map scan.