Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 95
Good morning! Here's your coding interview problem for today.

This problem was asked by Palantir.

Given a number represented by a list of digits, find the next greater permutation of a number, in terms of lexicographic ordering. If there is not greater permutation possible, return the permutation with the lowest value/ordering.

For example, the list [1,2,3] should return [1,3,2]. The list [1,3,2] should return [2,1,3]. The list [3,2,1] should return [1,2,3].

Can you perform the operation without allocating extra memory (disregarding the input memory)?

Pull request:
Day95
Resolves #198. 

Patch:
diff --git a/README.md b/README.md
index 70585dd..e7a4e92 100644
--- a/README.md
+++ b/README.md
@@ -102,3 +102,4 @@ problems from
 * [Day 90](https://github.com/vaskoz/dailycodingproblem-go/issues/189)
 * [Day 91](https://github.com/vaskoz/dailycodingproblem-go/issues/192)
 * [Day 92](https://github.com/vaskoz/dailycodingproblem-go/issues/194)
+* [Day 95](https://github.com/vaskoz/dailycodingproblem-go/issues/198)
diff --git a/day95/problem.go b/day95/problem.go
new file mode 100644
index 0000000..1313ef1
--- /dev/null
+++ b/day95/problem.go
@@ -0,0 +1,27 @@
+package day95
+
+import "sort"
+
+// NextPermutation reorders the digits for the next
+// greater permutation.
+func NextPermutation(digits []int) {
+	var i int
+	for i = len(digits) - 1; i > 0; i-- {
+		if digits[i] > digits[i-1] {
+			break
+		}
+	}
+	if i == 0 {
+		sort.Ints(digits)
+		return
+	}
+	x := digits[i-1]
+	min := i
+	for j := i + 1; j < len(digits); j++ {
+		if digits[j] > x && digits[j] < digits[min] {
+			min = j
+		}
+	}
+	digits[i-1], digits[min] = digits[min], digits[i-1]
+	sort.Ints(digits[i:])
+}


Test patch:
diff --git a/day95/problem_test.go b/day95/problem_test.go
new file mode 100644
index 0000000..1f3f619
--- /dev/null
+++ b/day95/problem_test.go
@@ -0,0 +1,36 @@
+package day95
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	in, out []int
+}{
+	{[]int{1, 2, 3}, []int{1, 3, 2}},
+	{[]int{1, 3, 2}, []int{2, 1, 3}},
+	{[]int{3, 2, 1}, []int{1, 2, 3}},
+}
+
+func TestNextPermutation(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		in := make([]int, len(tc.in))
+		copy(in, tc.in)
+		NextPermutation(in)
+		if !reflect.DeepEqual(in, tc.out) {
+			t.Errorf("Expected %v got %v", tc.out, in)
+		}
+	}
+}
+
+func BenchmarkNextPermutation(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			in := make([]int, len(tc.in))
+			copy(in, tc.in)
+			NextPermutation(in)
+		}
+	}
+}