Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 401
Good morning! Here's your coding interview problem for today.

This problem was asked by Twitter.

A permutation can be specified by an array `P`, where `P[i]` represents the location of the element at i in the permutation. For example, `[2, 1, 0]` represents the permutation where elements at the index 0 and 2 are swapped.

Given an array and a permutation, apply the permutation to the array. For example, given the array `["a", "b", "c"]` and the permutation `[2, 1, 0]`, return `["c", "b", "a"]`.

Pull request description:
Day401
Resolves #805.

Patch:
diff --git a/README.md b/README.md
index 4012f8b..fe4c781 100644
--- a/README.md
+++ b/README.md
@@ -393,4 +393,5 @@ problems from
 * [Day 398](https://github.com/vaskoz/dailycodingproblem-go/issues/799)
 * [Day 399](https://github.com/vaskoz/dailycodingproblem-go/issues/801)
 * [Day 400](https://github.com/vaskoz/dailycodingproblem-go/issues/803)
+* [Day 401](https://github.com/vaskoz/dailycodingproblem-go/issues/805)
 
diff --git a/day401/problem.go b/day401/problem.go
new file mode 100644
index 0000000..d49a040
--- /dev/null
+++ b/day401/problem.go
@@ -0,0 +1,22 @@
+package day401
+
+// ApplyPermutation mutates the given input based on the
+// permutation information in the 2nd argument.
+// Runs in O(N) time and O(N/2) space.
+// Correct input is the responsibility of the caller.
+func ApplyPermutation(input []interface{}, permutation []int) {
+	if len(input) != len(permutation) {
+		panic("permutation length must match input length")
+	}
+
+	passed := make(map[int]interface{}, len(input))
+
+	for i, pos := range permutation {
+		if pos < i {
+			input[i] = passed[pos]
+		} else {
+			passed[i] = input[i]
+			input[i] = input[pos]
+		}
+	}
+}


Test patch:
diff --git a/day401/problem_test.go b/day401/problem_test.go
new file mode 100644
index 0000000..0620885
--- /dev/null
+++ b/day401/problem_test.go
@@ -0,0 +1,50 @@
+package day401
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	input    []interface{}
+	perm     []int
+	expected []interface{}
+}{
+	{
+		[]interface{}{"a", "b", "c"},
+		[]int{2, 1, 0},
+		[]interface{}{"c", "b", "a"},
+	},
+}
+
+func TestApplyPermutation(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		copied := append([]interface{}{}, tc.input...)
+		if ApplyPermutation(copied, tc.perm); !reflect.DeepEqual(copied, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, copied)
+		}
+	}
+}
+
+func TestApplyPermutationBadInput(t *testing.T) {
+	t.Parallel()
+
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("Expected a panic")
+		}
+	}()
+	ApplyPermutation([]interface{}{"a", "b", "c"}, []int{2, 1, 0, 3})
+}
+
+func BenchmarkApplyPermutation(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			copied := append([]interface{}{}, tc.input...)
+			ApplyPermutation(copied, tc.perm)
+		}
+	}
+}