Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 232
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Implement a PrefixMapSum class with the following methods:

`insert(key: str, value: int)`: Set a given key's value in the map. If the key already exists, overwrite the value.
`sum(prefix: str)`: Return the sum of all values of keys that begin with a given prefix.
For example, you should be able to run the following code:
```
mapsum.insert("columnar", 3)
assert mapsum.sum("col") == 3

mapsum.insert("column", 2)
assert mapsum.sum("col") == 5
```

Pull request description:
Day232
Resolves #477.

Patch:
diff --git a/README.md b/README.md
index ac0ab80..05a4d52 100644
--- a/README.md
+++ b/README.md
@@ -240,3 +240,4 @@ problems from
 * [Day 228](https://github.com/vaskoz/dailycodingproblem-go/issues/470)
 * [Day 230](https://github.com/vaskoz/dailycodingproblem-go/issues/473)
 * [Day 231](https://github.com/vaskoz/dailycodingproblem-go/issues/475)
+* [Day 232](https://github.com/vaskoz/dailycodingproblem-go/issues/477)
diff --git a/day232/problem.go b/day232/problem.go
new file mode 100644
index 0000000..4f26d42
--- /dev/null
+++ b/day232/problem.go
@@ -0,0 +1,46 @@
+package day232
+
+// PrefixMapSum represents a prefix tree collection of sums.
+type PrefixMapSum interface {
+	Insert(key string, value int)
+	Sum(prefix string) int
+}
+
+type prefixMapSumTrie struct {
+	sum  int
+	next map[rune]*prefixMapSumTrie
+}
+
+// NewPrefixMapSum returns a new instance.
+func NewPrefixMapSum() PrefixMapSum {
+	return &prefixMapSumTrie{}
+}
+
+func (pms *prefixMapSumTrie) Insert(key string, value int) {
+	curr := pms
+	for _, r := range key {
+		if curr.next == nil {
+			curr.next = make(map[rune]*prefixMapSumTrie)
+		}
+		if _, found := curr.next[r]; !found {
+			curr.next[r] = &prefixMapSumTrie{}
+		}
+		curr.next[r].sum += value
+		curr = curr.next[r]
+	}
+}
+
+func (pms *prefixMapSumTrie) Sum(prefix string) int {
+	curr := pms
+	for _, r := range prefix {
+		if curr.next == nil || curr.next[r] == nil {
+			curr = nil
+			break
+		}
+		curr = curr.next[r]
+	}
+	if curr != nil {
+		return curr.sum
+	}
+	return 0
+}


Test patch:
diff --git a/day232/problem_test.go b/day232/problem_test.go
new file mode 100644
index 0000000..17f4ff6
--- /dev/null
+++ b/day232/problem_test.go
@@ -0,0 +1,33 @@
+package day232
+
+import "testing"
+
+func TestPrefixMapSum(t *testing.T) {
+	t.Parallel()
+	pms := NewPrefixMapSum()
+	pms.Insert("columnar", 3)
+	if sum := pms.Sum("col"); sum != 3 {
+		t.Errorf("Sum should be 3 here got %d", sum)
+	}
+	pms.Insert("column", 2)
+	if sum := pms.Sum("col"); sum != 5 {
+		t.Errorf("Sum should be 5 here got %d", sum)
+	}
+	if sum := pms.Sum("columns"); sum != 0 {
+		t.Errorf("Sum should be 0 here got %d", sum)
+	}
+	if sum := pms.Sum("hi there"); sum != 0 {
+		t.Errorf("Sum should be 0 here got %d", sum)
+	}
+}
+
+func BenchmarkPrefixMapSum(b *testing.B) {
+	pms := NewPrefixMapSum()
+	for i := 0; i < b.N; i++ {
+		pms.Insert("columnar", 3)
+		pms.Insert("column", 2)
+		pms.Sum("col")
+		pms.Sum("columns")
+		pms.Sum("hi there")
+	}
+}