LRU Cache
Updated
Problem statement
Build a cache that holds at most capacity key-value pairs. When it is full and a new key arrives, it throws out the key whose last use is the oldest. This rule is called least recently used (LRU) replacement.
The cache starts empty. Process the calls in order. Call i is operations[i] on the key keys[i]:
"get": if the key is in the cache, report its value and mark the key as just used. If it is not, report-1and change nothing.values[i]is not used."put": storevalues[i]under the key and mark the key as just used. If the key is already in the cache, only its value changes and nothing is removed. If the key is new and the cache already holdscapacitykeys, first remove the key whose last use is the oldest.
A key counts as used when a "get" finds it or when a "put" stores it. Return an array with one number for each "get" call, in order. A "put" call adds nothing to the array.
Function
runLruCache(capacity: int, operations: String[], keys: int[], values: int[]) → int[]Examples
Example 1
capacity = 2operations = ["put","put","get","put","get","get","get"]keys = [1,2,1,3,2,3,1]values = [10,20,0,30,0,0,0]return = [10,-1,30,10]- The two puts fill the cache with keys
1and2. - The get on key
1reports10and makes key1the most recently used. - The put of key
3finds the cache full. Key2was used longest ago, so it is removed. - The gets then report
-1for key2,30for key3and10for key1.
Example 2
capacity = 2operations = ["put","put","put","put","get","get","get"]keys = [5,6,5,7,6,5,7]values = [1,2,3,4,0,0,0]return = [-1,3,4]- The third put writes key
5again. The cache keeps two keys, key5now holds3, and key5becomes the most recently used. - The put of key
7finds the cache full and removes key6, whose last use is now the oldest. - The gets report
-1for key6,3for key5and4for key7.
Example 3
capacity = 1operations = ["get","put","get","put","get","get"]keys = [4,4,4,8,4,8]values = [0,0,0,9,0,0]return = [-1,0,-1,9]- The first get finds an empty cache and reports
-1. - After key
4is stored with value0, the get reports0. - With room for one key, storing key
8removes key4, so the last gets report-1and9.
Constraints
1 <= capacity <= 10^41 <= operations.length <= 10^4keys.length == values.length == operations.length- Each
operations[i]is"get"or"put". 0 <= keys[i] <= 10^90 <= values[i] <= 10^9
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
- Distance Sums to Special Nodes in a Weighted TreeONSITE INTERVIEW · Seen Aug 2021
Similar questions at other companies
- LRU CacheLotusFlare · ONSITE INTERVIEW
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- LRU CacheJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
- LRU Cache OperationsHevo Data · ONSITE INTERVIEW
- LRU Cache OperationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- LRU Cache Operation SequenceGoogle · ONSITE INTERVIEWGoogle interview questions
- Least Recently Used CacheMicrosoft · OA · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- LRU CacheAMD · ONSITE INTERVIEWAMD interview questions
- LRU CacheApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions
- Least Recently Used CacheByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions