It does not use removeEldestEntry from the API.
By leveraging the insertion-order property of LinkedHashMap, removing a key, value pair and putting it back maintains the least recently used property in O(1) time.
Combining iterator.next().getKey() with remove allows you to remove the least recently used pair in O(1) time.
Just using a list instead of deque or orderedDict will also do the work:
Depends on how you define "do the work". If we use OrderedDict, both operations would be O(1) on average. And when we use deque instead, at least for set operation, when capacity is full and the key we want to push is not in cache, we get O(1) on average. And in your case, both operations take O(n).
Hitalex - This is least recently used cache eviction algorithm. Your answer would be right if it is least FREQUENTLY used (LFU) algorithm where the number of times the key is accessed matters. It does not matter in LRU.
Hi @uniqueness, first, I want to say welcome and I appreciate your contribution to the community. If you have a question about your algorithm, feel free to ask a question. Discuss is not built for the purpose of sharing your solution, though in future OJ might have a separate feature for you to share your solution. If you would like to contribute to the community, I would suggest contributing answers to questions that other users had posted.