Efficient Data Structures | Dataford Interview Questions

Can you solve a classic data structure problem using an efficient algorithm?

Implement an LRU cache supporting get and put operations in O(1) average time. Use lru_cache_operations(capacity, operations), where each operation is ['get', key] or ['put', key, value]; return values for get operations, using -1 for missing keys. Keys and values are integers.

Constraints

1 <= capacity <= 10^5
1 <= len(operations) <= 5000
Each operation is either ['get', key] or ['put', key, value]
Keys and values are integers
Keys may be repeated
All get operations must return their values in input order

Function Signature

def lru_cache_operations(capacity, operations):

Your question is Efficient Data Structures. 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

Can you solve a classic data structure problem using an efficient algorithm?

Constraints

1 <= capacity <= 10^5
1 <= len(operations) <= 5000
Each operation is either ['get', key] or ['put', key, value]
Keys and values are integers
Keys may be repeated
All get operations must return their values in input order

Function Signature

def lru_cache_operations(capacity, operations):

Your question is Efficient Data Structures. 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.