Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 101
Good morning! Here's your coding interview problem for today.

This problem was asked by Alibaba.

Given an even number (greater than 2), return two prime numbers whose sum will be equal to the given number.

A solution will always exist. See Goldbach’s conjecture.

Example:
```
Input: 4
Output: 2 + 2 = 4
```
If there are more than one solution possible, return the lexicographically smaller solution.

If [a, b] is one solution with a <= b, and [c, d] is another solution with c <= d, then
```
[a, b] < [c, d]
If a < c OR a==c AND b < d.
```

Pull request description:
Day101
Resolves #212.

Patch:
diff --git a/README.md b/README.md
index e09bea7..231ca71 100644
--- a/README.md
+++ b/README.md
@@ -110,3 +110,4 @@ problems from
 * [Day 98](https://github.com/vaskoz/dailycodingproblem-go/issues/204)
 * [Day 99](https://github.com/vaskoz/dailycodingproblem-go/issues/205)
 * [Day 100](https://github.com/vaskoz/dailycodingproblem-go/issues/209)
+* [Day 101](https://github.com/vaskoz/dailycodingproblem-go/issues/212)
diff --git a/day101/problem.go b/day101/problem.go
new file mode 100644
index 0000000..acdb1e0
--- /dev/null
+++ b/day101/problem.go
@@ -0,0 +1,47 @@
+package day101
+
+import (
+	"math"
+)
+
+// Sieve of prime numbers up to n.
+// Runs in O(N log log N)
+func Sieve(n int) []int {
+	data := make([]bool, n+1)
+	for i := 2; i < int(math.Sqrt(float64(n)))+1; i++ {
+		if !data[i] {
+			for j := i * i; j <= n; j += i {
+				data[j] = true
+			}
+		}
+	}
+	var results []int
+	for i := 2; i <= n; i++ {
+		if !data[i] {
+			results = append(results, i)
+		}
+	}
+	return results
+}
+
+// GoldbachsConjecture returns two prime numbers whose sum
+// is equal to the given number.
+// If even param is less than 4 or an odd number, nil is returned.
+func GoldbachsConjecture(even int) []int {
+	if even < 4 || even%2 != 0 {
+		return nil
+	}
+	primes := Sieve(even)
+	set := make(map[int]struct{}, len(primes))
+	for _, prime := range primes {
+		set[prime] = struct{}{}
+	}
+	result := make([]int, 2)
+	for _, prime := range primes {
+		if _, found := set[even-prime]; found {
+			result[0], result[1] = prime, even-prime
+			break
+		}
+	}
+	return result
+}


Test patch:
diff --git a/day101/problem_test.go b/day101/problem_test.go
new file mode 100644
index 0000000..53d7a57
--- /dev/null
+++ b/day101/problem_test.go
@@ -0,0 +1,62 @@
+package day101
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	even     int
+	expected []int
+}{
+	{4, []int{2, 2}},
+	{6, []int{3, 3}},
+	{8, []int{3, 5}},
+	{10, []int{3, 7}},
+	{10, []int{3, 7}},
+	{18, []int{5, 13}},
+}
+
+func TestSieve(t *testing.T) {
+	t.Parallel()
+	expected := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
+		41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
+
+	if result := Sieve(100); !reflect.DeepEqual(expected, result) {
+		t.Errorf("Expected %v got %v", expected, result)
+	}
+}
+
+func BenchmarkSieve(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Sieve(100)
+	}
+}
+
+func TestGoldbachsConjecture(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := GoldbachsConjecture(tc.even); !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkGoldbachsConjecture(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			GoldbachsConjecture(tc.even)
+		}
+	}
+}
+
+func TestGoldbachsConjectureBadInput(t *testing.T) {
+	t.Parallel()
+	if result := GoldbachsConjecture(3); result != nil {
+		t.Errorf("Parameters less than 4 should result in nil return")
+	}
+	if result := GoldbachsConjecture(9); result != nil {
+		t.Errorf("Odd parameters should result in nil return")
+	}
+
+}