Your question is LRU 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.
Twitch mobile clients may cache recently viewed chat metadata to reduce repeated work while users switch between channels. Implement a fixed-capacity least-recently-used cache that supports constant-time retrieval, updates, and eviction.
The cache must process operations in order. A get returns the value for a key and marks that key as most recently used. A missing key returns -1. A put inserts or updates a key, marks it as most recently used, and evicts the least recently used key if capacity is exceeded.
Implement lru_cache_operations(capacity, operations), where capacity is a positive 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 results of all get commands in their original order. put commands do not add an output.
Use a custom data structure. Do not use Python's built-in cache or ordered dictionary implementations.
def lru_cache_operations(capacity, operations):