Skip to question
ASIC.FYI

Q217FreeFirmware

Expiring Key-Value Store

Difficulty
Hard
Topic
Data Structures
Language
SV
Interview prompt

Question

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.

Starting point

Question code

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
Reviewed example

Trace one case

Input
t=10: put(key=7, value=0xAA, ttl=5)
t=14: get(7)
t=15: get(7)
Expected output
t=14 -> 0xAA
t=15 -> MISS

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

What to cover

Requirements

  1. Define precisely whether ttl=1 survives the current cycle or the next cycle.
  2. Updating an existing key replaces both its value and expiration time.
  3. Ignore stale expiration records created by prior updates to the same key.
  4. Make expiration work proportional to entries that actually expire plus scheduling overhead, not a full-map scan.
Continue practicing
Q266 · Data StructuresLongest-Prefix-Match Routing TableQ264 · Data StructuresExact Streaming MedianQ273 · Data StructuresReturn the first unique value in a stream