• https://leetcode.com/problems/lru-cache/
• https://leetcode.com/problems/lfu-cache/
• https://medium.com/@krishankantsinghal/my-first-blog-on-medium-583159139237
• https://medium.com/algorithm-and-datastructure/lfu-cache-in-o-1-in-java-4bac0892bdb3
• https://en.wikipedia.org/wiki/Cache_replacement_policies
• https://ieftimov.com/post/when-why-least-frequently-used-cache-implementation-golang/
• https://en.wikipedia.org/wiki/Least_frequently_used
• https://medium.com/algorithm-and-datastructure/lfu-cache-in-o-1-in-java-4bac0892bdb3

goals of this workshop

• understand concept of LRU cache
• understand concept of LFU cache
• implement LRU and LFU cache
• see how guards are useful in list implementations

workshop: lfu.workshop, lru.workshop

• during implementation use classes from list

answers: lfu.answers, lru.answers

• get(key) - get the value if the key exists in the cache, otherwise null
• put(key, value) - set or insert the value if the key is not already present
  • when the cache reached its capacity, it should invalidate the least recently used item before inserting a new item
• both in O(1)

• LinkedHashMap<Integer, Integer> + overridden removeEldestEntry method
  • remark: LinkedHashMap has two iteration order: access-order or insertion-order
• map + double linked list

• get(key) - get the value if the key exists in the cache, otherwise null
• put(key, value) - set or insert the value if the key is not already present
  • when the cache reached its capacity, it should invalidate the least recently used item before inserting a new item
• both in O(1)

• consider an item in memory which is referenced repeatedly for a short period of time and is not accessed again for an extended period of time
• an explicit LFU system is fairly uncommon; instead, there are hybrids that utilize LFU concepts

• cache map, frequency map, frequency list