Reference: LeetCode
Difficulty: Hard

Problem

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

  • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  • put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted (FIFO).

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

Example: 

1
2
3
4
5
6
7
8
9
10
11
LFUCache cache = new LFUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Follow up: Could you do both operations in $O(1)$ time complexity?

Analysis

Three Maps

Reference: LFU cache in O(1) in Java

  • valMap: Store keys and values.
  • countMap: Store frequencies of keys.
  • listMap: Store count and its corresponding keys in order to handle tie cases (insertion-order mode).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class LFUCache {
  
  Map<Integer, Integer> valMap = new HashMap<>();
  Map<Integer, Integer> countMap = new HashMap<>();
  Map<Integer, LinkedHashSet<Integer>> listMap = new HashMap<>(); // <count, <key>> (FIFO)
  
  int capacity;
  int min;
  
  public LFUCache(int capacity) {
    this.capacity = capacity;
    this.min = -1;
    listMap.put(1, new LinkedHashSet<>());
  }
  
  
  public int get(int key) {
    if (!valMap.containsKey(key)) {
      return -1;
    }
    // update count
    int count = countMap.get(key);
    countMap.put(key, count + 1);
    // remove the key in the list of count
    listMap.get(count).remove(key); // <count, LinkedHashSet>
    // update min
    if (count == min && listMap.get(count).size() == 0) {
      ++min;
    }
    // add list of (count + 1)
    if (!listMap.containsKey(count + 1)) {
      listMap.put(count + 1, new LinkedHashSet<>());
    }
    listMap.get(count + 1).add(key);
    
    return valMap.get(key);
  }

  
  public void put(int key, int value) {
    if (capacity <= 0) {
      return;
    }
    if (valMap.containsKey(key)) { // exists
      valMap.put(key, value);
      get(key); // smart!
      return;
    }
    // new key
    if (valMap.size() == capacity) { // full
      int rk = listMap.get(min).iterator().next(); // removed key
      valMap.remove(rk);
      countMap.remove(rk);
      listMap.get(min).remove(rk);
    }
    // add
    valMap.put(key, value);
    countMap.put(key, 1);
    min = 1;
    listMap.get(1).add(key);
  }
}

Time: $O(1)$
Space: N/A