Measure LRU Cache Hits and Misses for an Access Workload

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

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.

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.

LRU Cache Hit and Miss Counter

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

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

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.

Hints

1. Recency changes on a hit too: keeping only insertion order is insufficient when an existing key is accessed again.
2. Track the ordering needed to identify the next eviction without scanning the entire cache.
3. Handle capacity zero separately: nothing is ever stored, so every request is a miss.

Approach

Simulate the cache with a recency-ordered hash structure (an ordered dictionary, or a hash map pointing into a doubly linked list). The invariant is that the structure holds exactly the cached keys, ordered from least to most recently used, and never more than capacity keys. On each request, a hash lookup decides hit or miss in expected O(1). A hit moves the key to the most-recent end, which is what distinguishes LRU from FIFO. A miss inserts the key at the most-recent end, first removing the key at the least-recent end if the cache already holds capacity keys; this is exactly the eviction rule, so the simulated contents match the real cache after every request and the counters are exact. Edge cases: capacity zero stores nothing, so the answer is [0, len(requests)]; an empty workload returns [0, 0]; a cache that is exactly full evicts only when a new key arrives, never on a hit.

• Time complexity: O(n) expected
• Space complexity: O(min(capacity, n))