Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 162
Good morning! Here's your coding interview problem for today.

This problem was asked by Square.

Given a list of words, return the shortest unique prefix of each word. For example, given the list:
```
* dog
* cat
* apple
* apricot
* fish
```
Return the list:
```
* d
* c
* app
* apr
* f
```

Pull request description:
Day162
Resolves #335.

Patch:
diff --git a/README.md b/README.md
index 9e5c104..cb4b438 100644
--- a/README.md
+++ b/README.md
@@ -170,4 +170,5 @@ problems from
 * [Day 157](https://github.com/vaskoz/dailycodingproblem-go/issues/327)
 * [Day 158](https://github.com/vaskoz/dailycodingproblem-go/issues/329)
 * [Day 159](https://github.com/vaskoz/dailycodingproblem-go/issues/331)
+* [Day 162](https://github.com/vaskoz/dailycodingproblem-go/issues/335)
 * [Day 163](https://github.com/vaskoz/dailycodingproblem-go/issues/336)
diff --git a/day162/problem.go b/day162/problem.go
new file mode 100644
index 0000000..329a56a
--- /dev/null
+++ b/day162/problem.go
@@ -0,0 +1,39 @@
+package day162
+
+import "strings"
+
+// Trie is a prefix search tree.
+type Trie struct {
+	freq map[rune]int
+	ptr  map[rune]*Trie
+}
+
+// ShortestUniquePrefix returns the shortest unique prefix for each word
+// amongst the words in the list.
+func ShortestUniquePrefix(words []string) []string {
+	root := &Trie{make(map[rune]int), make(map[rune]*Trie)}
+	for _, word := range words {
+		curr := root
+		for _, r := range word {
+			curr.freq[r]++
+			if curr.ptr[r] == nil {
+				curr.ptr[r] = &Trie{make(map[rune]int), make(map[rune]*Trie)}
+			}
+			curr = curr.ptr[r]
+		}
+	}
+	results := make([]string, 0, len(words))
+	for _, word := range words {
+		var sb strings.Builder
+		curr := root
+		for _, r := range word {
+			sb.WriteRune(r)
+			if curr.freq[r] == 1 {
+				results = append(results, sb.String())
+				break
+			}
+			curr = curr.ptr[r]
+		}
+	}
+	return results
+}


Test patch:
diff --git a/day162/problem_test.go b/day162/problem_test.go
new file mode 100644
index 0000000..bf97b8e
--- /dev/null
+++ b/day162/problem_test.go
@@ -0,0 +1,29 @@
+package day162
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	words, prefixes []string
+}{
+	{[]string{"dog", "cat", "apple", "apricot", "fish"}, []string{"d", "c", "app", "apr", "f"}},
+}
+
+func TestShortestUniquePrefix(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := ShortestUniquePrefix(tc.words); !reflect.DeepEqual(result, tc.prefixes) {
+			t.Errorf("Expected %v got %v", tc.prefixes, result)
+		}
+	}
+}
+
+func BenchmarkShortestUniquePrefix(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ShortestUniquePrefix(tc.words)
+		}
+	}
+}