In-memory KV Cache with Hit Count and Unit Tests

Question: Implement an In-memory KV Cache with Hit Count and Unit Tests Implement an in-memory key-value cache that supports get/put and maintains hit count statistics. Requirements Design a class KVCache: put(key: str, value: str) -> None If key exists, update its value. If the cache is full, evict one key according to an eviction policy you choose (e.g., LRU). get(key: str) -> Optional[str] If key exists, return its value and increment hit_count[key] += 1. Otherwise return None. hit_count(key: str) -> int Return how many times this key has been hit by get (misses do not count). If the key does not exist / never existed, return 0. Constraints Initialize with a positive integer capacity; eviction is required when full. Keys and values are strings. No persistence / no distribution required. State your target time complexity (e.g., amortized O(1) for both ops). Unit Tests Write unit tests that cover at least: Basic put/get behavior. Hit count increments on hits and does not change on misses. Behavior under eviction: evicted keys return None; hit count matches your definition. Updating an existing key with repeated put. Scale Number of operations N: 1 <= N <= 200000 capacity: 1 <= capacity <= 100000 I/O (online-judge style) Input: First line: capacity Q Next Q lines: PUT key value GET key HIT key Output: For each GET: print the value on hit, otherwise NULL For each HIT: print the integer hit count Example Input 2 9 PUT a 1 PUT b 2 GET a HIT a GET c HIT c PUT c 3 GET b GET c Output 1 1 NULL 0 NULL 3