LFU Cache

LeetCode Q 460 - LFU Cache

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.

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

Example:

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

Solution

Solution 1: HashTable + PriorityQueue

1. HashTable: enable reaching each node in O(1) time;

2. minHeap: extract the least frequent visited node

Code:

class Node {
	int key, value, frequency, timestamp;
	public Node (int k, int v, int t) {
		this.key = k; this.value = v; this.timestamp = t;
		this.frequency = 1;
	}
}

private int timestamp, capacity;
private Map<Integer, Node> map;
private Queue<Node> pq;

Comparator<Node> comparator = new Comparator<>() {
	public int compare (Node a, Node b) {
		int diff = a.frequency - b.frequency;
		if (diff == 0) 
			diff = a.timestamp - b.timestamp;
		return diff;
	}
}

private void updateQueue (Node node) {
	this.pq.remove(node);
	node.frequency++;
	node.timestamp = this.timestamp++;
	this.pq.offer(node);
}

public LFUCache(int capacity) {
	this.map = new HashMap<>();
	this.pq = new PriorityQueue<>(comparator);
	this.timestamp = 0;
	this.capacity = capacity;
}

public int get(int key) {
	if (this.capacity == 0) return -1;
	if (!this.map.containsKey(key)) return -1;

	updateQueue(this.map.get(key));
	return this.map.get(key);
}

public void put(int key, int value) {
	if (this.capacity == 0) return;

	if (this.map.containsKey(key)) {
		this.map.get(key).value = value;
		updateQueue(this.map.get(key));
	} else {
		Node newNode = new Node (key, value);
		if (this.pq.size() == this.capacity)
			this.map.remove(this.pq.poll().key);

		this.map.put(key, newNode);
		this.pq.offer(newNode);
	}
}

Solution 2: HashTables + LinkedHashSet

1. LinkedHashSet: Definition from Java 8 Oracle

   Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)

key words: set + doubly-linked list.

Code:

private Map<Integer, Integer> vals; // key - value pair
private Map<Integer, Integer> freqs; // key - freq pair
private Map<Integer, LinkedListSet<Integer>> lists; // key is freq, value - the items appearing that times.

private int capacity, min;

public LFUCache(int capacity) {
	this.vals = new HashMap<>();
	this.freqs = new HashMap<>();
	this.lists = new HashMap<>();
	this.lists.put(1, new LinkedListSet<>()); // don't forget this
	this.capacity = capacity; this.min = -1;
}

public int get(int key) {
	if (this.capacity == 0) return -1;
	if (!this.vals.containsKey(key)) return -1;

	int freq = this.freqs.get(key);
	this.freqs.put(key, freq + 1);

	if (this.min == freq && this.lists.get(freq))
		this.min++;

	this.lists.get(freq).remove(key);

	if (!this.lists.containsKey(freq + 1)) {
		this.lists.put(freq + 1, new LinkedHashSet<>());
	}
	this.lists.get(freq + 1).add(node);

	return this.vals.get(key);
}

public void put(int key, int value) {
	if (this.capacity == 0) return;
	
	if (!this.vals.containsKey(key)) {
		this.vals.put(key, value);
		get(key);
	} else {
		if (this.vals.size() == this.capacity) {
			int evictIp = this.lists.get(min).iterator().next();
			this.lists.get(min).remove(evictIp);
			this.vals.remove(evictIp);
		}

		this.vals.put(key, value);
		this.freqs.put(key, 1);
		this.min = 1;
		this.lists.get(1).add(key);
	}
}