lru cache design

Posted on |

leetCode 146, for non-CS background, this kind of problem is out of mind, what is talking about, but I know at all it is about design a data structure to meet some requirements:

first a hash map data structure for key, value operations, e.g. get(), put(); but normal hash map can’t track the most recent used element, so either find a data structure, which can track the recently used element in the hash map; or define some routines to do it.

a data structure to catch recently used

each get(), put() will operate on one special element, and that element should be marked as recently used, and the next element is the least recently used element, which can be overlapped in next operation.

stack and queue have some property to track the most recent element, but they are one-way, not straight forward to manage two neighbor elements.

double linked list is a good choice to track both the most recent element and the least most recent element. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct node{
	int val ;
	int key ;
	Node *pre ;
	Node *next ;
	public Node(int value_, int key_)
	{
		val = value_;
		key = key_ ; 
		pre = NULL ;
		next = NULL;
	}
}
class LRUCache {
	public: 
		list<node*> recent ;
		unorder_map<int, node*>  hash ;
		int capacity ;
		
		LRUCache(int cap): capacity(cap) {}
		
		node* get(int key){
			if(hash.find(key) != hash.end()){
				recent.remove(hash[key])
				recent.push_front(hash[key]); 
				return hash[key] ;
			}
			return -1 ;
		}
		
		void put(int key, int value){
			if(hash.find(key) != hash.end()){
				recent.remove(hash[key]);
				hash[key] =  value; 
				recent.push_front(hash[key]);
			}
			
			node* tmp = new node(value, key); 
			hash[key] = tmp ; 
			recent.remove(tmp); 
			recent.push_front(tmp);
	
			if(hash.size() >= capacity){
				node *tmp2 = recent.back(); 
				hash.erase(tmp2->key); 
			}
		}
	}

routines to track recently used

in this way, the hash is still needed, but define routine to set the latest updated node always at front.

void setHead(Node* n){
    n.next = head ; 
    n.pre = null ;
    if(head != null) head.pre = n ;
    head = n ; 
    if(end == null) end = head;  //only 1 element 
}

when solving real problems, either has a good understand about special data structure, which can solve this problem, or the raw way is to implement routines based on the exisiting input