Katkat
Back

Implement Expiring LRU Cache

ByteDanceSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates skill in designing and implementing efficient in-memory caching data structures, testing understanding of LRU eviction, per-entry TTL expiration, and the use of hash maps and linked lists for O(1) operations.

Implement an in-memory key-value cache with least-recently-used eviction and per-entry expiration.

The cache has a fixed positive capacity. Each inserted key has a time-to-live value. Once an entry expires, it should behave as if it does not exist and should be removed from the cache when encountered.

Design a class with the following operations:

ExpiringCache(int capacity)
int get(int key, int now)
void put(int key, int value, int ttl, int now)

Rules:

  • put(key, value, ttl, now) inserts or updates key with value.
  • The entry expires at time now + ttl.
  • get(key, now) returns the value if the key exists and has not expired; otherwise return -1.
  • Accessing a non-expired key through get makes it the most recently used entry.
  • Updating an existing non-expired key through put updates its value, expiration time, and recency.
  • If an existing key has already expired, treat the operation as inserting a new key.
  • If inserting a new entry causes the number of non-expired entries to exceed capacity, evict the least recently used non-expired entry.
  • Expired entries should be deleted when detected.

Target: make get and put run in O(1) average time, using an appropriate combination of a hash map and a doubly linked list.