MediumLinked ListsAI interview only
LRU Cache
Asked atamazongooglemetamicrosoftapplebloomberglinkedinubergoldman-sachs
01 · Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)— Initialize the LRU cache with positive sizecapacity.int get(int key)— Return the value of thekeyif the key exists, otherwise return-1.void put(int key, int value)— Update the value of thekeyif the key exists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
02 · Examples
Example 01
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
After put(1,1) and put(2,2), the cache holds {1=1, 2=2}. get(1) returns 1 and makes key 1 most recent. put(3,3) evicts key 2 (least recently used). get(2) returns -1. put(4,4) evicts key 1. get(1) returns -1, get(3) returns 3, get(4) returns 4.
03 · Constraints
- 011 <= capacity <= 3000
- 020 <= key <= 104
- 030 <= value <= 105
- 04At most 2 * 105 calls will be made to get and put.
04 · Optimal complexity
- Time
- O(1)
- Space
- O(capacity)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.