“This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”
preface
This would work as long as you dare to write your resume in Redis, the interviewer will dare to call you a consortium handwritten LRU, but for handwritten LFU is relatively rare, but, if you can finish the LRU told the interviewer you also master LFU algorithm, then even if you don’t write only speak about, then in the interviewer is also big points!!!!!!
So, today let me help you to master this high frequency test point!!
== warm tips == : the main idea of understanding in the comments in the comments a little shallow, you can copy to their own compiler to have a good look
Big factory interview questions column, there are more and better quality big factory interview questions, can take a look at a look at oh!!
Hand LRU
LRU is relatively simple in general, as long as you master the concept, even if you haven’t written it for a long time, you can remember it!
The general idea of LRU: put the most recently used one in the closest position (far left), so the least used one will naturally be farther away from you (to the right).
So using a bidirectional linked list is not enough, we also need to use a Map to Map keys to corresponding nodes
In a bidirectional linked list, virtual head nodes and tail nodes are used as nodes, so that there is no need to check whether the adjacent nodes exist when adding and deleting nodes.
public class Main {
// Define a two-way linked list
class DoubleLinkedList {
private int key;
private int value;
private DoubleLinkedList next;
private DoubleLinkedList prev;
public DoubleLinkedList(a) {}public DoubleLinkedList(int key, int value) {
this.key = key;
this.value = value; }}// Virtual head node, tail node
private DoubleLinkedList head,tail;
// Store the mapped HashMap
private Map<Integer,DoubleLinkedList> map = new HashMap<>();
/ / capacity
private int capacity;
// The actual number of elements
private int size;
// Data initialization
public Main(int capacity) {
this.capacity = capacity;
head = new DoubleLinkedList();
tail = new DoubleLinkedList();
head.next = tail;
tail.prev = head;
this.map = new HashMap<>();
}
// The exposed get method
public int get(int key) {
// If no key exists, return -1
if(! map.containsKey(key)) {return -1;
}
// If I come here, I have this key, so I put it out
DoubleLinkedList node = map.get(key);
// Since this node is already used, it needs to be moved to the head node
moveToHead(node);
// Return the value
return node.value;
}
// The exposed PUT method
public void put(int key,int value) {
// If the key exists
if (map.containsKey(key)) {
// So get out, replace value, because used, so move the head node
DoubleLinkedList node = map.get(key);
node.value = value;
moveToHead(node);
}else {
// Because the key does not exist
// So create a new node
DoubleLinkedList newNode = new DoubleLinkedList(key, value);
// Add the node to the map and add it to the top node, increasing the total number of elements by 1
map.put(key,newNode);
addHead(newNode);
size++;
// If the total number of elements is greater than the maximum capacity
if (size > capacity) {
// Delete the last node, which is the least used noderemoveLastNode(); }}}// Delete the last node
private void removeLastNode(a) {
// Tail is the virtual tail node, so the node before it is the last node
DoubleLinkedList lastNode = tail.prev;
// Delete the node
removeNode(lastNode);
map.remove(lastNode.key);
size--;
}
// Move the top node
private void moveToHead(DoubleLinkedList node) {
removeNode(node);
addHead(node);
}
// Add the head node
private void addHead(DoubleLinkedList node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// Delete the node
private void removeNode(DoubleLinkedList node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.prev = null;
node.next = null; }}Copy the codeForce button: LRU address
Hand LFU
LFU is not arranged by recent use like LFU. LFU is arranged by frequency of use. In simple terms, LFU is arranged by number of uses (in the case of guaranteed number of uses, recent use), so you need to define an extra count for linked list nodes
public class Main {
// Define the linked list
class Node {
private int key;
private int value;
private int count;
private Node next;
private Node prev;
public Node(a) {}public Node(int key, int value,int count) {
this.key = key;
this.value = value;
this.count = count; }}// Map the key to the corresponding Node
private Map<Integer,Node> keyMap;
// The frequency is mapped to the first node of its corresponding region
private Map<Integer,Node> cntMap;
// Virtual head node and tail node
private Node head,tail;
// Maximum capacity
private int capacity;
// The actual number of elements
private int size;
/ / initialization
public Main(int capacity) {
this.capacity = capacity;
this.head = new Node();
this.tail = new Node();
head.next = tail;
tail.prev = head;
keyMap = new HashMap<>();
cntMap = new HashMap<>();
}
// Expose the get method
public int get(int key) {
// If the capacity is 0 or there is no key, return -1
if (capacity == 0| |! keyMap.containsKey(key)) {return -1;
}
// Remove the node corresponding to key
Node node = keyMap.get(key);
// Update the usage frequency
updateNode_fre(node);
/ / return a value
return node.value;
}
// Update the node usage frequency
private void updateNode_fre(Node node) {
// Old usage frequency
int oldCnt = node.count;
// New usage frequency
int newCnt = node.count + 1;
// Which node to save the insert before
// Because the insertion location may or may not be the first node of the region
Node next = null;
// If the current node is the first node of the frequency
if (cntMap.get(oldCnt) == node) {
// If there is a next node in the current region, set the first node in the current region to the next node
if (node.next.count == node.count) {
cntMap.put(oldCnt,node.next);
}else {
// If there is no next node, then the region needs to be deleted. Because this node frequency is about to be updated
cntMap.remove(oldCnt);
}
// If no new zone exists
if (cntMap.get(newCnt) == null) {
// Then create a new region and set this node as the first node
cntMap.put(newCnt,node);
// The frequency should be updated
node.count++;
// No further action is required
return;
}else {
// If so, you need to delete the node and set next as the first node of the new regionremoveNode(node); next = cntMap.get(newCnt); }}else {
// If not, delete the node
removeNode(node);
// Next is equal to the first node of the new area frequency if there is a new area frequency
// If not, insert in front of the current frequency is ok
if (cntMap.get(newCnt) == null) {
next = cntMap.get(oldCnt);
}else{ next = cntMap.get(newCnt); }}// All nodes that can come here are not updated
node.count++;
// Update the frequency mapping
cntMap.put(newCnt,node);
// Insert before the specified node
addNode(node,next);
}
// Expose the put method
public void put(int key,int value) {
// If the capacity is 0, the key-value pair cannot be put
if (capacity == 0) return;
// If there is a key
if (keyMap.containsKey(key)) {
// Fetch the node, replace value, and update
Node node = keyMap.get(key);
node.value = value;
updateNode_fre(node);
}else {
// If the number of elements is equal to the maximum capacity
if (size == capacity) {
// Then you need to delete the mo tail node
deleteLastNode();
}
// Create a new node. The default value is 1
Node newNode = new Node(key, value,1);
// Insert at the head of the count=1 region because it is a new node
Node next = cntMap.get(1);
// But if there is no area, then insert directly into
if (next == null) {
next = tail;
}
// Insert, update
addNode(newNode,next);
keyMap.put(key,newNode);
cntMap.put(1,newNode); size++; }}// Add a node
private void addNode(Node node, Node next) {
node.next = next;
node.prev = next.prev;
next.prev.next = node;
next.prev = node;
}
// Delete the last node
private void deleteLastNode(a) {
Node lastNode = tail.prev;
// If this node is the only node in this area, then this area needs to be deleted
if (cntMap.get(lastNode.count) == lastNode) {
cntMap.remove(lastNode.count);
}
removeNode(lastNode);
keyMap.remove(lastNode.key);
size--;
}
// Delete the node
private void removeNode(Node node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.next = null;
node.prev = null; }}Copy the codeForce button: LFU address
The last
I am aCode pipi shrimpI am a mantis shrimp lover who loves to share knowledge. I will keep updating my blog in the future. I look forward to your attention!!
Creation is not easy, if this blog is helpful to you, I hope you can == a key three! ==, thanks for your support, see you next time ~~~
Share the outline
Big factory interview questions column
