Two days ago, I failed to implement the optimized LRU cache in coding interview due to panic and stopped by the interviewer. Yes, I suck at coding interviews. I have implemented LRU cache before, so I know how it works and of course know how to implement it. But if you never heard of it, I think this explanation is enough.
Brief definition
LRU Cache is a combination of hash map and queue. Hash map will store the elements by keys and values while the queue keeps track the least recently used keys. We will implement the queue using doubly linked list.
Rules
Track each key usage
Set max capacity that LRU cache will handle
If the size is over the defined capacity, remove the least recently used data, and store the new data
Accessed (get/set) the data means we use the data so mark it as the most recently used data
Node Structure
Node structure will store the key, value, and its previous & next nodes (doubly linked list).
1
2
3
4
5
6
7
8
9
10
11
12
13
type Node struct {
Key int Value int Prev *Node
Next *Node
}
funcNewNode(key, value int) *Node {
return&Node{
Key: key,
Value: value,
}
}
LRU Structure
LRU will store the capacity, size (optional), the stored data, and it will track the most and the least recently used using tail and head pointer. Size is optional since you can use len(v Type) method.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type LRU struct {
capacity int size int data map[int]*Node
tail *Node
head *Node
}
funcNewLRU(capacity int) *LRU {
return&LRU{
capacity: capacity,
size: 0,
data: make(map[int]*Node),
}
}
Queue Operation
Push Tail
Push tail will append the given node to the queue.
1
2
3
4
5
6
7
8
9
10
11
12
func (l *LRU) pushTail(n *Node) {
if l.head ==nil {
l.head = n
l.tail = n
return }
l.tail.Next = n
n.Prev = l.tail
l.tail = n
l.tail.Next = nil}
Pop Head
Pop head will remove the head (least recently used) node.
1
2
3
4
5
6
7
8
9
10
11
12
func (l *LRU) popHead() *Node {
ret := l.head
if l.head == l.tail {
l.head = nil } else {
l.head = l.head.Next
l.head.Prev = nil }
return ret
}
Pop Tail
Pop tail will remove the tail (most recently used) node. We will not use this method directly, but it will be used later whenever user reset the tail value.
1
2
3
4
5
6
7
8
9
10
11
12
func (l *LRU) popTail() *Node {
ret := l.tail
if l.head == l.tail {
l.head = nil } else {
l.tail = l.tail.Prev
l.tail.Next = nil }
return ret
}
Pop
This Pop method will receive node that we want to pop.
1
2
3
4
5
6
7
8
9
10
11
12
func (l *LRU) pop(n *Node) *Node {
switch n {
case l.head:
return l.popHead()
case l.tail:
return l.popTail()
}
n.Next.Prev = n.Prev
n.Prev.Next = n.Next
return n
}
Now all the queue operations has defined, let’s implement the main operation of the LRU.
Set
Set method will store the given value identified by the given key. Remember the 3rd and 4th rules.
If the size is over the defined capacity, remove the least recently used data, and store the new data
Accessed (get/set) the data means we use the data so mark it as the most recently used data
func (l *LRU) Set(key, value int) {
// check if the key exists
// if it exists, we need to remove it
// then we append it to the queue
// 4th rule (mark it as the most recently used)
if val, isOk := l.data[key]; isOk {
// this is the reason why we need to use popTail
l.pop(val)
l.size-- }
// 3rd rule
if l.size >= l.capacity {
n := l.popHead()
delete(l.data, n.Key)
l.size-- }
// push new data
n :=NewNode(key, value)
l.data[key] = n
l.pushTail(n)
l.size++}
Get
Get method will return the stored value depends on the given key. Remember the 4th rule.
Accessed (get/set) the data means we use the data so mark it as the most recently used data
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (l *LRU) Get(key int) int {
val, isOk := l.data[key]
if !isOk {
return-1 }
// remove it
l.pop(val)
// then mark it as the most recently used
l.pushTail(val)
return val.Value
}
Lastly, to ensure our queue rotation is correct, let’s implement the showQueue method.
1
2
3
4
5
6
7
8
func (l *LRU) ShowQueue() {
fmt.Printf("Least ")
for n := l.head ; n != l.tail ; n = n.Next {
fmt.Printf("%v -> ", n.Key)
}
fmt.Println(l.tail.Key, "Most")
}
package main
import"fmt"type Node struct {
Key int Value int Prev *Node
Next *Node
}
funcNewNode(key, value int) *Node {
return&Node{
Key: key,
Value: value,
}
}
type LRU struct {
capacity int size int data map[int]*Node
tail *Node
head *Node
}
funcNewLRU(capacity int) *LRU {
return&LRU{
capacity: capacity,
size: 0,
data: make(map[int]*Node),
}
}
func (l *LRU) pushTail(n *Node) {
if l.head ==nil {
l.head = n
l.tail = n
return }
l.tail.Next = n
n.Prev = l.tail
l.tail = n
l.tail.Next = nil}
func (l *LRU) popHead() *Node {
ret := l.head
if l.head == l.tail {
l.head = nil } else {
l.head = l.head.Next
l.head.Prev = nil }
return ret
}
func (l *LRU) popTail() *Node {
ret := l.tail
if l.head == l.tail {
l.head = nil } else {
l.tail = l.tail.Prev
l.tail.Next = nil }
return ret
}
func (l *LRU) pop(n *Node) *Node {
switch n {
case l.head:
return l.popHead()
case l.tail:
return l.popTail()
}
n.Next.Prev = n.Prev
n.Prev.Next = n.Next
return n
}
func (l *LRU) Set(key, value int) {
// check if the key exists
// if it exists, we need to remove it
// then we append it to the queue
// 4th rule (mark it as the most recently used)
if val, isOk := l.data[key]; isOk {
// this is the reason why we need to use popTail
l.pop(val)
l.size-- }
// 3rd rule
if l.size >= l.capacity {
n := l.popHead()
delete(l.data, n.Key)
l.size-- }
// push new data
n :=NewNode(key, value)
l.data[key] = n
l.pushTail(n)
l.size++}
func (l *LRU) Get(key int) int {
val, isOk := l.data[key]
if !isOk {
return-1 }
// remove it
l.pop(val)
// then mark it as the most recently used
l.pushTail(val)
return val.Value
}
func (l *LRU) ShowQueue() {
fmt.Printf("Least ")
for n := l.head; n != l.tail; n = n.Next {
fmt.Printf("%v -> ", n.Key)
}
fmt.Println(l.tail.Key, "Most")
}
funcmain() {
lru :=NewLRU(3)
lru.Set(1, 1)
lru.Set(2, 2)
lru.Set(3, 3)
// Least 1 -> 2 -> 3 Most
lru.ShowQueue()
// 2
fmt.Println(lru.Get(2))
// Least 1 -> 3 -> 2 Most
lru.ShowQueue()
lru.Set(1, 100)
// Least 3 -> 2 -> 1 Most
lru.ShowQueue()
lru.Set(4, 4)
// Least 2 -> 1 -> 4 Most
lru.ShowQueue()
}
Thank you for reading!
···
Love This Content?
Any kind of supports is greatly appreciated! Kindly support me via Bitcoin, Ko-fi, Trakteer, or just continue to read another content. You can write a response via Webmention and let me know the URL via Telegraph.
