Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 99
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, given `[100, 4, 200, 1, 3, 2]`, the longest consecutive element sequence is `[1, 2, 3, 4]`. Return its length: 4.

Your algorithm should run in O(n) complexity.

Pull request:
Day99
Resolves #205.

Patch:
diff --git a/README.md b/README.md
index 38172cc..c59f71a 100644
--- a/README.md
+++ b/README.md
@@ -105,3 +105,4 @@ problems from
 * [Day 94](https://github.com/vaskoz/dailycodingproblem-go/issues/197)
 * [Day 95](https://github.com/vaskoz/dailycodingproblem-go/issues/198)
 * [Day 96](https://github.com/vaskoz/dailycodingproblem-go/issues/200)
+* [Day 99](https://github.com/vaskoz/dailycodingproblem-go/issues/205)
diff --git a/day99/problem.go b/day99/problem.go
new file mode 100644
index 0000000..186e624
--- /dev/null
+++ b/day99/problem.go
@@ -0,0 +1,48 @@
+package day99
+
+import "sort"
+
+// LongestConsecutiveSequenceBrute given an unsorted array of integers,
+// returns the length of the longest consecutive elements sequence length.
+// Runtime O(N log N)
+func LongestConsecutiveSequenceBrute(nums []int) int {
+	sort.Ints(nums)
+	var max, count int
+	count = 1
+	for i := 1; i < len(nums); i++ {
+		if nums[i] == nums[i-1]+1 {
+			count++
+		} else if count > max {
+			max = count
+			count = 1
+		}
+	}
+	if count > max {
+		max = count
+	}
+	return max
+}
+
+// LongestConsecutiveSequenceLinear given an unsorted array of integers,
+// returns the length of the longest consecutive elements sequence length.
+// Runtime O(N)
+func LongestConsecutiveSequenceLinear(nums []int) int {
+	set := make(map[int]struct{})
+	var max int
+	for _, val := range nums {
+		set[val] = struct{}{}
+	}
+	for _, val := range nums {
+		if _, found := set[val-1]; !found {
+			found = true
+			var count int
+			for count = 1; found; count++ {
+				_, found = set[val+count]
+			}
+			if count-1 > max {
+				max = count - 1
+			}
+		}
+	}
+	return max
+}


Test patch:
diff --git a/day99/problem_test.go b/day99/problem_test.go
new file mode 100644
index 0000000..22a51b1
--- /dev/null
+++ b/day99/problem_test.go
@@ -0,0 +1,47 @@
+package day99
+
+import "testing"
+
+var testcases = []struct {
+	input  []int
+	length int
+}{
+	{[]int{100, 4, 200, 1, 3, 2}, 4},
+	{[]int{100, 4, 101, 103, 1, 102, 3, 104, 2, 105}, 6},
+}
+
+func TestLongestConsecutiveSequenceBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		data := append([]int{}, tc.input...)
+		if result := LongestConsecutiveSequenceBrute(data); result != tc.length {
+			t.Errorf("Expected %v got %v", tc.length, result)
+		}
+	}
+}
+
+func BenchmarkLongestConsecutiveSequenceBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			data := append([]int{}, tc.input...)
+			LongestConsecutiveSequenceBrute(data)
+		}
+	}
+}
+
+func TestLongestConsecutiveSequenceLinear(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := LongestConsecutiveSequenceLinear(tc.input); result != tc.length {
+			t.Errorf("Expected %v got %v", tc.length, result)
+		}
+	}
+}
+
+func BenchmarkLongestConsecutiveSequenceLinear(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LongestConsecutiveSequenceLinear(tc.input)
+		}
+	}
+}