InternDoor

A cache that forgets the least used

Harddesign · hash map · linked listDesign a class

Reported in interviews at (where)

Build LFUCache, a store of whole-number keys and values that holds at most capacity keys and remembers how often each key has been used.

LFUCache(capacity) starts empty.

get(key) returns the value stored for key, or -1 if the key is not in the cache.

put(key, value) stores value for key, replacing the value the key had. If that adds a new key to a full cache, one key leaves first: the one used the fewest times, and among those with the same count, the one used longest ago.

A get of a key that is in the cache and every put add one use to that key; a key that is added starts with one use. A key that leaves the cache forgets its count. Aim for O(1) time per call.

Example 1
Input
["LFUCache","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 been used once and key 1 twice, so key 3 pushes key 2 out. Keys 1 and 3 then have two uses each; key 1 was used longer ago, so key 4 pushes it out.

Example 2
Input
["LFUCache","put","get","put","get","get"]
[[1],[5,50],[5],[6,60],[5],[6]]
Output
[null,null,50,null,-1,60]

With room for one key, a new key always replaces the old one, however often it was used.

Limits

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 100000
  • at most 20000 calls after the constructor

Hints

Hint 1

Group the keys by how many times they have been used, and inside each group keep them in the order they were used.

Hint 2

Remember the smallest count in use: it only resets to 1 when a new key arrives, and it only grows by one when the last key of that count is used again.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.