LFU Cache

LFU Cache is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

- LFUCache(int capacity) Initializes the object with the capacity of the data structure.

- int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.

- void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation // cnt(x) = the use counter for key x // cache=[] will show the last used order for tiebreakers (leftmost element is most recent) LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // return 1 // cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2. // cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1. // cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // return 4 // cache=[4,3], cnt(4)=2, cnt(3)=3

Constraints:

- 1 <= capacity <= 104

- 0 <= key <= 105

- 0 <= value <= 109

- At most 2 105 calls will be made to get and put.

Topics and companies

Topics: Hash Table, Linked List, Design, Doubly-Linked List.

Reported in interviews at Amazon, Microsoft, Google, Citadel, Bloomberg, Salesforce, Twitch.

How to practise LFU Cache on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) average per get and put operation. All operations (get, put, frequency update, eviction) are O(1) due to the use of hash maps and linked lists. time and O(N), where N is the capacity of the cache. Each key is stored in the hash maps and lists, and the total number of nodes never exceeds the capacity. space.

Open LFU Cache in the code editor, or read the LFU Cache editorial for a worked solution with its approach and complexity analysis.

Where LFU Cache sits in the DSA pattern sheet

Problems related to LFU Cache

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

Preparing this workspace.