LRU Cache with High Cache-Miss Follow-up

Problem: Implement an LRU Cache Implement a fixed-capacity LRU, or Least Recently Used, cache. The cache supports the following operations: get(key): If key exists in the cache, return its value and mark the key as recently used. Otherwise, return -1. put(key, value): If key already exists, update its value and mark it as recently used. If key does not exist, insert the key-value pair. If the cache is full, evict the least recently used item. Requirements: Both get and put should run in average O(1) time. Input Format The first line contains an integer capacity, the cache capacity. The second line contains an integer n, the number of operations. The next n lines each contain one operation: GET key PUT key value Output Format For each GET operation, print one line containing the result. Constraints 1 <= capacity <= 10^5 1 <= n <= 2 * 10^5 0 <= key, value <= 10^9 Example Input: 2 6 PUT 1 1 PUT 2 2 GET 1 PUT 3 3 GET 2 GET 3 Output: 1 -1 3 Follow-up If the cache miss rate is high in production, how would you diagnose and optimize it? Example Input 2 6 PUT 1 1 PUT 2 2 GET 1 PUT 3 3 GET 2 GET 3 Output 1 -1 3