FastPrepLeast Frequently Used Cache Simulator
Problems/Least Frequently Used Cache Simulator

Least Frequently Used Cache Simulator

Adobe logoAdobe● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report only says the first DSA round ended with a talk about LFU caching, after two coded questions and a third described out loud; it gives no interface, rules or code.

We turned that topic into a coded exercise. Our choices: a get or a value update counts as a use, a new key starts at one use, ties on use count go to the key used longest ago, a value update never removes a key, capacity is 1 to 1000 with at most 2000 calls, keys up to 10^4 and values up to 10^5, and the examples are new.

The judged task matches the report at about 55%.

A cache holds at most capacity keys, each with a value. It starts empty. Every key also has a use count.

  • get(key): if the key is in the cache, return its value and add 1 to its use count. Otherwise return -1 and change nothing.
  • put(key, value): if the key is already in the cache, set its new value and add 1 to its use count; nothing is removed. If the key is new and the cache is full, first remove one key: the one with the smallest use count. If several keys share that smallest count, remove the one whose last get or put happened longest ago. Then add the new key with use count 1.

The calls come as three arrays: call i is operations[i] on key keys[i], and values[i] is the value for a "put" (it is 0 for a "get"). Return the results of the "get" calls, in order.

Function

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

Examples

Example 1

capacity = 2operations = ["put","put","get","get","put","get","get","get"]keys = [3,8,3,3,6,8,3,6]values = [30,80,0,0,60,0,0,0]return = [30,30,-1,30,60]

Key 3 is used three times (one put, two gets) and key 8 once. When key 6 arrives the cache is full, so the least used key, 8, is removed: get 8 returns -1, while keys 3 and 6 return 30 and 60.

Example 2

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

Keys 1 and 2 are both used once. That is a tie, so the one used longer ago, key 1, is removed when key 3 arrives.

Example 3

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

Putting key 4 again only updates its value; nothing is removed, and get 4 returns 44.

Constraints

  • 1 <= capacity <= 1000
  • 1 <= operations.length <= 2000, and keys.length == values.length == operations.length
  • Each operations[i] is "get" or "put", and at least one is "get".
  • 0 <= keys[i] <= 10^4
  • 0 <= values[i] <= 10^5, and values[i] == 0 when operations[i] is "get".

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[] runLfuCache(int capacity, String[] operations, int[] keys, int[] values) {
    // Write your code here.
}
Checking account…