Your question is LRU Caching Mechanism. 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.
Shutterfly Photos may repeatedly request recently viewed photo metadata. Implement an in-memory Least Recently Used (LRU) cache that supports get and put operations in O(1) average time.
The cache has a fixed positive capacity. A successful get makes the key most recently used. Inserting or updating a key with put also makes it most recently used. When inserting a new key would exceed capacity, evict the least recently used key.
Implement lru_cache_operations(capacity, operations), where capacity is an integer and operations is a list of commands. Each command is either ['get', key] or ['put', key, value]. Keys and values are integers. Return a list containing the result of every get command in order. Return -1 for a missing key. put commands produce no output.
Use a hash map and a doubly linked list. The list should maintain entries from least recently used to most recently used.
def lru_cache_operations(capacity, operations):