Custom Data Structure Implementation | Dataford Interview Questions

Implement a solution for a specific data structure problem without using built-in libraries for Crypto backend code.

Implement an LRU cache from scratch. Use a custom hash table and doubly linked list, without dict, set, OrderedDict, or external libraries.

I/O Contract

Implement lru_cache(capacity, operations). Each operation is ['put', key, value] or ['get', key]. Return a list containing the result of every get, using -1 for a missing key. A successful get and every put mark the key as most recently used.

Constraints

1 <= capacity <= 10^5
1 <= len(operations) <= 5000
Each operation is either ['get', key] or ['put', key, value]
Keys and values are integers
Do not use dict, set, OrderedDict, or external libraries

Function Signature

def lru_cache(capacity, operations):

Your question is Custom Data Structure Implementation. 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