Code RoomCache eviction misses
HardPrep Room Coding #4869

Cache eviction misses

CodingDistributed systemsAlgorithms & data structuresMid–Staff~35 min

A build farm replays a recorded fetch log through a local artifact cache that holds at most slot_count artifacts and starts empty. requests[i] is the artifact fetched at step i. Fetching an artifact that is already resident costs nothing. Fetching an absent one is a miss: it gets loaded, and if every slot is already full then exactly one resident artifact is dropped to make room. Because the entire log was recorded before this replay begins, you may choose each drop knowing every fetch still to come. Return the fewest misses the replay can end with. slot_count may be 0, in which case every fetch misses, and the log may be empty. Dropping whichever artifact went unused the longest is not always the fewest.

Implement
fewest_fetch_misses(requests: list[int], slot_count: int) → int
Examples
in[[1,2,3,1,2,3],2]out4
in[[4,4,4,4],1]out1
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 35 min
InputExpectedGot
[[1,2,3,1,2,3],2]4not run yetsample
[[4,4,4,4],1]1not run yetsample