Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 309
Good morning! Here's your coding interview problem for today.

This problem was asked by Walmart Labs.

There are M people sitting in a row of N seats, where M < N. Your task is to redistribute people such that there are no gaps between any of them, while keeping overall movement to a minimum.

For example, suppose you are faced with an input of `[0, 1, 1, 0, 1, 0, 0, 0, 1]`, where `0` represents an empty seat and `1` represents a person. In this case, one solution would be to place the person on the right in the fourth seat. We can consider the cost of a solution to be the sum of the absolute distance each person must move, so that the cost here would be five.

Given an input such as the one above, return the lowest possible cost of moving people to remove all gaps.

Pull request:
Day309
Resolves #631.

Patch:
diff --git a/README.md b/README.md
index 1b45316..c6d017c 100644
--- a/README.md
+++ b/README.md
@@ -316,3 +316,4 @@ problems from
 * [Day 305](https://github.com/vaskoz/dailycodingproblem-go/issues/622)
 * [Day 306](https://github.com/vaskoz/dailycodingproblem-go/issues/626)
 * [Day 307](https://github.com/vaskoz/dailycodingproblem-go/issues/628)
+* [Day 309](https://github.com/vaskoz/dailycodingproblem-go/issues/631)
diff --git a/day309/problem.go b/day309/problem.go
new file mode 100644
index 0000000..da972a2
--- /dev/null
+++ b/day309/problem.go
@@ -0,0 +1,104 @@
+package day309
+
+// MinRedistributeNoGapsFaster returns the minimum cost
+// to move all together.
+// Runs in O(N) time and O(1) space.
+func MinRedistributeNoGapsFaster(seating []int) int {
+	var min int
+	totalPeople := 0
+	for i := range seating {
+		if seating[i] == 1 {
+			totalPeople++
+		}
+	}
+	if totalPeople < 2 {
+		return 0
+	}
+	middle := (totalPeople / 2) + (totalPeople % 2)
+	index := 0
+	for i := range seating {
+		if seating[i] == 1 {
+			middle--
+		}
+		if middle == 0 {
+			index = i
+			break
+		}
+	}
+	// left
+	leftZero := 0
+	leftZeroFound := false
+	for j := index - 1; j >= 0; j-- {
+		if !leftZeroFound && seating[j] == 0 {
+			leftZero = j
+			leftZeroFound = true
+		} else if seating[j] == 1 && j < leftZero {
+			min += abs(j - leftZero)
+			leftZero--
+		}
+	}
+	// right
+	rightZero := 0
+	rightZeroFound := false
+	for j := index + 1; j < len(seating); j++ {
+		if !rightZeroFound && seating[j] == 0 {
+			rightZero = j
+			rightZeroFound = true
+		} else if seating[j] == 1 && j > rightZero {
+			min += abs(j - rightZero)
+			rightZero++
+		}
+	}
+	return min
+}
+
+// MinRedistributeNoGapsBrute returns the minimum cost
+// to move all together.
+// Runs in O(N^2) time and O(1) space.
+func MinRedistributeNoGapsBrute(seating []int) int {
+	const MaxInt = int(^uint(0) >> 1)
+	min := MaxInt
+	for i := range seating {
+		var curr int
+		if seating[i] == 1 {
+			// left
+			leftZero := 0
+			leftZeroFound := false
+			for j := i - 1; j >= 0; j-- {
+				if !leftZeroFound && seating[j] == 0 {
+					leftZero = j
+					leftZeroFound = true
+				} else if seating[j] == 1 && j < leftZero {
+					curr += abs(j - leftZero)
+					leftZero--
+				}
+			}
+			// right
+			rightZero := 0
+			rightZeroFound := false
+			for j := i + 1; j < len(seating); j++ {
+				if !rightZeroFound && seating[j] == 0 {
+					rightZero = j
+					rightZeroFound = true
+				} else if seating[j] == 1 && j > rightZero {
+					curr += abs(j - rightZero)
+					rightZero++
+				}
+			}
+			if curr < min {
+				min = curr
+			}
+		}
+	}
+	if min == MaxInt {
+		return 0
+	}
+	return min
+}
+
+func abs(a int) int {
+	if a < 0 {
+		return -a
+	}
+	return a
+}


Test patch:
diff --git a/day309/problem_test.go b/day309/problem_test.go
new file mode 100644
index 0000000..dc5f022
--- /dev/null
+++ b/day309/problem_test.go
@@ -0,0 +1,48 @@
+package day309
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	seating  []int
+	minMoves int
+}{
+	{[]int{0, 1, 1, 0, 1, 0, 0, 0, 1}, 5},
+	{[]int{0, 0, 1, 0, 0, 0, 0, 0, 0}, 0},
+	{[]int{0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
+	{[]int{1, 0, 1, 0, 1, 0, 1, 0, 1}, 6},
+}
+
+func TestMinRedistributeNoGapsFaster(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if minMoves := MinRedistributeNoGapsFaster(tc.seating); minMoves != tc.minMoves {
+			t.Errorf("Expected %v, got %v", tc.minMoves, minMoves)
+		}
+	}
+}
+
+func BenchmarkMinRedistributeNoGapsFaster(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinRedistributeNoGapsFaster(tc.seating)
+		}
+	}
+}
+
+func TestMinRedistributeNoGapsBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if minMoves := MinRedistributeNoGapsBrute(tc.seating); minMoves != tc.minMoves {
+			t.Errorf("Expected %v, got %v", tc.minMoves, minMoves)
+		}
+	}
+}
+
+func BenchmarkMinRedistributeNoGapsBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinRedistributeNoGapsBrute(tc.seating)
+		}
+	}
+}