Least recently used cache
hard
The first line has the cache capacity and the number of operations q. Each of the next q lines is "put key value" or "get key". For each get, print the value, or -1 if the key is not cached. When putting into a full cache, first remove the key used least recently (a get or put counts as a use).
Example 1: input
2 9 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4
Output
1 -1 -1 3 4
Example 2: input
1 4 put 5 50 get 5 put 6 60 get 5
Output
50 -1
Plus 1 hidden test when you check your answer.
Your solution
Read from standard input and print the answer. Run it on the examples as often as you like, then check it against every test.
Stuck?
Open hints one at a time. The write-up explains a full solution.
Discussion
Ask a question or share a tip. Please don’t post full solutions. Posts appear once a moderator approves them.
No posts yet.