FastPrepLRU Cache
Problems/LRU Cache

LRU Cache

Nutanix logoNutanix● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A campus intern report published in 2025 says the talk moved from caching and page replacement to LRU. The candidate then wrote an LRU cache on paper. A 2021 intern report also had an LRU cache design question inside a system design round, with no code mentioned.

The reports give no interface, no edge rules and no limits. Here the cache stores whole-number keys and values from 0 to 10^9. It holds 1 to 10^4 keys and gets 1 to 10^4 calls. A get on a missing key returns -1 and leaves the cache unchanged. A get that finds its key and every put count as a use. A put on a key already in the cache only replaces its value. You get the calls as a list of operations instead of a class, and you return one number for each get.

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

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 -1 and change nothing. values[i] is not used.
  • "put": store values[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 holds capacity keys, 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 1 and 2.
  • The get on key 1 reports 10 and makes key 1 the most recently used.
  • The put of key 3 finds the cache full. Key 2 was used longest ago, so it is removed.
  • The gets then report -1 for key 2, 30 for key 3 and 10 for key 1.

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 5 again. The cache keeps two keys, key 5 now holds 3, and key 5 becomes the most recently used.
  • The put of key 7 finds the cache full and removes key 6, whose last use is now the oldest.
  • The gets report -1 for key 6, 3 for key 5 and 4 for key 7.

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 4 is stored with value 0, the get reports 0.
  • With room for one key, storing key 8 removes key 4, so the last gets report -1 and 9.

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] <= 10^9
  • 0 <= 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

Interview reports that mention this question

  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public int[] runLruCache(int capacity, String[] operations, int[] keys, int[] values) {
        // Write your code here.
    }
}
Checking account…