Created
June 20, 2019 13:18
-
-
Save aherve/598e68fe380a077b18c43fec204d77fd to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Go coding exercise: implement LRU Caching service | |
package main | |
func main() {} | |
type QueueNode struct { | |
next *QueueNode | |
prev *QueueNode | |
key string | |
} | |
type DataPoint struct { | |
value string | |
qNode *QueueNode | |
} | |
type Queue struct { | |
head *QueueNode | |
tail *QueueNode | |
length uint | |
maxLength uint | |
} | |
type Cache struct { | |
data map[string]DataPoint | |
queue Queue | |
} | |
func NewCache(maxSize uint) Cache { | |
return Cache{make(map[string]DataPoint), Queue{nil, nil, 0, maxSize}} | |
} | |
func (cache *Cache) Get(key string) string { | |
data, ok := cache.data[key] | |
if ok { | |
defer cache.queue.hit(key, &data) | |
} | |
return data.value | |
} | |
func (cache *Cache) Set(key, value string) { | |
data, ok := cache.data[key] | |
if ok { | |
data.value = value | |
cache.queue.hit(key, &data) | |
} else { | |
point := DataPoint{value, nil} | |
toRemove := cache.queue.hit(key, &point) | |
if toRemove != "" { | |
delete(cache.data, toRemove) | |
} | |
cache.data[key] = point | |
} | |
} | |
func (queue *Queue) hit(key string, dp *DataPoint) string { | |
qNode := dp.qNode | |
// 1. Update el | |
if qNode != nil { | |
if qNode.next == nil { | |
// node is already tail: nothing to do | |
return "" | |
} else if qNode.prev == nil { | |
next, tail := qNode.next, queue.tail | |
queue.head = next | |
queue.tail = qNode | |
qNode.next = nil | |
qNode.prev = tail | |
next.prev = nil | |
tail.next = qNode | |
} else { | |
prev, next, tail := qNode.prev, qNode.next, queue.tail | |
prev.next = next | |
next.prev = prev | |
tail.next = qNode | |
qNode.next = nil | |
qNode.prev = tail | |
queue.tail = qNode | |
} | |
return "" | |
} | |
// 2. New el | |
newNode := QueueNode{queue.tail, nil, key} | |
dp.qNode = &newNode | |
if queue.length == 0 { | |
queue.tail = &newNode | |
queue.head = &newNode | |
queue.length = 1 | |
} else if queue.length < queue.maxLength { | |
// 2.1 has space | |
queue.length++ | |
queue.tail.next = &newNode | |
queue.tail = &newNode | |
} else { | |
// 2.1 no space left | |
oldHeadKey := queue.head.key | |
queue.tail.next = &newNode | |
queue.tail = &newNode | |
queue.head = queue.head.next | |
return oldHeadKey | |
} | |
return "" | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment