Measure LRU Cache Hits and Misses for an Access Workload
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Measure cache hits and misses for an access workload handled by a least recently used (LRU) cache.
### Function Contract
Implement `lru_hit_miss_counts(capacity, requests) -> list[int]`.
The cache starts empty. `requests` lists integer keys accessed in order. Apply these explicit workload rules:
- Accessing a cached key is a hit and makes that key most recently used.
- Accessing an uncached key is a miss. If capacity is positive, insert it as most recently used, evicting the least recently used key first if the cache is full.
- At capacity zero, every request is a miss and nothing is stored.
Return `[hit_count, miss_count]`. These counters determine the hit ratio `hit_count / n` and miss ratio `miss_count / n` for a nonempty workload of length `n`. For an empty workload, return `[0, 0]`; no ratio is defined.
### Constraints and Clarifications
- `0 <= capacity <= 200000`.
- `0 <= len(requests) <= 200000`.
- Each key is an integer from `0` through `1000000000`.
- Capacity counts keys, and every key occupies one slot.
- There is no expiration, prefetching, or write policy in this exercise.
- Aim for expected `O(n)` total time with `O(min(capacity, n))` cache storage.
### Examples
```text
capacity = 2
requests = [1, 2, 1, 3, 2, 3]
Output: [2, 4]
```
The repeated accesses to `1` at the third request and `3` at the last request are hits. The hit ratio is `2/6`, and the miss ratio is `4/6`.
```text
capacity = 0
requests = [5, 5, 5]
Output: [0, 3]
```
```hint Recency changes on a hit too
Keeping insertion order is insufficient when an existing key is accessed again. Track the ordering needed to identify the next eviction without scanning the entire cache.
```
Overview: Simulate an LRU cache with hit and miss counters, correct recency updates, bounded capacity, and explicit empty-workload behavior.
Read the full LinkedIn Software Engineer interview experience this question came from
Measure cache hits and misses for an access workload handled by a least recently used (LRU) cache.
Implement `lru_hit_miss_counts(capacity, requests)`, which returns a list of two integers `[hit_count, miss_count]`.
The cache starts empty. `requests` lists integer keys accessed in order. Apply these rules to each request:
- Accessing a key that is currently cached is a **hit**, and that key becomes the most recently used.
- Accessing a key that is not cached is a **miss**. If `capacity` is positive, the key is inserted as the most recently used; if the cache already holds `capacity` keys, the least recently used key is evicted first.
- When `capacity` is zero, every request is a miss and nothing is ever stored.
Return `[hit_count, miss_count]` in that order. For a nonempty workload of length `n`, these determine the hit ratio `hit_count / n` and miss ratio `miss_count / n`. For an empty workload, return `[0, 0]` (no ratio is defined).
Capacity counts keys: every key occupies exactly one slot. There is no expiration, prefetching, or write policy. Both counts are at most 200000, so they fit in a 32-bit signed integer.
### Example 1
```text
capacity = 2
requests = [1, 2, 1, 3, 2, 3]
Output: [2, 4]
```
The accesses to `1` at the third request and to `3` at the last request are hits (the hit on `1` makes it most recent, so inserting `3` evicts `2`). The hit ratio is `2/6` and the miss ratio is `4/6`.
### Example 2
```text
capacity = 0
requests = [5, 5, 5]
Output: [0, 3]
```
With capacity zero nothing is stored, so every request misses.
### Constraints
- `0 <= capacity <= 200000`
- `0 <= len(requests) <= 200000`
- Each key is an integer from `0` through `1000000000`.
- Aim for expected `O(n)` total time with `O(min(capacity, n))` cache storage.
Constraints
- 0 <= capacity <= 200000
- 0 <= len(requests) <= 200000
- Each key is an integer from 0 through 1000000000
- Capacity counts keys; every key occupies one slot
- No expiration, prefetching, or write policy
- Return [hit_count, miss_count]; an empty workload returns [0, 0]
Examples
Input: (2, [1, 2, 1, 3, 2, 3])
Expected Output: [2, 4]
Explanation: Source example: the hit on 1 refreshes it, so 3 evicts 2; later 2 evicts 1 and the final 3 hits.
Input: (0, [5, 5, 5])
Expected Output: [0, 3]
Explanation: Source example: capacity zero stores nothing, so every request misses.
Hints
- Recency changes on a hit too: keeping only insertion order is insufficient when an existing key is accessed again.
- Track the ordering needed to identify the next eviction without scanning the entire cache.
- Handle capacity zero separately: nothing is ever stored, so every request is a miss.
Community answers
Answer by rzcsong
// 7:45PM - 9:23PM
// Design a LRU cache
// Need a hashMap to find the requests
// Need a double LinkedList to track the order
// Head -> Least used request
// Tail -> Latest used request
// hit, miss, count
//capacity = 2 requests = [1, 2, 1, 3, 2, 3]
//hit: 2
//miss: 4
//count: 2
//map: {3 : Node(3)}, {2: Node(2)}
// head - 2 - 3 - tail
//capacity = 0
//
class Solution {
public int[] lru_hit_miss_counts(int capacity, int[] requests) {
int hit = 0;
int miss = 0;
int count = 0;
Map map = new HashMap<>();
Node head = new Node(0, null, null);
Node tail = new Node(0, head, null);
head.next = tail;
for (int i = 0; i < requests.length; i++) {
if (capacity <= 0) {
miss++;
continue;
}
if (!map.containsKey(requests[i])) {
Node latestRecentUsedNode = new Node(requests[i], null, null);
if (count < capacity) {
insertToTail(latestRecentUsedNode, tail);
count++;
} else {
int valToRemove = removeLeastUsed(head);
map.remove(valToRemove);
insertToTail(latestRecentUsedNode, tail);
}
map.put(requests[i], latestRecentUsedNode);
miss++;
} else if (map.containsKey(requests[i])) {
Node requestNode = map.get(requests[i]);
Node prevNode = requestNode.prev;
Node nextNode = requestNode.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
insertToTail(requestNode, tail);
hit++;
}
}
return new int[] {hit, miss};
}
private void insertToTail(Node latestToInsert, Node tail) {
Node latestUsed = tail.prev;
latestUsed.next = latestToInsert;
latestToInsert.prev = latestUsed;
latestToInsert.next = tail;
ta