LRU Cache Statistics- OYO Prism Online Assessment NSUT

Problem Preview

"A computer system maintains an **LRU (Least Recently Used)** cache capable of storing at most **K** pages. You are given a sequence of page requests. Initially, the cache is empty. For every requested page: * If the page is already present in the cache, it is a **cache hit**. * Mark it as the most recently used page. * Otherwise, it is a **cache miss**. * If the cache is not full, insert the page. * Otherwise, remove the least recently used page and insert the requested page. After processing all requests, determine the total number of cache hits and cache misses. ### Input Format * The first line contains two integers `K` and `N` — the cache capacity and the number of page requests. * The second line contains `N` integers representing the page requests. ### Output Format Print two integers: ``` hits misses ``` ### Constraints * `1 ≤ K ≤ 10^5` * `1 ≤ N ≤ 2 × 10^5` * `1 ≤ pages[i] ≤ 10^9` ### Sample Input 1 ``` 3 8 1 2 3 1 4 5 1 2 ``` ### Sample Output 1 ``` 2 6 ``` ### Explanation | Request | Cache | Result | | ------- | ----- | ------ | | 1 | 1 | Miss | | 2 | 1 2 | Miss | | 3 | 1 2 3 | Miss | | 1 | 2 3 1 | Hit | | 4 | 3 1 4 | Miss | | 5 | 1 4 5 | Miss | | 1 | 4 5 1 | Hit | | 2 | 5 1 2 | Miss | Hence, there are **2 hits** and **6 misses**. --- ### Sample Input 2 ``` 2 6 1 2 3 4 5 6 ``` ### Sample Output 2 ``` 0 6 ``` ### Explanation Every request is for a new page, so every access results in a cache miss."