Katkat
Back

Design and Implement a Fixed-Capacity LRU Cache with Constant-Time Operations

AMDSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Design and implement a fixed-capacity least-recently-used cache whose get and put operations run in constant time, while answering follow-up probes during coding. It tests data structure composition, careful iterator handling, eviction edge cases, and extensions such as thread safety and expiry.

Design and implement a least-recently-used (LRU) cache with a fixed capacity. The interviewer asked follow-up questions while you were writing the code.

The cache stores key-value pairs and supports two operations:

  • get(key): return the value stored for key if it is present, and otherwise report a miss. A successful get counts as a use of that key.
  • put(key, value): insert key with value, or update its value if it is already present; either way it counts as a use. If inserting a new key would make the cache hold more than its capacity, first evict the least recently used key.

Constraints and Clarifications

  • Both operations should run in constant time on average.
  • The specific follow-ups asked during the interview were not reported; the follow-up questions below are representative probes of the same design.

Clarifying Questions

  • What should get return on a miss: a sentinel value, an empty optional, or an exception?
  • What are the key and value types? Should the cache be generic over them?
  • How should a capacity of zero behave?
  • Will the cache be used from multiple threads?

Hints

Hint 1

Two jobs, two structures: One part of the cache must find a key quickly; another must keep keys in order of recent use and move any one of them to the front cheaply. Consider combining structures.

Follow-up questions

  • Make the cache safe for concurrent use. What is the simplest correct approach, and how would you reduce lock contention?
  • Add a time-to-live to each entry. How are expired entries removed?
  • Capacity is now measured in bytes rather than entries, and values vary in size. What changes?
  • Why can LRU be a poor policy for some workloads, such as a large one-time sequential scan, and what would you use instead?