Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 143
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given a pivot `x`, and a list `lst`, partition the list into three parts.

The first part contains all elements in lst that are less than x
The second part contains all elements in lst that are equal to x
The third part contains all elements in lst that are larger than x
Ordering within a part can be arbitrary.

For example, given `x = 10` and `lst = [9, 12, 3, 5, 14, 10, 10]`, one partition may be `[9, 3, 5, 10, 10, 12, 14]`.

Pull request:
Day143
Resolves #299.

Patch:
diff --git a/README.md b/README.md
index 4ee88d7..aeb9206 100644
--- a/README.md
+++ b/README.md
@@ -153,3 +153,4 @@ problems from
 * [Day 140](https://github.com/vaskoz/dailycodingproblem-go/issues/292)
 * [Day 141](https://github.com/vaskoz/dailycodingproblem-go/issues/294)
 * [Day 142](https://github.com/vaskoz/dailycodingproblem-go/issues/297)
+* [Day 143](https://github.com/vaskoz/dailycodingproblem-go/issues/299)
diff --git a/day143/problem.go b/day143/problem.go
new file mode 100644
index 0000000..7749272
--- /dev/null
+++ b/day143/problem.go
@@ -0,0 +1,30 @@
+package day143
+
+import "sort"
+
+// DNFPartitionBrute has values smaller than pivot first, followed by pivot values,
+// followed by values larger than pivot last.
+// Runs in O(N log N) because it just sorts.
+func DNFPartitionBrute(lst []int, pivot int) {
+	sort.Ints(lst)
+}
+
+// DNFPartition has values smaller than pivot first, followed by pivot values,
+// followed by values larger than pivot last.
+// Runs in O(N) because it just sorts.
+func DNFPartition(lst []int, pivot int) {
+	var i, j int
+	n := len(lst) - 1
+	for j <= n {
+		if lst[j] < pivot {
+			lst[i], lst[j] = lst[j], lst[i]
+			i++
+			j++
+		} else if lst[j] > pivot {
+			lst[j], lst[n] = lst[n], lst[j]
+			n--
+		} else {
+			j++
+		}
+	}
+}


Test patch:
diff --git a/day143/problem_test.go b/day143/problem_test.go
new file mode 100644
index 0000000..97879cb
--- /dev/null
+++ b/day143/problem_test.go
@@ -0,0 +1,66 @@
+package day143
+
+import "testing"
+
+var testcases = []struct {
+	lst   []int
+	pivot int
+}{
+	{[]int{9, 12, 3, 5, 14, 10, 10}, 10},
+	{[]int{9, 12, 3, 5, 14, 10, 10}, 20},
+	{[]int{9, 12, 3, 5, 14, 10, 10}, 1},
+}
+
+func checkInvariant(lst []int, pivot int) bool {
+	var i int
+	for i < len(lst) && lst[i] < pivot {
+		i++
+	}
+	for i < len(lst) && lst[i] == pivot {
+		i++
+	}
+	for i < len(lst) && lst[i] > pivot {
+		i++
+	}
+	return i == len(lst)
+}
+
+func TestDNFPartitionBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		copied := append([]int{}, tc.lst...)
+		DNFPartitionBrute(copied, tc.pivot)
+		if !checkInvariant(copied, tc.pivot) {
+			t.Errorf("Didn't partition correctly. pivot=%d. Given %v got %v", tc.pivot, tc.lst, copied)
+		}
+	}
+}
+
+func BenchmarkDNFPartitionBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			copied := append([]int{}, tc.lst...)
+			DNFPartitionBrute(copied, tc.pivot)
+		}
+	}
+}
+
+func TestDNFPartition(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		copied := append([]int{}, tc.lst...)
+		DNFPartition(copied, tc.pivot)
+		if !checkInvariant(copied, tc.pivot) {
+			t.Errorf("Didn't partition correctly. pivot=%d. Given %v got %v", tc.pivot, tc.lst, copied)
+		}
+	}
+}
+
+func BenchmarkDNFPartition(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			copied := append([]int{}, tc.lst...)
+			DNFPartition(copied, tc.pivot)
+		}
+	}
+}