Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 55
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Implement a URL shortener with the following methods:

`shorten(url)`, which shortens the url into a six-character alphanumeric string, such as zLg6wl.
`restore(short)`, which expands the shortened string into the original url. If no such shortened string exists, return null.
Hint: What if we enter the same URL twice?

Pull request description:
Day55
Resolves #121.

Patch:
diff --git a/README.md b/README.md
index b4fbcce..cb383ed 100644
--- a/README.md
+++ b/README.md
@@ -66,3 +66,4 @@ problems from
 * [Day 52](https://github.com/vaskoz/dailycodingproblem-go/issues/113)
 * [Day 53](https://github.com/vaskoz/dailycodingproblem-go/issues/114)
 * [Day 54](https://github.com/vaskoz/dailycodingproblem-go/issues/118)
+* [Day 55](https://github.com/vaskoz/dailycodingproblem-go/issues/121)
diff --git a/day55/problem.go b/day55/problem.go
new file mode 100644
index 0000000..77dbb8b
--- /dev/null
+++ b/day55/problem.go
@@ -0,0 +1,63 @@
+package day55
+
+const base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
+
+var (
+	b64pos = make(map[rune]int)
+	posb64 = make(map[int]rune)
+)
+
+func init() {
+	for i, r := range base64 {
+		b64pos[r] = i
+		posb64[i] = r
+	}
+}
+
+// URLShortener represents a URL shortener application.
+type URLShortener interface {
+	Shorten(url string) string
+	Restore(short string) string
+}
+
+type inMemoryURLShortener struct {
+	shorten map[string]string
+	restore map[string]string
+	next    uint64
+}
+
+// NewInMemoryURLShortener returns an in-memory URLShortener.
+func NewInMemoryURLShortener() URLShortener {
+	return &inMemoryURLShortener{
+		shorten: make(map[string]string),
+		restore: make(map[string]string),
+	}
+}
+
+func (imus *inMemoryURLShortener) Shorten(url string) string {
+	k := key(imus.next)
+	imus.shorten[url] = k
+	imus.restore[k] = url
+	imus.next++
+	return k
+}
+
+func (imus *inMemoryURLShortener) Restore(short string) string {
+	return imus.restore[short]
+}
+
+func key(index uint64) string {
+	result := make([]rune, 6)
+	i := 5
+	for index != 0 {
+		x := int(index % 64)
+		result[i] = posb64[x]
+		index /= 64
+		i--
+	}
+	for i >= 0 {
+		result[i] = posb64[0]
+		i--
+	}
+	return string(result)
+}


Test patch:
diff --git a/day55/problem_test.go b/day55/problem_test.go
new file mode 100644
index 0000000..72aad9c
--- /dev/null
+++ b/day55/problem_test.go
@@ -0,0 +1,35 @@
+package day55
+
+import "testing"
+
+var urls = []struct {
+	url, short string
+}{
+	{"http://google.com", "AAAAAA"},
+	{"http://yahoo.com", "AAAAAB"},
+	{"http://github.com", "AAAAAC"},
+}
+
+func TestInMemoryURLShortener(t *testing.T) {
+	t.Parallel()
+	us := NewInMemoryURLShortener()
+	for _, tc := range urls {
+		if short := us.Shorten(tc.url); short != tc.short {
+			t.Errorf("Expected %s got %s", tc.short, short)
+		}
+	}
+	for _, tc := range urls {
+		if url := us.Restore(tc.short); url != tc.url {
+			t.Errorf("Expected %s got %s", tc.url, url)
+		}
+	}
+}
+
+func BenchmarkInMemoryURLShortener(b *testing.B) {
+	us := NewInMemoryURLShortener()
+	for i := 0; i < b.N; i++ {
+		for _, tc := range urls {
+			us.Shorten(tc.url)
+		}
+	}
+}