Katkat
Back

Add TTL to an LRU cache

ByteDanceSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This question evaluates a candidate's understanding of cache design, LRU eviction policies, time-to-live (TTL) semantics, appropriate data structures, time complexity reasoning, and concurrency control.

Design an in-memory LRU cache and explain how to extend it with TTL support.

Requirements:

  • get(key) returns the value if the key exists and has not expired; otherwise it returns a cache miss.
  • put(key, value, ttl) inserts or updates an entry with an expiration time.
  • When capacity is exceeded, evict the least recently used item.
  • Expired items should never be returned, and the design should explain how they are removed.
  • Discuss the data structures, time complexity, cleanup strategy, and concurrency considerations.