text: Hi,
  At the moment, the explainations are written as comments in the code. I'll probably move them as text when I have some time. Feel free to leave a comment.
  import java.util.HashMap; import java.util.Map; /** * A cache used to store and retrieve key/value pairs using the * Least Frequently Used policy for choosing which key to remove * when the cache is full. * <p> * The cache has a fixed size. When a new key needs to be stored * and the cache is full, the Least Frequently Used is discarded. * If several keys have the same frequency, the Least Recently * Used is discarded. * </p><p> * This implementation uses a HashMap and two kinds of * doubly-linked lists. This allows all operations run in O(1) * (see each operation comment for detailled explanations). * </p><p> * So, the LFUCache consists of a HashMap which associates each * key with a unique QueueNode and of a doubly-linked list of * FrequencyNodes. * </p><p> * Each FrequencyNode contains its frequency, a pointer to the * previous and next FrequencyNodes in the list and two pointers * (head and tail) to a doubly-linked list of QueueNodes which * contains all the QueueNodes associated with keys of the same * frequency as the FrequencyNode. * </p><p> * Each QueueNode stores its key/value pair, pointers to the * previous and next QueueNodes in the list of QueueNodes of * same frequency and a pointer to the FrequencyNode which * contains this list. * </p><p> * Finally, I used sentinel nodes in order to simplify the code. * With sentinel nodes, you can safely link/unlink in the list * without ever needing to check for null pointers. * </p><p> * <b>Class Invariants:</b> * </p><p> * - There's only one QueueNode per key in the cache. This is * ensured because QueueNodes are created only when a new key * is added. * </p><p> * - FrequencyNodes are linked in increasing order of frequency. * This is true because we always add FrequencyNodes by increment * of frequency by one, one at a time and only if needed. * Similarly, FrequencyNodes are removed one at a time, without * changing the order of the list. * </p><p> * - For any FrequencyNode (except the sentinel), the list of * QueueNodes has at least one element. We ensure that by * checking and removing empty FrequencyNodes after each * frequency update. * </p><p> * - Each list of QueueNodes is sorted from Least Recently * Used (head.next) to Most Recently Used (tail). That is true * because nodes are always added at the tail. And when we * remove some, the order doesn't change. * </p> */ public class LFUCache { /** * A node to store all the QueueNodes with the same frequency. * <p> * The list of QueueNodes contains at least one element unless * this Frequency node is a sentinel. QueueNodes are always * added at the end of the list to ensure that they are sorted * from Least Recently Used (head) to Most Recently Used (tail). */ private static class FrequencyNode { /** * This node's frequency */ final int freq; /** * Link to the previous node in the list (with lower frequency) */ FrequencyNode prev; /** * Link to the next node in the list (with higher frequency) */ FrequencyNode next; /** * Link to the head of the list of QueueNodes with the same * frequency (head is the Least Recently used) */ QueueNode head; /** * Link to the tail of the list of QueueNodes with the same * frequency (tail is the Most Recently used) */ QueueNode tail; /** * Constructs a sentinel FrequencyNode with an enmpty list * of QueueNodes. */ public FrequencyNode(int freq) { this.freq = freq; // Sentinel nodes to simplify the code this.head = new QueueNode(); this.tail = new QueueNode(); this.head.next = tail; this.tail.prev = head; } /** * Constructs a FrequencyNode and adds it between prev and next. * Requires that prev.freq + 1 = this.freq < next.freq. */ public FrequencyNode(int freq, FrequencyNode prev, FrequencyNode next) { this(freq); this.prev = prev; this.next = next; prev.next = this; next.prev = this; } /** * Removes the given node from the list of QueueNodes. * If the QueueNode list becomes empty, remove this * FrequencyNode from the cache (unless it's the head). * This is done easily by linking prev and next. * This operation takes O(1). * Requires that node.parent = this. */ public void removeNode(QueueNode node) { node.prev.next = node.next; node.next.prev = node.prev; if ((freq != 0) && (head.next == tail)) { prev.next = next; next.prev = prev; } } /** * Moves the specified node at tail of the FrequencyNode * with frequency this.freq + 1. If no FrequencyNode * exist with that frequency (we only need to check the * next one), one is created and inserted just after * the current one. The queueNode is then moved to the * FrequencyNode with the incremented frequency. * The current FrequencyNode is then removed if needed. * This operation takes O(1). * Requires that node.parent = this. * This has the side-effect that node will point to * the FrequencyNode with frequency = this.freq + 1. */ public void incrementFreq(QueueNode node) { FrequencyNode nextNode = next; if (nextNode.freq != freq + 1) { nextNode = new FrequencyNode(freq + 1, this, next); } removeNode(node); nextNode.addLast(node); } /** * Helper method to link a QueueNode at the tail of the list. * This operation takes O(1). * This has the side-effect that node will point to the * current node. */ private void addLast(QueueNode node) { node.prev = tail.prev; node.next = tail; tail.prev.next = node; tail.prev = node; node.parent = this; } } /** * A mutable class used to construct a Deque. * The QueueNode stores the key and its associated value as well * as pointers to the previous and next nodes in the queue and * a pointer to the FrequencyNode holding the queue. */ private static class QueueNode { /** * The key that this node belongs to */ final int key; /** * The value associated to the key. This value can change via * the {@code put} method of the {@LFUCache} class. */ int value; /** * The previous node in the queue */ QueueNode prev; /** * The next node in the queue */ QueueNode next; /** * The FrequencyNode holding this queue */ FrequencyNode parent; /** * Constructs a sentine QueueNode. */ public QueueNode() { this.key = Integer.MIN_VALUE; this.value = Integer.MIN_VALUE; this.parent = null; } /** * Constructs a QueueNode and adds it to the given FrequencyNode. */ public QueueNode(int key, int value, FrequencyNode parent) { this.key = key; this.value = value; this.parent = parent; this.parent.addLast(this); } /** * Removes this QueueNode from its parent's queue. * This operation takes O(1). */ public void removeFromQueue() { parent.removeNode(this); } /** * Moves this QueueNode to the FrequencyNode with a * frequency increased by one and removes its current * parent from the LFUCache if needed. * This operation takes O(1). */ public void incrementFreq() { parent.incrementFreq(this); } } /** * A map to associate each key to a unique QueueNoode */ private Map<Integer, QueueNode> infoByKey; /** * The sentinel node starting the list of FrequencyNodes. * It has a frequency of 0. */ private FrequencyNode head; /** * The maximum number of unique keys that the cache can hold */ private final int capacity; /** * Constructs an empty LFUCache with the given capacity. * * @param capacity the maximum number of unique keys that the cache can hold */ public LFUCache(int capacity) { this.capacity = capacity; this.infoByKey = new HashMap<>(); this.head = new FrequencyNode(0); // Sentinel node to simplify the implementation FrequencyNode sentinel = new FrequencyNode(Integer.MAX_VALUE); this.head.next = sentinel; sentinel.prev = this.head; } /** * Returns the value associated with the given key or -1 * if the key is not in the cache. if the key is present, * its frequency is incremented. * This operation takes O(1). * * @param key a key * @return the value associated with the given key or -1 * if the key is not in the cache */ public int get(int key) { if (!infoByKey.containsKey(key)) { return -1; } QueueNode keyNode = infoByKey.get(key); keyNode.incrementFreq(); return keyNode.value; } /** * Adds the key/value pair to the cache or just update the * value if the key is already present. * If the key is new and the cache is full, the Least * Frequently Used key/value pair is discarded first. * This operation takes O(1). * * @param key a key. This must be a positive number * @param value the value to associate with the key */ public void put(int key, int value) { if (capacity == 0) { return; } QueueNode keyNode; if (infoByKey.containsKey(key)) { keyNode = infoByKey.get(key); keyNode.value = value; } else { if (infoByKey.size() == capacity) { deleteLFULRUKey(); } keyNode = new QueueNode(key, value, head); infoByKey.put(key, keyNode); } keyNode.incrementFreq(); } /** * Removes the Least Frequently Used key from the cache. If there's more than * one key with the lowest frequency, the Least Recently Used is removed. * This operation takes O(1). */ private void deleteLFULRUKey() { // The nodes with the LFU keys are in the FrequencyNode just after head. // This node queue has at least one element (class invariant) and the first // one is the least frequently used since we always add new elements at the // tail. QueueNode nodeToRemove = head.next.head.next; nodeToRemove.removeFromQueue(); infoByKey.remove(nodeToRemove.key); } /** * Your LFUCache object will be instantiated and called as such: * LFUCache obj = new LFUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */ public static void main(String[] args) { LFUCache cache = new LFUCache(2); cache.put(1, 1); cache.put(2, 2); System.out.println(cache.get(1)); cache.put(3, 3); System.out.println(cache.get(2)); System.out.println(cache.get(3)); cache.put(4, 4); System.out.println(cache.get(1)); System.out.println(cache.get(3)); System.out.println(cache.get(4)); } }