FastPrepLRU Cache
Problems/LRU Cache

LRU Cache

Capital One logoCapital One● MediumNEW GRADINTERNPHONE SCREENONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Four Capital One reports ask for an LRU cache in the coding part of the final interview. One from 2026 asks for get and put that both run in O(1). TDP new grad reports from 2020 and 2022 and a 2020 intern report name the task with no other detail.

The reports give no interface, edge rules or limits. Here a get on a missing key returns -1 and changes nothing. A get that finds its key and every put count as a use. A put on a stored key only changes its value. Keys and values are whole numbers from 0 to 10^9, the capacity is 1 to 10^4, and there are 1 to 10^4 calls. You get the calls as a list of operations instead of a class. You return one result for each get, in call order.

Our version is about 85% the same as the reported questions.

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 up keys[i]. On a hit, the call returns the cached value and that entry becomes the most recently used. On a miss, the call returns -1 and the cache stays exactly as it was.
  • "put" writes values[i] for keys[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 all capacity slots 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 101 returns 5 and moves it to the newest end: 102, 103, 101.
  • Key 104 evicts 102, the oldest use. Key 105 then evicts 103. The order is now 101, 104, 105.
  • So the gets return -1 for keys 102 and 103, and 5 for key 101, 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 9 is a miss. It returns -1 and does not add key 9.
  • After key 2 is written, both slots are used. Writing key 1 again only changes its value to 45; nothing is evicted.
  • The get on key 2 returns 60 and makes key 2 the newest use, so key 1 is now the oldest.
  • Key 3 therefore evicts key 1. The last two gets return -1 and 80.

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 10 holds the value 0. That is a real value, so its get returns 0, not -1.
  • Key 30 is a miss before it is written and a hit after, and key 20 is still cached. The results are 0, -1, 1, 0.

Constraints

  • 1 <= capacity <= 10^4
  • 1 <= operations.length <= 10^4
  • keys.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)
All Capital One interview questionsSee Capital One hiring insights
Saved
class Solution {
    public int[] runLruCache(int capacity, String[] operations, int[] keys, int[] values) {
        // Write your code here.
    }
}
Checking account…