Your question is LRU Cache O(1) Average. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Google services such as Google Drive may need to evict the least recently used entries when an in-memory cache reaches capacity. Design an LRU cache that supports get and put in O(1) average time.
Implement lru_cache(capacity, operations). The cache stores integer keys and values. Each operation is either ['get', key] or ['put', key, value]. Return the results of all get operations in order. A missing key returns -1.
A successful get marks the key as most recently used. Inserting a new key also marks it as most recently used. Updating an existing key changes its value and marks it as most recently used. If insertion exceeds capacity, evict the least recently used key.
capacity, a positive integer, and operations, a list of operation lists.get operations.get and put operation must run in O(1).def lru_cache(capacity, operations):