Your question is LRU Cache From Scratch. 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.
The AWS Inferentia2 inference path in Annapurna Labs (U.S.) may cache recently used results under a fixed memory budget. Implement an LRU cache from scratch so lookups, insertions, updates, and evictions are efficient.
Define lru_cache(operations, capacity), where operations is a list of commands:
['put', key, value]: insert or update key with value. An updated key becomes most recently used.['get', key]: return the value for key, or -1 if absent. A successful lookup becomes most recently used.Return a list containing the result of every get operation, in order. Use a hash map and a doubly linked list. Do not use Python's cache or ordered-map utilities.
operations, a list of operation lists, and capacity, a positive integer.get operations.def lru_cache(operations, capacity):