Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 66
Good morning! Here's your coding interview problem for today.

This problem was asked by Square.

Assume you have access to a function toss_biased() which returns 0 or 1 with a probability that's not 50-50 (but also not 0-100 or 100-0). You do not know the bias of the coin.

Write a function to simulate an unbiased coin toss.

Pull request description:
Day66
Resolves #141.

Patch:
diff --git a/README.md b/README.md
index 505e64d..8e30726 100644
--- a/README.md
+++ b/README.md
@@ -75,3 +75,4 @@ problems from
 * [Day 62](https://github.com/vaskoz/dailycodingproblem-go/issues/134)
 * [Day 63](https://github.com/vaskoz/dailycodingproblem-go/issues/136)
 * [Day 65](https://github.com/vaskoz/dailycodingproblem-go/issues/139)
+* [Day 66](https://github.com/vaskoz/dailycodingproblem-go/issues/141)
diff --git a/day66/problem.go b/day66/problem.go
new file mode 100644
index 0000000..9ba6278
--- /dev/null
+++ b/day66/problem.go
@@ -0,0 +1,49 @@
+package day66
+
+import (
+	"math/rand"
+	"time"
+)
+
+// BiasedCoin represents a biased coin. Not 50-50.
+type BiasedCoin struct {
+	zeroBias int
+	r        *rand.Rand
+}
+
+// Toss throws the coin and returns 0 or 1
+func (bc *BiasedCoin) Toss() int {
+	if val := bc.r.Intn(100); val < bc.zeroBias {
+		return 0
+	}
+	return 1
+}
+
+// NewBiasedCoin returns a biased coin for flipping.
+// zeroBias represents the amount of bias towards a zero value.
+// The higher the value of zeroBias the more you will see zeros.
+// a zeroBias of 50 will be a fair coin.
+func NewBiasedCoin(zeroBias int) *BiasedCoin {
+	return &BiasedCoin{zeroBias: zeroBias, r: rand.New(rand.NewSource(time.Now().UnixNano()))}
+}
+
+// FairTosser represents a fair 50-50 coin tosser even if given an unfair coin.
+type FairTosser struct {
+	bc *BiasedCoin
+}
+
+// Toss throws the coin and returns 0 or 1 and should be a 50-50 chance.
+func (ft *FairTosser) Toss() int {
+	firstToss := ft.bc.Toss()
+	secondToss := ft.bc.Toss()
+	for firstToss == secondToss {
+		firstToss = ft.bc.Toss()
+		secondToss = ft.bc.Toss()
+	}
+	return firstToss
+}
+
+// NewFairTosser makes a biased coin fair.
+func NewFairTosser(bc *BiasedCoin) *FairTosser {
+	return &FairTosser{bc: bc}
+}


Test patch:
diff --git a/day66/problem_test.go b/day66/problem_test.go
new file mode 100644
index 0000000..0aa7b2a
--- /dev/null
+++ b/day66/problem_test.go
@@ -0,0 +1,34 @@
+package day66
+
+import "testing"
+
+func TestFairTosser(t *testing.T) {
+	t.Parallel()
+	bc := NewBiasedCoin(99)
+	biasedResults := make([]int, 2)
+	for i := 0; i < 100000; i++ {
+		biasedResults[bc.Toss()]++
+	}
+	if biasedResults[1] == 0 {
+		t.Errorf("Should have received 1 at least once")
+	}
+	if ratio := biasedResults[0] / biasedResults[1]; ratio < 90 {
+		t.Errorf("Expected the ratio of 0's to 1's to be near 99, but got %v", ratio)
+	}
+	ft := NewFairTosser(bc)
+	fairResults := make([]int, 2)
+	for i := 0; i < 100000; i++ {
+		fairResults[ft.Toss()]++
+	}
+	if ratio := float64(fairResults[0]) / float64(fairResults[1]); ratio < 0.9 || ratio > 1.1 {
+		t.Errorf("Expected the ratio of 0's to 1's to be near 1.0, but got %v", ratio)
+	}
+}
+
+func BenchmarkFairTosser(b *testing.B) {
+	bc := NewBiasedCoin(99)
+	ft := NewFairTosser(bc)
+	for i := 0; i < b.N; i++ {
+		ft.Toss()
+	}
+}