Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 15
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.

Pull request description:
day 15 solution
Resolves #33 

Patch:
diff --git a/README.md b/README.md
index e75b4d3..90dc2b1 100644
--- a/README.md
+++ b/README.md
@@ -25,3 +25,4 @@ problems from
 * [Day 12 Count and Deepest](https://github.com/vaskoz/dailycodingproblem-go/issues/27)
 * [Day 13](https://github.com/vaskoz/dailycodingproblem-go/issues/29)
 * [Day 14](https://github.com/vaskoz/dailycodingproblem-go/issues/31)
+* [Day 15](https://github.com/vaskoz/dailycodingproblem-go/issues/33)
diff --git a/day15/problem.go b/day15/problem.go
new file mode 100644
index 0000000..c123451
--- /dev/null
+++ b/day15/problem.go
@@ -0,0 +1,25 @@
+package day15
+
+import (
+	"math/rand"
+	"time"
+)
+
+var randomizer *rand.Rand = rand.New(rand.NewSource(time.Now().UnixNano()))
+
+// UniformlyRandom reads from a stream of anything and
+// returns an element with uniform probabilty.
+// O(N) time and O(1) space
+func UniformlyRandom(stream <-chan interface{}) interface{} {
+	var result interface{}
+	var count int
+	for element := range stream {
+		if count == 0 {
+			result = element
+		} else if randomizer.Intn(count) == 0 {
+			result = element
+		}
+		count++
+	}
+	return result
+}


Test patch:
diff --git a/day15/problem_test.go b/day15/problem_test.go
new file mode 100644
index 0000000..a8af6eb
--- /dev/null
+++ b/day15/problem_test.go
@@ -0,0 +1,36 @@
+package day15
+
+import (
+	"math/rand"
+	"testing"
+)
+
+func TestUniformlyRandom(t *testing.T) {
+	t.Parallel()
+	randomizer = rand.New(rand.NewSource(99)) // use a fixed seed for testing.
+	expected := 58                            // because of the constant random seed
+	input := make(chan interface{})
+	go func() {
+		for i := 0; i < 100; i++ {
+			input <- i
+		}
+		close(input)
+	}()
+	if result := UniformlyRandom(input); result != 58 {
+		t.Errorf("Expected %v but got %v", expected, result)
+	}
+}
+
+func BenchmarkUniformlyRandom(b *testing.B) {
+	randomizer = rand.New(rand.NewSource(99)) // use a fixed seed for testing.
+	for i := 0; i < b.N; i++ {
+		input := make(chan interface{})
+		go func() {
+			for i := 0; i < 100; i++ {
+				input <- i
+			}
+			close(input)
+		}()
+		UniformlyRandom(input)
+	}
+}