Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 368
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Implement a key value store, where keys and values are integers, with the following methods:

* `update(key, vl)`: updates the value at `key` to `val`, or sets it if doesn't exist
* `get(key)`: returns the value with key, or `None` if no such value exists
* `max_key(val)`: returns the largest key with value `val`, or `None` if no key with that value exists

For example, if we ran the following calls:
```
kv.update(1, 1)
kv.update(2, 1)
```
And then called `kv.max_key(1)`, it should return `2`, since it's the largest key with value `1`.

Pull request:
Day368
Resolves #743

Patch:
diff --git a/README.md b/README.md
index 6bd4abf..a695f84 100644
--- a/README.md
+++ b/README.md
@@ -363,4 +363,5 @@ problems from
 * [Day 365](https://github.com/vaskoz/dailycodingproblem-go/issues/720)
 * I thought it was done at day 365. Apparently not.
 * [Day 367](https://github.com/vaskoz/dailycodingproblem-go/issues/740)
+* [Day 368](https://github.com/vaskoz/dailycodingproblem-go/issues/743)
 
diff --git a/day368/problem.go b/day368/problem.go
new file mode 100644
index 0000000..6131261
--- /dev/null
+++ b/day368/problem.go
@@ -0,0 +1,69 @@
+package day368
+
+import "errors"
+
+// KeyValueStore is a key value store for the problem.
+type KeyValueStore interface {
+	// Update updates the value at key to val, or sets it if doesn't exist
+	Update(key, val int)
+	// Get returns the value with key or an error if no such value exists
+	Get(key int) (int, error)
+	// MaxKey returns the largest key with value val or error
+	// if no key with that value exists
+	MaxKey(val int) (int, error)
+}
+
+var errNotFound = errors.New("not found")
+
+type keyValueStore struct {
+	keyToVals map[int]int
+	valToKeys map[int]map[int]struct{}
+}
+
+func (kvs *keyValueStore) Update(k, v int) {
+	if prevV, found := kvs.keyToVals[k]; found {
+		delete(kvs.valToKeys[prevV], k) // delete previous key
+
+		if len(kvs.valToKeys[prevV]) == 0 { // delete previous value
+			delete(kvs.valToKeys, prevV)
+		}
+	}
+
+	kvs.keyToVals[k] = v
+	if m, exists := kvs.valToKeys[v]; exists {
+		m[k] = struct{}{}
+	} else {
+		kvs.valToKeys[v] = make(map[int]struct{})
+		kvs.valToKeys[v][k] = struct{}{}
+	}
+}
+
+func (kvs *keyValueStore) Get(k int) (int, error) {
+	if v, found := kvs.keyToVals[k]; found {
+		return v, nil
+	}
+
+	return 0, errNotFound
+}
+
+func (kvs *keyValueStore) MaxKey(v int) (int, error) {
+	if len(kvs.valToKeys[v]) == 0 {
+		return 0, errNotFound
+	}
+
+	maxKey := -int(^uint(0)>>1) - 1 // most negative int
+	for k := range kvs.valToKeys[v] {
+		if k > maxKey {
+			maxKey = k
+		}
+	}
+
+	return maxKey, nil
+}
+
+func NewKeyValueStore() KeyValueStore {
+	return &keyValueStore{
+		keyToVals: make(map[int]int),
+		valToKeys: make(map[int]map[int]struct{}),
+	}
+}


Test patch:
diff --git a/day368/problem_test.go b/day368/problem_test.go
new file mode 100644
index 0000000..41013c3
--- /dev/null
+++ b/day368/problem_test.go
@@ -0,0 +1,54 @@
+package day368
+
+import "testing"
+
+func TestKeyValueStore(t *testing.T) {
+	t.Parallel()
+
+	kv := NewKeyValueStore()
+
+	if _, err := kv.Get(1); err == nil {
+		t.Errorf("Expected an error getting 1 on empty KV store")
+	}
+
+	kv.Update(1, 1)
+	kv.Update(2, 1)
+
+	if v, err := kv.Get(1); v != 1 || err != nil {
+		t.Errorf("Expected (%v,%v), got (%v,%v)", 1, nil, v, err)
+	}
+
+	if v, err := kv.Get(2); v != 1 || err != nil {
+		t.Errorf("Expected (%v,%v), got (%v,%v)", 2, nil, v, err)
+	}
+
+	kv.Update(1, 2)
+	kv.Update(2, 2)
+
+	if v, err := kv.Get(1); v != 2 || err != nil {
+		t.Errorf("Expected (%v,%v), got (%v,%v)", 2, nil, v, err)
+	}
+
+	if v, err := kv.MaxKey(2); v != 2 || err != nil {
+		t.Errorf("Expected (%v,%v), got (%v,%v)", 2, nil, v, err)
+	}
+
+	if _, err := kv.MaxKey(1); err == nil {
+		t.Errorf("Expected an error getting MaxKey 1")
+	}
+}
+
+func BenchmarkKeyValueStore(b *testing.B) {
+	kv := NewKeyValueStore()
+
+	for i := 0; i < b.N; i++ {
+		kv.Update(1, 1)
+		kv.Update(2, 1)
+		kv.Get(1)    // nolint
+		kv.MaxKey(1) // nolint
+		kv.MaxKey(2) // nolint
+		kv.Update(1, 2)
+		kv.Update(2, 2)
+		kv.MaxKey(2) // nolint
+	}
+}