KV Cache with Hit Count

Problem: Implement a KV Cache with Hit Count Implement an in-memory KV cache with get and put, and maintain a hit count per key that increments on every successful get. Functional Requirements put(key, value): insert or update a key. get(key): If key exists, return the value and increment hit_count[key] += 1. If key does not exist, return NULL. The cache has a maximum capacity. When full, evict entries according to a policy you choose (explain it in the interview, e.g., LRU/LFU/Random). I/O Format (for coding) Read from stdin: Line 1: two integers capacity and q (#operations). Next q lines: each is an operation: PUT key value GET key For each GET, print one line: the value if hit, otherwise NULL. Constraints 1 <= capacity <= 1e5 1 <= q <= 2e5 key and value are strings without spaces Target amortized time close to O(1) (depending on eviction policy) Example Input 2 7 PUT a 1 PUT b 2 GET a PUT c 3 GET b GET a GET c Output 1 NULL 1 3 The example uses LRU eviction: inserting c evicts b. Example Input 2 7 PUT a 1 PUT b 2 GET a PUT c 3 GET b GET a GET c Output 1 NULL 1 3