Count LRU Cache Misses
A virtual memory management system use
least-recently-Used (LRU) cache.
When a requested memory page is not in the cache and the cache is full,
the page that was
least-recently-used should be removed from the cache to make room for the requested page.
If the cache is not full, the requested page can simply be added to the cache and considered the
most-recently-used page in the cache.
A given page should occur at most once in the cache.
Given the maximum size of the cache and a list of page requests,write an algorithm to calculate the number of cache misses. A cache miss occurs when a page is requested and isn't found in the cache.
int lruCacheMisses(int num, List<Integer> pages, int maxCacheSize)
The input consists of three arguments:
num : an
integer representing the number of pages
pages : a
list of integers representing the pages requested
maxCacheSize : an
integer representing the size of the cache
integer for the number of cache misses.
The cache is initially empty and the list contains pages numbered in the range
1-50. A page at index
"i" in the list is requested before a page at index
0 <= i < num
Cache state as requests come in ordered longest-time-in-cache to shortest-time-in-cache: 1* 1,2* 2,1 1,3* 3,1 1,2* Asterisk (*) represents a cache miss. Hence, the total number of a cache miss is `4`.