Amazon Online Assessment (OA) - 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.

1int lruCacheMisses(int num, List<Integer> pages, int maxCacheSize)

Input

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

Output

Return an integer for the number of cache misses.

Note

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 "i+1".

Constraints

0 <= i < num

Examples

Example 1:

Input:

num = 6

pages = [1,2,1,3,1,2]

maxCacheSize = 2

Output: 4
Explanation:
1  Cache state as requests come in ordered longest-time-in-cache to shortest-time-in-cache:
2
3  1*
4
5  1,2*
6
7  2,1
8
9  1,3*
10
11  3,1
12
13  1,2*
14
15  Asterisk (*) represents a cache miss. Hence, the total number of a cache miss is `4`.

Solution

This is basically the classic LRU Cache problem.

1from typing import List
2
3def lru_cache_misses(num: int, pages: List[int], max_cache_size: int) -> int:
4    class LRUCache:
5        class DLL:
6            def __init__(self, key, val):
7                self.key = key
8                self.val = val
9                self.next = None
10                self.prev = None
11        def __init__(self, capacity: int):
12            self.m = {}
13            self.head = self.DLL(0,0)
14            self.tail = self.DLL(0,0)
15            self.head.next = self.tail
16            self.tail.prev = self.head
17            self.size = 0
18            self.capacity = capacity
19        def get(self, key: int) -> int:
20            if key in self.m:
21                loc = self.m[key]
22                loc.prev.next = loc.next
23                loc.next.prev = loc.prev
24                self.head.next.prev = loc
25                loc.next = self.head.next
26                self.head.next = loc
27                loc.prev = self.head
28                return loc.val
29            else:
30                return -1
31        def put(self, key: int, value: int) -> None:
32            if key in self.m:
33                self.get(key)
34                self.m[key].val = value
35                return
36            self.size += 1
37            if self.size > self.capacity:
38                lru = self.tail.prev
39                del self.m[lru.key]
40                self.tail.prev.val = self.tail.val
41                self.tail.prev.next = None
42                self.tail = self.tail.prev
43                self.size -= 1
44            new_head = self.DLL(key, value)
45            self.head.next.prev = new_head
46            new_head.next = self.head.next
47            self.head.next = new_head
48            new_head.prev = self.head
49            self.m[key] = new_head
50
51    cache = LRUCache(max_cache_size)
52    misses = 0
53    for page in pages:
54        if cache.get(page) == -1:
55            misses += 1
56        cache.put(page, None)
57    return misses
58
59if __name__ == '__main__':
60    num = int(input())
61    pages = [int(x) for x in input().split()]
62    max_cache_size = int(input())
63    res = lru_cache_misses(num, pages, max_cache_size)
64    print(res)
65