Loading...
Loading...
Loading...
Sneha is building the product cache for her online store app. The cache can hold at most c keys, each with a value.
You get q commands, one per line: - get key: print the value stored for key, or -1 if key is not in the cache. - put key value: store value for key. If key is already there, replace its value. A put prints nothing.
Both commands count as a use of the key (a get of a missing key uses nothing). When a put brings in a new key and the cache already holds c keys, first remove the key whose last use is the oldest.
get key or put key value.get command, in the order the commands appear.get.Example
Input
2 8 put 1 10 put 2 20 get 1 put 3 30 get 2 get 3 put 1 15 get 1
Output
10 -1 30 15
get 1 makes key 1 the most recent, so put 3 30 removes key 2. Then put 1 15 replaces the value of key 1 without removing anything.
Try the problem first. Open one hint at a time.
Two things must be fast: finding a key, and knowing which key was used longest ago.
Keep the keys in order of last use: the most recent at one end, the oldest at the other. Every use moves a key to the recent end.
Moving a key from the middle of that order must be O(1). A list where each entry knows its neighbours on both sides can unlink itself.
Use a HashMap from key to node, plus a doubly linked list of nodes in order of use. Java also has LinkedHashMap with access order, which does the same job.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor