Cache misses under LRU eviction
An LRU (least-recently-used) cache holds at most items. Starting empty, it receives the access sequence An access is a miss if the item is not currently cached (a miss on a full cache evicts the least-recently-used item to make room). How many of the accesses are misses?
Show hints (2)+
- Track the cache as an ordered list; every hit moves that item to most-recently-used, and a full-cache miss evicts the least-recently-used.
- Watch item : it hits at step 4 but misses at step 8 because it was evicted at step 7.
Answer
Reveal answer →Final answer
7
Create a free account to see the full worked solution and track your progress.
Interview format: Hedge Fund Quant, Betting Game Rounds