Skip to content
Katabench
Try free

Fewest Cache Fetches

Hard About 45 min Free, no account needed

Use tomorrow's requests to find the smallest possible number of cache misses today.

The brief

A replay tool has the complete request log from a finished job. It wants to measure how few fetches a cache could have made with perfect knowledge of the remaining requests.

Implement int Solve(int[] requests, int capacity). The cache starts empty and can hold at most capacity distinct item IDs. Process requests in their given order:

  • If the requested item is cached, serve it without a fetch.
  • Otherwise, fetch it once. If capacity is positive, the fetched item must enter the cache. When the cache is full, evict a currently cached item first.
  • With capacity zero, every request requires a fetch and nothing is retained.

You may choose evictions using the entire log. You cannot reorder requests, prefetch an item, or bypass insertion on a miss. Return the minimum possible total number of fetches.

For Solve([1, 2, 3, 1, 2, 3], 2), return 4. Fetch 1 and 2. To load 3, evict 2; the next request for 1 is then a hit. Fetch 2, evict 1, and serve the final 3 from cache. That costs four fetches. Evicting the least recently requested item at every miss would cost six.

For Solve([8, 8, 8], 0), return 3. With capacity 1, the same log needs only 1 fetch. An empty log returns 0.

There are at most 200,000 requests, 0 <= capacity <= 200,000, and IDs may be any signed 32-bit integer. IDs identify items; their numeric order has no significance. Do not change the request array.

Starter code

C#
public class Solution
{
    public int Solve(int[] requests, int capacity)
    {
        // Return the minimum fetch count with the complete future log available.
        throw new System.NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Greedy algorithms
Make the locally best choice when an exchange argument proves it stays globally optimal.
Heaps and priority queues
Pull the smallest or largest pending item cheaply for top-k, scheduling and eviction.

Related katas