Loading...
Loading...
Loading...
A cache holds at most c items. put k v stores a value and makes k the most recently used; if the cache then holds more than c items, the least recently used one is removed. get k prints the value of k, or -1 if absent, and makes k the most recently used. Print the result of every get.
put k v or get k.Example 1
Input
2 9 put 1 10 put 2 20 get 1 put 3 30 get 2 put 4 40 get 1 get 3 get 4
Output
10 -1 -1 30 40
Key 2 is evicted first, then key 1.
Example 2
Input
1 3 put 5 6 get 5 get 7
Output
6 -1
Try the problem first. Open one hint at a time.
Keep keys in order from least to most recently used.
OrderedDict.move_to_end and popitem(last=False) do both jobs in constant time.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor