I need two structure.
[Hashmap] to store all inserted key,value pairs
[Queue] to remember the least recently used one at top.( when a key is visited, put the entry to the bottom of the queue);
So, when set method is called,
3,create new key,value pair or invalid LRU one from queue top.
Updated 12/7/13 9:37 am
Java's build in collection framework has a type called " LinkedHashSet" which may help.
It will better describe the queue as a doubly linked list.
I think the most important part is that, when there is an existing entry in the cache, how to move this recent entry to the queue top (or the head node)? Such movement should not require iterating over the entire list. Otherwise, you will get TLE.
I think your approach should work. Don't forget to update the queue when get method is called as well.
My result is fully accepted.
One way is to add a increment flag to each item of the queue. At the same time, we store the latest flag in hash table for each key. For each visit or update, we push a new item into the queue while update the latest flag.
As a result, when invalidating the old key, we compare the item's flag with the key's latest one. If the flag is the same, it means the key is really old enough to be removed. Otherwise, just keep popping the queue.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.