Java · Mid-level · Coding

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.

~15 min by voice

How to approach it

This checks whether you can build a data structure from two primitives to get O(1) on both operations, a hash table for lookup and a doubly linked list for usage order, and carefully handle the edge cases: updating an existing key, eviction without an off-by-one error, a missing key.

Have you seen this question in a real interview?

Answers0

Avg. score—

Strong—

Practiced0

Topics

lru cache collections

Similar questions

Write a class FlatIterator that takes a list of lists of integers and implements the Iterator interface: hasNext tells you whether there are elements left, and next returns the next number, going through all the nested lists in order. You're not allowed to copy all the elements into one combined list up front. Mid-level 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 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). Mid-level What's the difference between ArrayList and LinkedList, and when would you choose each? Junior How does a HashMap work internally? What happens when you call put? Junior

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