I was asked this question in an interview where he asked first about the difference between LRU and LFU and then asked to implement both. I knew LRU can be implemented through LinkedHashMap but I got confused with LFU. Can anyone tell me how to implement it with simplest data structures with good explaination? Also can it be implemented with LinkedHashMap too.?
Assuming the cache entries were keyed, you could do it with a queue (LinkedList) and a map (HashMap).
(assume the queue and map are full)
Pick a bound b for the queue. On every cache request, push the key for the requested page into the queue then poll the queue.
If the page you want is in the map, return the page. If the page isn't in the map find the least frequently occurring key in the queue which is also in the map or key for the page you want. If that key is the key for the page you want, do nothing; else remove the entry from the map for that key and insert your page into the map.
Return your page.
Complexity for a cache hit is O(1), O(b) for a miss.
This assumes you want to bound the frequency. ie. "least frequently used in the last b requests" instead of "least frequently used ever".