The recent spring recruitment advance batch will also start, I will push algorithm + computer based articles, as soon as possible to push some interview related articles
About last March, when I was looking for spring recruitment internship, I met Ali once, and then the first part was to write algorithm questions. However, to my surprise, I was hooked on LRU cache algorithm, which is an algorithm THAT I am very familiar with… Let’s share a wave today, and you may not be able to do it!
One, diligent in using the brain, lazy in action
When doing the problem, I think too much, feel the design of a LRU(Least recently used) cache algorithm, not so simple ah, so understand the wrong meaning of the question (I am also take, can also understand into such ，，，，), their wave of operation to write a lot of code, then stuck, and then to look carefully at the problem, It is so simple to design an LRU cache algorithm.
According to the truth, if you are really familiar with this algorithm, you can write it in ten minutes. However, although I understand the idea of LRU cache algorithm and know the specific steps, BUT I have never written it before, resulting in writing, very unskilled, that is to say, Feeling like you’re going to be able to write it perfectly in code is not the same thing.
So here to remind you, if you can, be sure to use their own code to achieve what you think you can. Don’t think you understand the idea, you don’t need to write code, alone through the code, is really understand, and when the interview, you need to hit the code in the notepad, not to give you the compiler…
But today I take you to use the code to implement the LRU cache algorithm, and provide the optimal solution, later you encounter this type of problem, ensure that you perfect seconds kill it.
Topic describes
Design and implement a least recently used (LRU) cache data structure. It should support the following operations: GET and PUT.
Get (key) – Gets the value of the key if it exists in the cache (always positive), otherwise returns -1.
Put (key, value) – Set or insert a value if the key does not exist. When the cache reaches its capacity, it should invalidate the least recently used items before inserting new ones.
Advanced:
Can you perform two operations in O(1) time complexity?
Example:
LFUCache cache = new LFUCache(2 /* capacity (cache capacity) */); cache.put(1, 1); cache.put(2, 2); cache.get(1); // return 1 cache. Put (3, 3); // remove key 2 cache.get(2); // return -1 (key 2 not found) cache.get(3); // return 3 cache. Put (4, 4); // remove key 1 cache.get(1); // return -1 (key 1 not found) cache.get(3); // return 3 cache.get(4); / / return 4Copy the codeBasic edition: single linked list to solve
We want to delete the least recently used nodes, and an easy way to do this is to use a single linked list as a data structure. When we perform the put operation, the following situations occur:
1, If the put(key,value) already exists in the list, then we need to delete the old data from the list and insert the new data into the head of the list. ,
2, If the data to put(key,value) does not exist behind the list, we need to determine whether the cache is full. If so, delete the node at the end of the list, and insert the new data into the head of the list. If not, insert data directly into the head of the list.
For get operations, the following happens
1. If the data to get(key) exists in the list, return value, delete the node, and insert it into the head of the list.
If the key to get(key) does not exist behind the list, return -1.
The general idea is this, do not feel very simple, let you write, ten minutes you may not write out. The specific code, in order not to affect the reading, I put it at the end of the article.
Time and space complexity analysis
For this method, both PUT and GET need to traverse the list to see if the data exists, so the time complexity is O(n). The space complexity is O(1).
Space for time
In practical applications, when we want to read a data, we will first determine whether the data exists in the cache, if it does, we will return, if it does not exist, we will go to other places to find the data (such as disk), after finding the data stored in the cache, and then return.
Therefore, in practical applications, PUT operation is generally accompanied by GET operation, that is to say, the number of GET operation is relatively large, and the hit ratio is relatively high, and the number of PUT operation is relatively small. We can consider the way of space for time to speed up our GET operation.
For example, we can use an extra hash table (such as a HashMap) to store key-values, so that our get operation can find the target node in O(1) time and return the value.
However, can get really be done in O(1) time with a hash table?
With a hash table, although we can find the target in the O (1) the time element, can, we also need to delete the element, the element is inserted and to list the head ah, delete an element, we need to go to the elements of the precursor, and then locate precursors to this element, is the need to O (n) time complexity.
The end result is that, with hash tables, the worst time is O(1), and the space is O(n).
Bidirectional linked list + hash table
We have been able to find the O (1) time complexity to delete the node, the reason also take O (n) time complexity to delete, mainly is the time is spent on node precursor to find, in order to solve this problem, in fact, we can replace singly linked lists with double linked list, so, we can well solve the problem, moreover, When you switch to a double-linked list, you’ll find that it’s a lot easier to do than a single-linked list.
Therefore, our final solution is: double linked list + hash table. By using the combination of these two data structures, our GET operation can be completed in O(1) time complexity. Since the nodes to be removed by the PUT operation are usually tail nodes, we can use a variable tai to record the position of the tail node. In this case, our PUT operation can also be completed in O(1) time.
The specific code is as follows:
Class LRUNode{String key; Object value; LRUNode next; LRUNode pre; public LRUNode(String key, Object value) { this.key = key; this.value = value; }}Copy the code// LRU public class LRUCache { Map<String, LRUNode> map = new HashMap<>(); LRUNode head; LRUNode tail; Int capacity = 1; int capacity = 1; public LRUCache(int capacity) { this.capacity = capacity; } public void put(String key, Object value) {if (head == null) {
head = new LRUNode(key, value);
tail = head;
map.put(key, head);
}
LRUNode node = map.get(key);
if(node ! = null) {// Update node.value = value; RemoveAndInsert (node); }else{ LRUNode tmp = new LRUNode(key, value); // If overflow occursif(map.size() >= capacity) {// remove map.remove(tail.key); // Delete the tail node tail = tail.pre; tail.next = null; } map.put(key, tmp); // Insert tmp.next = head; head.pre = tmp; head = tmp; } } public Object get(String key) { LRUNode node = map.get(key);if(node ! = null) {removeAndInsert(node);return node.value;
}
returnnull; } private void removeAndInsert(LRUNode node) {private void removeAndInsert(LRUNode node) {private void removeAndInsert(LRUNode node) {private void removeAndInsert(LRUNode node)if (node == head) {
return;
} else if (node == tail) {
tail = node.pre;
tail.next = null;
} else{ node.pre.next = node.next; node.next.pre = node.pre; } // Insert the head node node.next = head; node.pre = null; head.pre = node; head = node; }}Copy the codeIt is important to note that for linked list data structures, head and tail nodes are special points. If the nodes to be deleted are either head or tail nodes, they should be processed first.
Let me put the single linked list version here
Class LRUNode{String key; Object value; LRUNode next; public LRUNode(String key, Object value) { this.key = key; this.value = value; }} RLU public class LRUCache {LRUNode head; int size = 0; Int capacity = 0; Public LRUCache(int capacity) {this.capacity = capacity; } public Object get(String key) { LRUNode cur = head; LRUNode pre = head; // Point to the precursor of the node to be deleted // find the corresponding node and put the corresponding node at the head of the list // consider special cases firstif(head == null)
return null;
if(cur.key.equals(key))
returncur.value; Cur = cur.next;while(cur ! = null) {if (cur.key.equals(key)) {
break; } pre = cur; cur = cur.next; } // the node is not foundif (cur == null)
returnnull; Pre.next = cur.next; // Insert a cur.next = head; head = cur;returncur.value; } public void put(String key, Object value) {// If the maximum capacity is 1, there is no way ，，，，，if(capacity == 1) { head = new RLUNode(key, value); } LRUNode cur = head; LRUNode pre = head; // Check if the list is emptyif (head == null) {
head = new RLUNode(key, value);
return; } // Check whether the node exists // Check whether the first node is specialif (head.key.equals(key)) {
head.value = value;
return;
}
cur = cur.next;
while(cur ! = null) {if (cur.key.equals(key)) {
break; } pre = cur; cur = cur.next; } // The key of the node to be inserted already exists, so update the value and place it in the first nodeif(cur ! = null) { cur.value = value; pre.next = cur.next; cur.next = head; head = cur; }elseLRUNode TMP = new LRUNode(key, value); // The node does not existif(size >= capacity) {// Remove the last node cur = head;while(cur.next ! = null && cur.next.next ! = null) { cur = cur.next; } cur.next = null; tmp.next = head; head = tmp; }}}}Copy the codeIf you need time, it is highly recommended to implement a wave yourself manually.
Brother Dei, if you think my writing is good, please do me a favor
1. Follow my original wechat public account “Shuaidi Play programming”, push technical articles of dry goods on time every day, focus on writing algorithm + basic knowledge of computer (computer network + operating system + database +Linux), I heard that those who are concerned will also become excellent.
Give me a thumbs up, can let more people see this article, by the way inspire me, hee hee.
The author is simple
Author: Hello, everyone, I am Shuaidi, from the university, self-study all the way, know the importance of algorithm, computer basic knowledge, so I applied for a microstar public account “Shuaidi play programming”, specializing in writing these basic knowledge, improve our internal skills, Shuaidi look forward to your attention, and study with me. Reprint description: Without authorization, reprint is prohibited
Finally, I recommend Github, which has a collection of high-quality programming books: