FastPrepLeast Recently Used Cache With O(1) Calls
Problems/Least Recently Used Cache With O(1) Calls

Least Recently Used Cache With O(1) Calls

Adobe logoAdobe● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: Two separate Adobe interviews, described in three posts, bring up a least-recently-used cache in the first round. In one, the candidate only had to outline it in pseudocode; the same candidate's later retelling of that interview adds that the outline paired a hash map with a doubly linked list so get and put run in constant time. In the other, the candidate wrote constant-time Java and was then asked how to restructure it so a different eviction rule, LFU for example, could be swapped in with little new code.

Neither interview gives an interface or examples. Our choices: the calls come as arrays of get and put operations, a missing key returns -1, updating an existing key never evicts, capacity is 1 to 1000, there are at most 2000 calls, keys are 0 to 10^4 and values 0 to 10^5, and the examples are our own. The editorial discusses the swap-in follow-up; the judge does not test it.

The judged task matches the reports at about 85%.

Build a cache that holds at most capacity keys, each with a value, and evicts the least recently used key when it runs out of room. It starts empty and supports two calls:

  • get(key): if key is in the cache, return its value and mark it as the most recently used key. Otherwise return -1 and change nothing.
  • put(key, value): if key is already in the cache, replace its value and mark it as the most recently used. Otherwise, if the cache is full, first remove the least recently used key; then add key as the most recently used.

Updating a key that is already in the cache never removes anything.

You get the calls in order as three arrays: operations[i] is "get" or "put", keys[i] is its key and values[i] its value. Return the results of the get calls, in order. Try to make each call take O(1) time.

Function

runLruCache(capacity: int, operations: String[], keys: int[], values: int[]) → int[]

Examples

Example 1

capacity = 2operations = ["put","put","get","put","get","get","put","get"]keys = [5,7,5,9,7,9,5,5]values = [50,70,0,90,0,0,55,0]return = [50,-1,90,55]

After get 5, key 5 is the most recently used and key 7 the least. So put 9 on a full cache evicts 7, and get 7 returns -1. get 9 returns 90. put 5 55 updates the value of key 5 without evicting anything, so the last get 5 returns 55.

Example 2

capacity = 1operations = ["put","put","get","get"]keys = [1,2,1,2]values = [10,20,0,0]return = [-1,20]

With room for one key, put 2 evicts key 1. So get 1 returns -1 and get 2 returns 20.

Example 3

capacity = 3operations = ["get","put","get"]keys = [4,4,4]values = [0,40,0]return = [-1,40]

The cache starts empty, so the first get 4 returns -1. After put 4 40, it returns 40.

Constraints

  • 1 <= capacity <= 1000
  • 1 <= operations.length <= 2000, and keys and values have the same length as operations.
  • Each operations[i] is "get" or "put", and at least one is "get".
  • 0 <= keys[i] <= 10^4 and 0 <= values[i] <= 10^5; for a "get", values[i] is 0 and is ignored.

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
public int[] runLruCache(int capacity, String[] operations, int[] keys, int[] values) {
    // Write your code here.
}
Checking account…