ORIGINAL CODING QUESTION
Cache misses in a request trace
An initially empty cache holds at most capacity keys. Every request makes its key most recently used. A missing key counts as one miss and is inserted, evicting the least recently used key if full. Return the miss count.
Original exercise · medium. Editorial role relevance does not imply a company has asked this question.
Input and output
n capacity, then n integer keys.
Constraints
1 ≤ n ≤ 1000; 1 ≤ capacity ≤ 100; keys in [0,10000].
Example 1
Input
5 2 1 2 1 3 2
Output
4
Requests for 1, 2, 3 and the final 2 miss.
Example 2
Input
3 1 7 7 7
Output
1
Only the first request misses.
Explain your approach
Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?
Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.
Hint 1
Hits change eviction order.
Hint 2
Track keys by recency.
Hint 3
Remove an existing key before inserting at the most recent end.
Practice this question
Save your work privately, explain decisions and return to your revision queue.
Open practice workspaceBrowse the question library →