LRU Cache
Updated
Problem statement
A service keeps a small in-memory cache in front of a slow account lookup. The cache has room for capacity entries, and each entry is a key with a value. When a new key arrives and every slot is taken, the entry whose most recent use lies furthest in the past is evicted. This policy is called least recently used (LRU).
Simulate this cache over a sequence of calls. For each index i, operations[i] names the call and keys[i] is its key. values[i] is the value to write, and a "get" call ignores it. Before the first call, nothing is cached.
"get"looks upkeys[i]. On a hit, the call returns the cached value and that entry becomes the most recently used. On a miss, the call returns-1and the cache stays exactly as it was."put"writesvalues[i]forkeys[i]and makes that entry the most recently used. Writing a key that is already cached overwrites its value and evicts nothing. Writing a key that is not cached while allcapacityslots are full first evicts the least recently used entry.
Return the values returned by the "get" calls, in call order. "put" calls return nothing.
Try to make every call take O(1) time on average.
Function
runLruCache(capacity: int, operations: String[], keys: int[], values: int[]) → int[]Examples
Example 1
capacity = 3operations = ["put","put","put","get","put","put","get","get","get"]keys = [101,102,103,101,104,105,102,103,101]values = [5,7,9,0,11,13,0,0,0]return = [5,-1,-1,5]- The first three puts fill all three slots. From oldest to newest use, the order is
101, 102, 103. - The get on key
101returns5and moves it to the newest end:102, 103, 101. - Key
104evicts102, the oldest use. Key105then evicts103. The order is now101, 104, 105. - So the gets return
-1for keys102and103, and5for key101, which survived because the earlier get refreshed it.
Example 2
capacity = 2operations = ["put","get","put","put","get","put","get","get"]keys = [1,9,2,1,2,3,1,3]values = [40,0,60,45,0,80,0,0]return = [-1,60,-1,80]- The get on key
9is a miss. It returns-1and does not add key9. - After key
2is written, both slots are used. Writing key1again only changes its value to45; nothing is evicted. - The get on key
2returns60and makes key2the newest use, so key1is now the oldest. - Key
3therefore evicts key1. The last two gets return-1and80.
Example 3
capacity = 4operations = ["put","put","get","get","put","get","get"]keys = [10,20,10,30,30,30,20]values = [0,0,0,0,1,0,0]return = [0,-1,1,0]- Only three different keys are ever written, so the four slots never fill and nothing is evicted.
- Key
10holds the value0. That is a real value, so its get returns0, not-1. - Key
30is a miss before it is written and a hit after, and key20is still cached. The results are0, -1, 1, 0.
Constraints
1 <= capacity <= 10^41 <= operations.length <= 10^4keys.length == values.length == operations.length- Each
operations[i]is"get"or"put". 0 <= keys[i], values[i] <= 10^9
More Capital One Onsite Interview questions
- Digit-Coded Card ValidationONSITE INTERVIEW · Seen Nov 2026
- Sort ColorsONSITE INTERVIEW · Seen Oct 2026
- Virtual Card Transaction ValidatorONSITE INTERVIEW · Seen Oct 2026
- Banking System with Top ActivityONSITE INTERVIEW · Seen Sep 2026
- Transaction Event StoreONSITE INTERVIEW · Seen Jul 2026
- Shortest Path in an Unweighted GraphONSITE INTERVIEW · Seen Jul 2026
- Duplicate Transactions Within 60 SecondsONSITE INTERVIEW · Seen May 2026
- Cashback TrackerONSITE INTERVIEW · Seen Nov 2025
- Reverse a StringOA · ONSITE INTERVIEW · Seen Oct 2025
- Most Cost-Effective MachineONSITE INTERVIEW · Seen Sep 2025
Similar questions at other companies
- LRU CacheLotusFlare · ONSITE INTERVIEW
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- LRU CacheGimlet Labs · PHONE SCREEN
- LRU CacheBNSF Railway · PHONE SCREENBNSF Railway interview questions
- LRU CacheJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
- LRU Cache OperationsHevo Data · ONSITE INTERVIEW
- Max Frequency TrackerProcol · PHONE SCREEN
- Balanced Session ManagerPalantir · PHONE SCREENPalantir interview questions
- LRU Cache Operation SequenceCARS24 · PHONE SCREEN
- LRU Cache OperationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
Capital One interview experiences
- Capital One Experienced Engineer Power Day and OA: 6 Experiences
- Capital One New Grad OA Questions: 14 Experiences (Part 2 of 2)
- Capital One TDP Agentic Round (AI Coding): 7 Experiences
- Capital One SWE Power Day, Level Not Reported: 6 Experiences
- Capital One TIP Intern OA and Power Day: 13 Experiences
- Capital One TDP Agentic Power Day: 25 Experiences (Part 1 of 2)