How should I practice LFU Cache?

Start by reading the full statement, solve the visible examples, then compare the pattern against related JP Morgan Chase onsite interview problems in FastPrep.

Is LFU Cache associated with JP Morgan Chase?

FastPrep tags this as a JP Morgan Chase onsite interview coding practice problem when the problem catalog has that company and stage context.

LFU Cache

JP Morgan Chase● HardFULLTIMEONSITE INTERVIEW

Problem statement

Source note: This is the follow-up to the LRU cache question in the coding round of a JPMorgan Chase senior software engineer interview: extend the cache into an LFU cache. The report says to be ready to explain the data structures, frequency buckets for this part, and to target constant time for reads and writes. It gives no operation format, tie rule or limits.

Practice choices: operations come as PUT and GET strings; a successful GET and every PUT on a stored key add one use; a missing GET returns -1 and changes nothing; an eviction removes the key with the fewest uses, breaking ties by least recent use; a new or returning key starts at one use; updating a stored key evicts nothing; the limits; and the examples, which are ours. The tests check results only, not running time.

The judged task matches the report at about 80%.

Build a least frequently used (LFU) cache that holds at most capacity keys, then run the operations in operations in order. Every stored key has a use count.

"GET key" returns the stored value and adds 1 to the key's use count, or returns -1 if the key is not in the cache. A GET that misses changes nothing.
"PUT key value" on a stored key replaces its value and adds 1 to its use count; nothing is evicted.
"PUT key value" on a new key first makes room if the cache already holds capacity keys: it removes the key with the smallest use count, and if several keys tie, the one among them that was used least recently. Then it stores the new key with use count 1.

A key's last use is its most recent PUT or successful GET. A key that is evicted and stored again starts over at use count 1.

Return the results of all GET operations, in order. Aim for O(1) average time for each operation. The judge checks only the returned results, not the running time.

Function

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

Examples

Example 1

capacity = 2operations = ["PUT 1 10","PUT 2 20","GET 1","PUT 3 30","GET 2","GET 3","GET 1"]return = [10,-1,30,10]

After GET 1, key 1 has been used twice and key 2 once. PUT 3 30 needs room, so it evicts key 2, the least frequently used key. The gets then return -1, 30 and 10.

Example 2

capacity = 2operations = ["PUT 1 1","PUT 2 2","GET 1","GET 2","PUT 3 3","GET 1","GET 2","GET 3"]return = [1,2,-1,2,3]

Keys 1 and 2 have both been used twice, so their counts tie. Among them, key 1 was used least recently, so PUT 3 3 evicts key 1. The gets after it return -1, 2 and 3.

Example 3

capacity = 2operations = ["PUT 4 40","PUT 5 50","GET 5","PUT 4 44","PUT 6 60","GET 4","GET 5","GET 6"]return = [50,44,-1,60]

GET 5 returns 50 and uses key 5, and PUT 4 44 updates key 4, which also counts as a use. Both keys now have count 2. Key 5 was used less recently, so PUT 6 60 evicts key 5. The last three gets return 44, -1 and 60.

Constraints

1 <= capacity <= 3000
1 <= operations.length <= 10^4
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.