# LFU Cache

## Question

LFU (Least Frequently Used) is a famous cache eviction algorithm.

For a cache with capacity k, if the cache is full and need to evict a key in it, the key with the least frequently used will be kicked out.

Implement `set` and `get` method for LFU cache.

Have you met this question in a real interview? Yes

Example

Given capacity=3

``````set(2,2)
set(1,1)
get(2)
>> 2
get(1)
>> 1
get(2)
>> 2
set(3,3)
set(4,4)
get(3)
>> -1
get(2)
>> 2
get(1)
>> 1
get(4)
>> 4
``````

## Solution

``````public class LFUCache {

private final Map<Integer, CacheNode> cache;
private int lowestFrequency;
private int maxFrequency;
private final int maxCacheSize;

// @param capacity, an integer
public LFUCache(int capacity) {
this.cache = new HashMap<Integer, CacheNode>(capacity);
this.frequencyList = new LinkedHashSet[capacity * 2];
this.lowestFrequency = 0;
this.maxFrequency = capacity * 2 - 1;
this.maxCacheSize = capacity;
initFrequencyList();
}

// @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
CacheNode currentNode = cache.get(key);
if (currentNode == null) {
if (cache.size() == maxCacheSize) {
doEviction();
}
currentNode = new CacheNode(key, value, 0);
cache.put(key, currentNode);
lowestFrequency = 0;
} else {
currentNode.v = value;
}
}

public int get(int key) {
CacheNode currentNode = cache.get(key);
if (currentNode != null) {
return currentNode.v;
} else {
return -1;
}
}

int currentFrequency = currentNode.frequency;
if (currentFrequency < maxFrequency) {
int nextFrequency = currentFrequency + 1;
moveToNextFrequency(currentNode, nextFrequency, currentNodes, newNodes);
cache.put(currentNode.k, currentNode);
if (lowestFrequency == currentFrequency && currentNodes.isEmpty()) {
lowestFrequency = nextFrequency;
}
} else {
// Hybrid with LRU: put most recently accessed ahead of others:
nodes.remove(currentNode);
}
}

public int remove(int key) {
CacheNode currentNode = cache.remove(key);
if (currentNode != null) {
nodes.remove(currentNode);
if (lowestFrequency == currentNode.frequency) {
findNextLowestFrequency();
}
return currentNode.v;
} else {
return -1;
}
}

public int frequencyOf(int key) {
CacheNode node = cache.get(key);
if (node != null) {
return node.frequency + 1;
} else {
return 0;
}
}

public void clear() {
for (int i = 0; i <= maxFrequency; i++) {
frequencyList[i].clear();
}
cache.clear();
lowestFrequency = 0;
}

public int size() {
return cache.size();
}

public boolean isEmpty() {
return this.cache.isEmpty();
}

public boolean containsKey(int key) {
return this.cache.containsKey(key);
}

private void initFrequencyList() {
for (int i = 0; i <= maxFrequency; i++) {
}
}

private void doEviction() {
int currentlyDeleted = 0;
double target = 1; // just one
while (currentlyDeleted < target) {
if (nodes.isEmpty()) {
continue;
} else {
Iterator<CacheNode> it = nodes.iterator();
while (it.hasNext() && currentlyDeleted++ < target) {
CacheNode node = it.next();
it.remove();
cache.remove(node.k);
}
if (!it.hasNext()) {
findNextLowestFrequency();
}
}
}
}

private void moveToNextFrequency(CacheNode currentNode, int nextFrequency,
currentNodes.remove(currentNode);
currentNode.frequency = nextFrequency;
}

private void findNextLowestFrequency() {
while (lowestFrequency <= maxFrequency && frequencyList[lowestFrequency].isEmpty()) {
lowestFrequency++;
}
if (lowestFrequency > maxFrequency) {
lowestFrequency = 0;
}
}

private class CacheNode {
public final int k;
public int v;
public int frequency;

public CacheNode(int k, int v, int frequency) {
this.k = k;
this.v = v;
this.frequency = frequency;
}

}
}
``````