Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 126
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Write a function that rotates a list by k elements. For example, `[1, 2, 3, 4, 5, 6]` rotated by two becomes `[3, 4, 5, 6, 1, 2]`. Try solving this without creating a copy of the list. How many swap or move operations do you need?



Pull request:
Day126
Resolves #258.

Patch:
diff --git a/README.md b/README.md
index 7e9d9c8..d0dc865 100644
--- a/README.md
+++ b/README.md
@@ -131,5 +131,6 @@ problems from
 * [Day 123](https://github.com/vaskoz/dailycodingproblem-go/issues/253)
 * [Day 124](https://github.com/vaskoz/dailycodingproblem-go/issues/255)
 * [Day 125](https://github.com/vaskoz/dailycodingproblem-go/issues/257)
+* [Day 126](https://github.com/vaskoz/dailycodingproblem-go/issues/258)
 * [Day 127](https://github.com/vaskoz/dailycodingproblem-go/issues/259)
 * [Day 129](https://github.com/vaskoz/dailycodingproblem-go/issues/263)
diff --git a/day126/problem.go b/day126/problem.go
new file mode 100644
index 0000000..beeeebf
--- /dev/null
+++ b/day126/problem.go
@@ -0,0 +1,47 @@
+package day126
+
+// RotateNew returns a new slice that has been rotated by k.
+func RotateNew(nums []int, k int) []int {
+	result := make([]int, len(nums))
+	for i := k; i < k+len(nums); i++ {
+		result[i-k] = nums[i%len(nums)]
+	}
+	return result
+}
+
+// RotateKSwaps rotates the values by k in-place using swaps.
+// It uses O(K*N) time.
+func RotateKSwaps(nums []int, k int) {
+	for i := 0; i < k; i++ {
+		for j := 1; j < len(nums); j++ {
+			nums[j-1], nums[j] = nums[j], nums[j-1]
+		}
+	}
+}
+
+// RotateJuggleSwaps rotates using swaps but faster.
+func RotateJuggleSwaps(nums []int, k int) {
+	for i := 0; i < gcd(len(nums), k); i++ {
+		tmp := nums[i]
+		j := i
+		for {
+			jj := j + k
+			if jj >= len(nums) {
+				jj = jj % len(nums)
+			}
+			if jj == i {
+				break
+			}
+			nums[j] = nums[jj]
+			j = jj
+		}
+		nums[j] = tmp
+	}
+}
+
+func gcd(a, b int) int {
+	if b == 0 {
+		return a
+	}
+	return gcd(b, a%b)
+}


Test patch:
diff --git a/day126/problem_test.go b/day126/problem_test.go
new file mode 100644
index 0000000..2f17af6
--- /dev/null
+++ b/day126/problem_test.go
@@ -0,0 +1,76 @@
+package day126
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	original, rotated []int
+	k                 int
+}{
+	{[]int{1, 2, 3, 4, 5, 6}, []int{3, 4, 5, 6, 1, 2}, 2},
+	{[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, []int{4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3}, 3},
+	{[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, []int{7, 8, 9, 10, 1, 2, 3, 4, 5, 6}, 6},
+}
+
+func TestRotateNew(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := RotateNew(tc.original, tc.k); !reflect.DeepEqual(result, tc.rotated) {
+			t.Errorf("Expected %v got %v", tc.rotated, result)
+		}
+	}
+}
+
+func BenchmarkRotateNew(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			RotateNew(tc.original, tc.k)
+		}
+	}
+}
+
+func TestRotateKSwaps(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		copied := make([]int, len(tc.original))
+		copy(copied, tc.original)
+		RotateKSwaps(copied, tc.k)
+		if !reflect.DeepEqual(copied, tc.rotated) {
+			t.Errorf("Expected %v got %v", tc.rotated, copied)
+		}
+	}
+}
+
+func BenchmarkRotateKSwaps(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			copied := make([]int, len(tc.original))
+			copy(copied, tc.original)
+			RotateKSwaps(copied, tc.k)
+		}
+	}
+}
+
+func TestRotateJuggleSwaps(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		copied := make([]int, len(tc.original))
+		copy(copied, tc.original)
+		RotateJuggleSwaps(copied, tc.k)
+		if !reflect.DeepEqual(copied, tc.rotated) {
+			t.Errorf("Expected %v got %v", tc.rotated, copied)
+		}
+	}
+}
+
+func BenchmarkRotateJuggleSwaps(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			copied := make([]int, len(tc.original))
+			copy(copied, tc.original)
+			RotateJuggleSwaps(copied, tc.k)
+		}
+	}
+}