Your question is Custom Cache Eviction Policy. 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.
Persistent API services need a bounded in-memory cache for frequently requested responses. Implement a cache that evicts the least recently used entry whenever inserting a new entry would exceed its capacity.
The cache must support get and put operations in O(1) average time. A successful get marks the entry as most recently used. Updating an existing key with put also marks it as most recently used.
Implement process_cache(capacity, operations). capacity is a positive integer. operations is a list containing either ['get', key] or ['put', key, value], where keys and values are integers. Return a list containing the result of every get, in the same order. Return -1 when a key is absent. put operations do not add an item to the returned list.
Use a hash map combined with a doubly linked list. The list must maintain entries from least recently used to most recently used.
def process_cache(capacity, operations):