Design an LRU Cache with a Constant-Time Average
Company: Confluent
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Onsite
# Design an LRU Cache with a Constant-Time Average
Design an in-memory cache with fixed positive capacity. Keys are unique strings and values are signed numbers. Support:
- `get(key)`: return the value and mark the key most recently used, or report a miss.
- `put(key, value)`: insert or update the key and mark it most recently used; if over capacity, evict the least recently used key.
- `get_average()`: return the arithmetic mean of values currently in the cache, or a documented empty result.
All three operations should take expected `O(1)` time. Explain invariants, numeric choices, and edge cases rather than relying on an ordered-map library as a black box.
### Constraints & Assumptions
- Capacity never changes after construction.
- Updating an existing key replaces its value and changes recency.
- The average covers current entries, not historical requests.
- Thread safety is not required for the initial design.
### Clarifying Questions to Ask
- Are values integers or floating point, and what precision is expected?
- Does a miss change recency or affect the average?
- What should `get_average` return for an empty cache?
- Are overflow and concurrent calls in scope?
### What a Strong Answer Covers
- A hash map paired with a doubly linked recency list
- A running sum updated on insert, replacement, and eviction
- Correct movement, unlinking, and eviction invariants
- Expected-time, space, precision, and overflow analysis
- Tests that check both recency and aggregate correctness
### Follow-up Questions
- How would you add TTL expiration without scanning the cache?
- How would a dynamic capacity change work?
- How would you make operations thread-safe and linearizable?
- What changes if values are vectors rather than scalars?
Overview: Design a fixed-capacity LRU cache whose get, put, and current-value average operations all run in expected constant time. Reason through map and recency-list invariants, running-sum updates, replacement and eviction edge cases, numeric precision, overflow, and tests that catch aggregate or ordering bugs.
Read the full Confluent Software Engineer interview experience this question came from
Community answers
Answer by djawalkar
Here is my implementation for the Concurrent LRU Cache with getAverage Operation implemented using Lock Striping,
package lrucachewithaverage;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
public class ConcurrentLRUCacheWithAverage {
// Doubly Linked List Node
private static class Node {
String key;
double value;
Node prev;
Node next;
Node(String key, double value) {
this.key = key;
this.value = value;
}
}
// A single, self-contained LRU Cache protected by its own lock
private static class Shard {
private final int capacity;
private final Map cache;
private final Node head;
private final Node tail;
final ReentrantLock lock;
double currentSum;
int currentCount;
Shard(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.lock = new ReentrantLock();
this.head = new Node("", 0.0);
this.tail = new Node("", 0.0);
head.next = tail;
tail.prev = head;
this.currentSum = 0.0;
this.currentCount = 0;
}
Double get(String key) {
Node node = cache.get(key);
if (node == null) return null;
moveToHead(node);
return node.value;
}
void put(String key, double value) {
Node existingNode = cache.get(key);
if (existingNode != null) {
currentSum = currentSum - existingNode.value + value;
existingNode.value = value;
moveToHead(existingNode);
} else {
if (currentCount == capacity) {
Node lruNode = tail.prev;
cache.remove(lruNode.key);
removeNode(lruNode);
currentSum -= lruNode.value;
currentCount--;
}
Node newNode = new Node(key,