FastPrepLRU Cache
Problems/LRU Cache

LRU Cache

Gimlet Labs logoGimlet Labs● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A Gimlet Labs machine learning engineer phone screen asked for an LRU cache. The report names the exercise and nothing else.

It gives no interface, operation format, capacity or limits. We chose these. Operations come as PUT and GET strings. A GET that finds its key returns the value and makes that key the most recent. A GET on a missing key returns -1 and changes nothing. Every PUT makes its key the most recent, and updating a stored key does not evict anything. We also chose the limits on capacity, operations, keys and values.

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

Build a least recently used (LRU) cache that holds at most capacity keys, then run the operations in operations in order.

  • "PUT key value" stores value under key. If the key is already stored, its value is replaced and nothing is evicted. If the key is new and the cache already holds capacity keys, first remove the least recently used key.
  • "GET key" returns the stored value, or -1 if the key is not in the cache.
  • A PUT and a GET that finds its key both make that key the most recently used. A GET that misses changes nothing.

Return the results of all GET operations, in order.

Function

runLRU(capacity: int, operations: String[]) → int[]

Examples

Example 1

capacity = 3operations = ["PUT 1 100","PUT 2 200","PUT 3 300","GET 1","PUT 4 400","GET 2","GET 3","GET 1","GET 4"]return = [100,-1,300,100,400]

Keys 1, 2 and 3 fill the cache. GET 1 returns 100 and makes key 1 the most recent, so the least recently used key is now 2. PUT 4 400 needs room and evicts key 2. The gets then return -1 for key 2, 300 for key 3, 100 for key 1 and 400 for key 4.

Example 2

capacity = 2operations = ["PUT 8 1","PUT 9 2","GET 5","PUT 9 7","PUT 6 3","GET 8","GET 9","GET 6"]return = [-1,-1,7,3]

GET 5 misses, returns -1 and changes nothing. PUT 9 7 replaces the value of key 9 and makes it the most recent without evicting anything. When PUT 6 3 needs room, key 8 is the least recently used and is removed. The gets return -1, 7 and 3.

Example 3

capacity = 1operations = ["PUT 0 5","GET 0","PUT 1 6","GET 0","GET 1"]return = [5,-1,6]

With capacity 1, the cache holds one key. GET 0 returns 5. Putting key 1 evicts key 0, so the next gets return -1 and 6.

Constraints

  • 1 <= capacity <= 1000
  • 1 <= operations.length <= 2000
  • Each operation is "PUT key value" or "GET key", with single spaces and no leading zeros.
  • 0 <= key <= 10^4 and 0 <= value <= 10^5
  • At least one operation is a GET.

Similar questions at other companies

  • LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • LRU CacheBNSF Railway · PHONE SCREENBNSF Railway interview questions
  • Max Frequency TrackerProcol · PHONE SCREEN
  • Balanced Session ManagerPalantir · PHONE SCREENPalantir interview questions
  • LRU Cache Operation SequenceCARS24 · PHONE SCREEN
  • LRU Key-Value Cache OperationsCohesity · PHONE SCREEN
  • Least Recently Used CacheMicrosoft · OA · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
  • LRU CacheApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions
  • Least Recently Used CacheByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
  • LRU CacheServiceNow · PHONE SCREEN

Interview reports that mention this question

  • Gimlet Labs Experienced MLE Phone Screen and Onsite: 1 Experience
See Gimlet Labs hiring insights
Saved
class Solution {
    public int[] runLRU(int capacity, String[] operations) {
        // Write your code here.
    }
}
Checking account…