InternDoor

A cache that forgets the oldest

Mediumdesign · hash map · linked listDesign a class

Build LRUCache, a store of whole-number keys and values that holds at most capacity keys.

LRUCache(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, the key that was used longest ago leaves first.

A get of a key that is in the cache and every put count as using that key. Aim for O(1) time per call.

Example 1
Input
["LRUCache","put","put","get","put","get","get","put","get"]
[[2],[1,10],[2,20],[1],[3,30],[2],[3],[1,15],[1]]
Output
[null,null,null,10,null,-1,30,null,15]

Reading key 1 makes key 2 the one used longest ago, so adding key 3 pushes key 2 out. Putting key 1 again only changes its value.

Example 2
Input
["LRUCache","put","put","get","put","get","get"]
[[1],[7,1],[7,2],[7],[8,3],[7],[8]]
Output
[null,null,null,2,null,-1,3]

With room for one key, key 8 replaces key 7.

Limits

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

Hints

Hint 1

A hash map finds a key in O(1); something else has to remember the order the keys were used in.

Hint 2

Keep the keys in a doubly linked list, most recently used at one end: a use moves a node to that end, and the other end is the key to evict.

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.