# 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`

##### 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 = {}
14            self.tail = self.DLL(0,0)
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
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
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
``````