Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 155
Good morning! Here's your coding interview problem for today.

This problem was asked by MongoDB.

Given a list of elements, find the majority element, which appears more than half the time `(> floor(len(lst) / 2.0))`.

You can assume that such element exists.

For example, given `[1, 2, 1, 1, 3, 4, 0]`, return `1`.

Pull request:
Day155
Resolves #322.

Patch:
diff --git a/README.md b/README.md
index 6c43ed4..23b760d 100644
--- a/README.md
+++ b/README.md
@@ -164,3 +164,4 @@ problems from
 * [Day 151](https://github.com/vaskoz/dailycodingproblem-go/issues/313)
 * [Day 153](https://github.com/vaskoz/dailycodingproblem-go/issues/316)
 * [Day 154](https://github.com/vaskoz/dailycodingproblem-go/issues/320)
+* [Day 155](https://github.com/vaskoz/dailycodingproblem-go/issues/322)
diff --git a/day155/problem.go b/day155/problem.go
new file mode 100644
index 0000000..557f363
--- /dev/null
+++ b/day155/problem.go
@@ -0,0 +1,75 @@
+package day155
+
+import (
+	"errors"
+	"sort"
+)
+
+var errNoMajority = errors.New("no majority exists")
+
+// ErrNoMajority returns the same error returned when no majority exists.
+func ErrNoMajority() error {
+	return errNoMajority
+}
+
+// MajorityElementMap returns the number that occurs over half the time.
+// Runs in O(N) time and O(unique values) in space.
+func MajorityElementMap(nums []int) (int, error) {
+	counts := make(map[int]int)
+	for _, v := range nums {
+		counts[v]++
+	}
+	threshold := len(nums) / 2
+	for k, v := range counts {
+		if v >= threshold {
+			return k, nil
+		}
+	}
+	return 0, errNoMajority
+}
+
+// MajorityElementSort returns the number that occurs over half the time.
+// Runs in O(N log N) time and O(1) in space.
+func MajorityElementSort(nums []int) (int, error) {
+	if len(nums) < 1 {
+		return 0, errNoMajority
+	}
+	nums = append([]int{}, nums...) // don't mutate the input.
+	sort.Ints(nums)
+	var maxVal, maxCount int
+	val := nums[0]
+	count := 1
+	for i := 1; i < len(nums); i++ {
+		if nums[i] == val {
+			count++
+		} else {
+			if count > maxCount {
+				maxCount = count
+				maxVal = val
+			}
+			val = nums[i]
+			count = 1
+		}
+	}
+	if count > maxCount {
+		return val, nil
+	}
+	return maxVal, nil
+}
+
+// MajorityBoyerMoore runs in O(N) time and O(1) space.
+// Limitation: only works if there is definitely a majority value.
+func MajorityBoyerMoore(nums []int) (int, error) {
+	var m, i int
+	for _, x := range nums {
+		if i == 0 {
+			m = x
+			i = 1
+		} else if m == x {
+			i++
+		} else {
+			i--
+		}
+	}
+	return m, nil
+}


Test patch:
diff --git a/day155/problem_test.go b/day155/problem_test.go
new file mode 100644
index 0000000..87ca49c
--- /dev/null
+++ b/day155/problem_test.go
@@ -0,0 +1,68 @@
+package day155
+
+import "testing"
+
+var testcases = []struct {
+	nums     []int
+	majority int
+	err      error
+}{
+	{[]int{1, 2, 1, 1, 3, 1, 4, 0}, 1, nil},
+	{[]int{}, 0, ErrNoMajority()},
+	{[]int{4, 1, 2, 4, 1, 4, 1, 3, 4, 0, 4}, 4, nil},
+	{[]int{1, 2, 4, 1, 4, 1, 4, 3, 4, 0, 4}, 4, nil},
+}
+
+func TestMajorityElementMap(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := MajorityElementMap(tc.nums); err != tc.err || result != tc.majority {
+			t.Errorf("Expected (%v,%v) got (%v,%v)", tc.majority, tc.err, result, err)
+		}
+	}
+}
+
+func TestMajorityElementSort(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := MajorityElementSort(tc.nums); err != tc.err || result != tc.majority {
+			t.Errorf("Expected (%v,%v) got (%v,%v)", tc.majority, tc.err, result, err)
+		}
+	}
+}
+
+func TestMajorityBoyerMoore(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if tc.err != nil {
+			continue
+		}
+		if result, err := MajorityBoyerMoore(tc.nums); err != tc.err || result != tc.majority {
+			t.Errorf("Expected (%v,%v) got (%v,%v)", tc.majority, tc.err, result, err)
+		}
+	}
+}
+
+func BenchmarkMajorityElementMap(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MajorityElementMap(tc.nums)
+		}
+	}
+}
+
+func BenchmarkMajorityElementSort(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MajorityElementSort(tc.nums)
+		}
+	}
+}
+
+func BenchmarkMajorityBoyerMoore(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MajorityBoyerMoore(tc.nums)
+		}
+	}
+}