Skip to the code
cf.
+50 XP

#696 Asset Cache That Evicts the Least Used

hard

A design tool caches icons and keeps the ones used most often. Each cached key has a use count. When the cache is full and a new key arrives, it removes the key with the smallest use count; if several keys tie, it removes the one among them that was used least recently. Write a class AssetCache:

  • new AssetCache(capacity) creates an empty cache.
  • get(key) returns the key's value and adds one use, or returns -1 if the key isn't cached.
  • put(key, value) stores the value. For an existing key, it replaces the value and adds one use. For a new key, it first removes one key as described if the cache is full, then stores the new key with a use count of 1.

Both methods must run in O(1) average time.

Each example lists the calls in order, then each call's arguments. The first call creates the object with new AssetCache(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Example 1

Input: ["AssetCache","put","put","get","put","get","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
Output: [null,null,null,1,null,-1,3,null,-1,3,4]

Key 2 has fewer uses than key 1, so put(3, 3) removes 2. Keys 1 and 3 then tie at 2 uses, and 1 was used less recently, so put(4, 4) removes 1.

Example 2

Input: ["AssetCache","get"]
[[1],[0]]
Output: [null,-1]

Nothing is cached.

Constraints

  • 1 <= capacity <= 10^4
  • 0 <= key, value <= 10^5
  • At most 2 * 10^5 calls.
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).