Design and Implement a Fixed-Capacity LRU Cache with Constant-Time Operations
Company: AMD
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Onsite
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.
```hint 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.
```
### 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?
### What a Strong Answer Covers
- A combination of data structures that gives constant-time `get`, `put` and eviction, with justification
- Correct recency updates on both operations, eviction order, and updates of existing keys when the cache is full
- Clean, compilable code with sound memory and iterator handling
- A test sequence that exercises eviction and recency changes
- The ability to extend the design under follow-ups such as concurrency, expiry and size-based capacity
### 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?
Overview: 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.
Read the full AMD Software Engineer interview experience this question came from