Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 52
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Implement an LRU (Least Recently Used) cache. It should be able to be initialized with a cache size n, and contain the following methods:

* `set(key, value)`: sets key to value. If there are already n items in the cache and we are adding a new item, then it should also remove the least recently used item.
* `get(key)`: gets the value at key. If no such key exists, return null.
Each operation should run in O(1) time.

Pull request description:
Day52
Resolves #113 .

Patch:
diff --git a/README.md b/README.md
index bb37274..bc3c968 100644
--- a/README.md
+++ b/README.md
@@ -62,4 +62,5 @@ problems from
 * [Day 47](https://github.com/vaskoz/dailycodingproblem-go/issues/105)
 * [Day 49](https://github.com/vaskoz/dailycodingproblem-go/issues/107)
 * [Day 50](https://github.com/vaskoz/dailycodingproblem-go/issues/110)
+* [Day 52](https://github.com/vaskoz/dailycodingproblem-go/issues/113)
 * [Day 53](https://github.com/vaskoz/dailycodingproblem-go/issues/114)
diff --git a/day52/problem.go b/day52/problem.go
new file mode 100644
index 0000000..f281b8f
--- /dev/null
+++ b/day52/problem.go
@@ -0,0 +1,49 @@
+package day52
+
+import (
+	"container/list"
+)
+
+// Cache specifies a generic cache interface of key-value pairs.
+type Cache interface {
+	Set(key, value interface{})
+	Get(key interface{}) interface{}
+}
+
+type kvPair struct {
+	k, v interface{}
+}
+
+type lruCache struct {
+	data     map[interface{}]*list.Element
+	l        *list.List
+	capacity int
+}
+
+func (lc *lruCache) Set(key interface{}, value interface{}) {
+	if elem, found := lc.data[key]; found {
+		lc.l.MoveToFront(elem)
+		elem.Value = kvPair{k: key, v: value}
+		return
+	}
+	if len(lc.data) == lc.capacity { // evict oldest
+		oldest := lc.l.Back()
+		delete(lc.data, oldest.Value.(kvPair).k)
+		lc.l.Remove(oldest)
+	}
+	e := lc.l.PushFront(kvPair{k: key, v: value})
+	lc.data[key] = e
+}
+
+func (lc *lruCache) Get(key interface{}) interface{} {
+	if elem, found := lc.data[key]; found {
+		lc.l.MoveToFront(elem)
+		return elem.Value.(kvPair).v
+	}
+	return nil
+}
+
+// NewLRU returns a Cache implementation that behaves as a LRU.
+func NewLRU(capacity int) Cache {
+	return &lruCache{make(map[interface{}]*list.Element), list.New(), capacity}
+}


Test patch:
diff --git a/day52/problem_test.go b/day52/problem_test.go
new file mode 100644
index 0000000..592d3e4
--- /dev/null
+++ b/day52/problem_test.go
@@ -0,0 +1,49 @@
+package day52
+
+import "testing"
+
+func TestLRUCache(t *testing.T) {
+	lru := NewLRU(3)
+	for i := 0; i < 6; i++ {
+		lru.Set(i, i+1)
+	}
+	for i := 0; i < 3; i++ {
+		if v := lru.Get(i); v != nil {
+			t.Errorf("Expected these to be evicted")
+		}
+	}
+	for i := 3; i < 6; i++ {
+		if v := lru.Get(i); v != i+1 {
+			t.Errorf("Expected the values to remain")
+		}
+	}
+	for i := 3; i < 6; i++ {
+		lru.Set(i, 10*i)
+	}
+	for i := 3; i < 6; i++ {
+		if v := lru.Get(i); v != i*10 {
+			t.Errorf("Expected the values to modify")
+		}
+	}
+}
+
+func BenchmarkLRUCache(b *testing.B) {
+	lru := NewLRU(3)
+	for bm := 0; bm < b.N; bm++ {
+		for i := 0; i < 6; i++ {
+			lru.Set(i, i+1)
+		}
+		for i := 0; i < 3; i++ {
+			lru.Get(i)
+		}
+		for i := 3; i < 6; i++ {
+			lru.Get(i)
+		}
+		for i := 3; i < 6; i++ {
+			lru.Set(i, 10*i)
+		}
+		for i := 3; i < 6; i++ {
+			lru.Get(i)
+		}
+	}
+}