Find Bugs in an LRU Cache
Company: ZipHQ
Role: Backend Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
# Find Bugs in an LRU Cache
The Java class below is intended to implement a least-recently-used cache. A successful `get` and every `put` should make the key most recently used. Inserting a new key at capacity should evict the least recently used key.
```java
class LRUCache {
private final int capacity;
private final LinkedHashMap<Integer, String> cache;
LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new LinkedHashMap<>();
}
String get(int key) {
if (!cache.containsKey(key)) return null;
String value = cache.remove(key);
cache.put(key, value);
return value;
}
void put(int key, String value) {
if (cache.containsKey(key)) {
cache.put(key, value);
} else {
if (cache.size() >= capacity) {
Iterator<Map.Entry<Integer, String>> it = cache.entrySet().iterator();
Map.Entry<Integer, String> last = null;
while (it.hasNext()) last = it.next();
if (last != null) cache.remove(last.getKey());
}
cache.put(key, value);
}
}
}
```
Find every behavior that violates the specification, give a minimal failing test for each independent defect, and propose a corrected implementation. Explain which ordering mode `LinkedHashMap` uses and why merely compiling is not enough to validate recency semantics.
### Constraints & Assumptions
- Capacity is a positive integer.
- Keys are integers and values are non-null strings for this exercise.
- `get` returns `null` for a miss without changing order.
- Expected `get` and `put` time is constant on average.
### Clarifying Questions to Ask
- Should zero capacity be rejected or treated as a cache that stores nothing?
- Is the implementation required to be thread-safe?
- May library-provided access ordering and eviction hooks be used?
- Should updating an existing value count as access? The specification says yes.
### Hints
- Track the order after inserting two keys, reading the older key, and inserting a third.
- Track the order after updating the older key without reading it.
- Distinguish the first and last entries in insertion order.
### What a Strong Answer Covers
- Independent recency and eviction defects, each backed by a focused test.
- A correction whose ordering semantics are explicit.
- Capacity, complexity, and concurrency considerations.
- An explanation of why the fix preserves the invariant after every operation.
### Follow-up Questions
1. How would you make this cache safe under concurrent access?
2. How would weighted entries change eviction?
3. How would you add TTL without letting expired entries corrupt LRU order?
Quick Answer: Find the behavioral defects in a Java LRU cache built with LinkedHashMap and provide minimal failing tests. Correct access ordering, update recency, least-recently-used eviction, and constant-time average operations while explaining why compilation alone cannot validate cache semantics.