AmazonMediumHash Map / Linked List
LRU Cache
Software Engineer
Problem
Design a data structure that supports get and put operations in O(1) time.
Example
put(1, 10)
put(2, 20)
get(1) -> 10
put(3, 30)
get(2) -> -1
Approach
Use a hash map for O(1) lookup and a doubly linked list for O(1) insertion and removal.
Complexity
Time: Depends on system design
Space: Depends on storage architecture
Solution
Use:
HashMap:
key -> node
Doubly Linked List:
most recently used <-> least recently used
Both get() and put() can therefore run in O(1).
Related Topics
System DesignDatabaseCacheDistributed Systems