Build an LRU Cache | Dataford Interview Questions

SailPoint IdentityNow services may cache frequently requested identity data while limiting memory usage. Implement a fixed-capacity least recently used cache that supports get and put operations in O(1) average time.

The cache must evict the least recently used key whenever an insertion exceeds its capacity. A successful get and every put, including an update to an existing key, make that key the most recently used.

Formal Specification

Implement lru_cache(capacity, operations).

capacity is a positive integer.
operations is a list of operations. Each operation is either ['get', key] or ['put', key, value].
Keys are integers, and values are integers.
Return a list containing the result of every get operation, in order.
Return -1 for a missing key.
put operations do not contribute an item to the returned list.

Constraints

1 <= capacity <= 10^5
1 <= len(operations) <= 2 * 10^5
0 <= key <= 10^9
-10^9 <= value <= 10^9
Every operation is either ['get', key] or ['put', key, value]

Function Signature

def lru_cache(capacity, operations):

Your question is Build an LRU Cache. 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