Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 67
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Implement an LFU (Least Frequently 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 frequently used item. If there is a tie, then the least recently used key should be removed.
`get(key)`: gets the value at key. If no such key exists, return null.
Each operation should run in O(1) time.

Pull request:
Day67
Resolves #143.

Patch:
diff --git a/README.md b/README.md
index 8e30726..42bc6d4 100644
--- a/README.md
+++ b/README.md
@@ -76,3 +76,4 @@ problems from
 * [Day 63](https://github.com/vaskoz/dailycodingproblem-go/issues/136)
 * [Day 65](https://github.com/vaskoz/dailycodingproblem-go/issues/139)
 * [Day 66](https://github.com/vaskoz/dailycodingproblem-go/issues/141)
+* [Day 67](https://github.com/vaskoz/dailycodingproblem-go/issues/143)
diff --git a/day67/problem.go b/day67/problem.go
new file mode 100644
index 0000000..3b31ebe
--- /dev/null
+++ b/day67/problem.go
@@ -0,0 +1,118 @@
+package day67
+
+import (
+	"container/list"
+)
+
+type freqNode struct {
+	accessCount int
+	siblings    *list.List // is a list of keyValueNodes
+}
+
+type keyValueNode struct {
+	key      interface{}
+	value    interface{}
+	parent   *list.List
+	freqElem *list.Element
+}
+
+// LFUCache is a least-frequently-used cache.
+// Every operation runs in O(1) time.
+type LFUCache struct {
+	freqList *list.List // is a list of freqNodes
+	lookup   map[interface{}]*list.Element
+	capacity int
+}
+
+// Set 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 frequently used item.
+// If there is a tie, then the least recently used key should be removed.
+func (lfu *LFUCache) Set(key, value interface{}) {
+	if keyValNode, found := lfu.lookup[key]; found {
+		// update existing
+		kvn := keyValNode.Value.(*keyValueNode)
+		kvn.parent.Remove(keyValNode)
+		kvn.value = value
+		fqnNext := kvn.freqElem.Next()
+		fqn := kvn.freqElem.Value.(*freqNode)
+		if fqnNext == nil || fqnNext.Value.(*freqNode).accessCount != fqn.accessCount+1 {
+			newFreq := &freqNode{accessCount: fqn.accessCount + 1, siblings: list.New()}
+			e := newFreq.siblings.PushBack(kvn)
+			lfu.lookup[key] = e
+			lfu.freqList.InsertAfter(newFreq, kvn.freqElem)
+		} else {
+			e := fqnNext.Value.(*freqNode).siblings.PushBack(kvn)
+			lfu.lookup[key] = e
+		}
+		if kvn.parent.Len() == 0 {
+			lfu.freqList.Remove(kvn.freqElem)
+		}
+		return
+	} else if len(lfu.lookup) == lfu.capacity {
+		// evict the LFU first.
+		lowestAccess := lfu.freqList.Front().Value.(*freqNode)
+		leastRecently := lowestAccess.siblings.Front()
+		kv := leastRecently.Value.(*keyValueNode)
+		delete(lfu.lookup, kv.key)
+		lowestAccess.siblings.Remove(leastRecently)
+		if lowestAccess.siblings.Len() == 0 {
+			lfu.freqList.Remove(lfu.freqList.Front())
+		}
+	}
+	// add a new value into the cache.
+	if front := lfu.freqList.Front(); front == nil {
+		fqn := &freqNode{accessCount: 1, siblings: list.New()}
+		lfu.freqList.PushFront(fqn)
+		fqnElem := lfu.freqList.Front()
+		kvn := &keyValueNode{key: key, value: value, parent: fqn.siblings, freqElem: fqnElem}
+		e := fqn.siblings.PushBack(kvn)
+		lfu.lookup[key] = e
+	} else {
+		fqn := front.Value.(*freqNode)
+		if fqn.accessCount == 1 {
+			kvn := &keyValueNode{key: key, value: value, parent: fqn.siblings, freqElem: front}
+			e := fqn.siblings.PushBack(kvn)
+			lfu.lookup[key] = e
+		} else {
+			fqn := &freqNode{accessCount: 1, siblings: list.New()}
+			lfu.freqList.PushFront(fqn)
+			fqnElem := lfu.freqList.Front()
+			kvn := &keyValueNode{key: key, value: value, parent: fqn.siblings, freqElem: fqnElem}
+			e := fqn.siblings.PushBack(kvn)
+			lfu.lookup[key] = e
+		}
+	}
+}
+
+// Get gets the value at key. If no such key exists, return null.
+func (lfu *LFUCache) Get(key interface{}) interface{} {
+	// TODO: update freq counts.
+	if _, found := lfu.lookup[key]; !found {
+		return nil
+	}
+	keyValNode := lfu.lookup[key]
+	kvn := keyValNode.Value.(*keyValueNode)
+	kvn.parent.Remove(keyValNode)
+	fqnNext := kvn.freqElem.Next()
+	fqn := kvn.freqElem.Value.(*freqNode)
+	if fqnNext == nil || fqnNext.Value.(*freqNode).accessCount != fqn.accessCount+1 {
+		newFreq := &freqNode{accessCount: fqn.accessCount + 1, siblings: list.New()}
+		e := newFreq.siblings.PushBack(kvn)
+		lfu.lookup[key] = e
+		lfu.freqList.InsertAfter(newFreq, kvn.freqElem)
+	} else {
+		e := fqnNext.Value.(*freqNode).siblings.PushBack(kvn)
+		lfu.lookup[key] = e
+	}
+	if kvn.parent.Len() == 0 {
+		lfu.freqList.Remove(kvn.freqElem)
+	}
+	return kvn.value
+}
+
+// NewLFUCache returns a new instance of LFUCache.
+func NewLFUCache(n int) *LFUCache {
+	return &LFUCache{capacity: n,
+		lookup:   make(map[interface{}]*list.Element), // list.Element is *keyValueNode
+		freqList: list.New()}
+}


Test patch:
diff --git a/day67/problem_test.go b/day67/problem_test.go
new file mode 100644
index 0000000..98536fe
--- /dev/null
+++ b/day67/problem_test.go
@@ -0,0 +1,91 @@
+package day67
+
+import "testing"
+
+func TestLFUCacheOneEviction(t *testing.T) {
+	t.Parallel()
+	lfu := NewLFUCache(3)
+	lfu.Set("foo", "bar")
+	lfu.Set(1, 2)
+	lfu.Set("bar", "baz")
+	lfu.Get(1)
+	lfu.Get("bar")
+	lfu.Set(100, 1)
+	if result := lfu.Get("foo"); result != nil {
+		t.Errorf("'foo' should have been evicted at this point, got %v", result)
+	}
+	if result := lfu.Get(1); result == nil {
+		t.Errorf("1 should remain")
+	}
+	if result := lfu.Get("bar"); result == nil {
+		t.Errorf("'bar' should remain")
+	}
+	if result := lfu.Get(100); result == nil {
+		t.Errorf("100 should remain")
+	}
+	lfu.Set(100, "baz")
+	if result := lfu.Get(100); result.(string) != "baz" {
+		t.Errorf("I expected baz")
+	}
+}
+
+func TestLFUCacheDifferentAccessAmounts(t *testing.T) {
+	t.Parallel()
+	lfu := NewLFUCache(3)
+	lfu.Set("foo", "bar")
+	lfu.Set("foo", "bas")
+	lfu.Set("foo", "bat")
+	lfu.Set("foo", "bau")
+	lfu.Set(1, 2)
+	lfu.Set(1, 3)
+	lfu.Set("bar", "baz")
+	lfu.Set("willevictbar", "byebye")
+	lfu.Set("willevictbar2", "byebye")
+	if result := lfu.Get("foo"); result == nil {
+		t.Errorf("Should remain foo: %v", result)
+	}
+	if result := lfu.Get(1); result == nil {
+		t.Errorf("Shouldn't be nil, 1: %v", result)
+	}
+	if result := lfu.Get("bar"); result != nil {
+		t.Errorf("Should be nil")
+	}
+	if result := lfu.Get("willevictbar"); result != nil {
+		t.Errorf("Should be nil")
+	}
+	if result := lfu.Get("willevictbar2"); result == nil {
+		t.Errorf("Should remain")
+	}
+}
+
+func TestLFUCacheAccessGaps(t *testing.T) {
+	t.Parallel()
+	lfu := NewLFUCache(3)
+	lfu.Set("foo", "bar")
+	lfu.Set("foo", "bas")
+	lfu.Set("foo", "bat")
+	lfu.Set("foo", "bau")
+	lfu.Set("another", "one")
+	lfu.Set("last", "one")
+	if result := lfu.Get("foo"); result != "bau" {
+		t.Errorf("Expected 'bau' got %v", result)
+	}
+	if result := lfu.Get("another"); result != "one" {
+		t.Errorf("Expected 'one' got %v", result)
+	}
+	if result := lfu.Get("last"); result != "one" {
+		t.Errorf("Expected 'one' got %v", result)
+	}
+}
+
+func BenchmarkLFUCache(b *testing.B) {
+	lfu := NewLFUCache(3)
+	for i := 0; i < b.N; i++ {
+		lfu.Set("foo", "bar")
+		lfu.Set(1, 2)
+		lfu.Set("bar", "baz")
+		lfu.Get(1)
+		lfu.Get("bar")
+		lfu.Set(100, 1)
+	}
+}