Backend · Mid-level · Coding

Implement a fixed-capacity LRU cache. The get method takes a key and returns the value or an indication that it's missing, the put method adds or updates a value, and on overflow the key that has gone unused the longest is evicted. Both operations must run in O(1).

~15 min by voice

How to approach it

They're checking whether you can combine two data structures: a hash table for O(1) lookup and a doubly linked list (or an ordered dictionary) for the usage order. It's also important to handle the edge cases carefully: updating an existing key, eviction, and a zero capacity.

Have you seen this question in a real interview?

Answers0

Avg. score—

Strong—

Practiced0

Topics

lru cache data structures

Similar questions

Implement an LRUCache class with a given capacity and two methods: get returns the value for a key or None, and put stores a value. When the cache overflows, the key that hasn't been accessed for the longest time is evicted, and both operations must run in O(1). Mid-level Implement an LruCache class with a fixed capacity passed to the constructor. The get method returns the value for a key or null, the put method stores a key-value pair, and when the cache overflows, the element that hasn't been accessed for the longest time is evicted. Both operations must run in constant time. Mid-level

Answer by voice

The interviewer will ask this question and listen. Think out loud and ask for a hint if you need one. When you're done, pause or tap “That's my answer”. In about a minute, your score and the points you covered show up here.

Best with headphones · ~15 min