Data Structures for Efficient Python Lookups | Dataford Interview Questions

An IBM watsonx request layer needs a bounded in-memory cache for reusable session state. Implement a least recently used, or LRU, cache that supports constant-time lookups, updates, and evictions.

Create lru_operations(capacity, operations). The capacity is a positive integer. Each operation is a list in one of these forms:

['get', key]: Return the value for key, or -1 if it is absent. A successful lookup marks the key as most recently used.
['put', key, value]: Insert or replace the value. The key becomes most recently used. If the cache exceeds capacity, remove the least recently used key. This operation produces no output.

Return a list containing the results of all get operations in their original order. Use a hash map and a doubly linked list, rather than scanning the cache to identify the least recently used entry.

Constraints

1 <= capacity <= 10^5
1 <= len(operations) <= 2 * 10^5
Keys and values are integers in the range [-10^9, 10^9]
Every operation is valid and has the required number of fields

Function Signature

def lru_operations(capacity, operations):

Your question is Data Structures for Efficient Python Lookups. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem