Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 337
Good morning! Here's your coding interview problem for today.

This problem was asked by Apple.

Given a linked list, uniformly shuffle the nodes. What if we want to prioritize space over time?

Pull request:
Day337
Resolves #674.

Patch:
diff --git a/README.md b/README.md
index 52917c6..19daf0e 100644
--- a/README.md
+++ b/README.md
@@ -329,6 +329,7 @@ problems from
 * [Day 323](https://github.com/vaskoz/dailycodingproblem-go/issues/656)
 * [Day 324](https://github.com/vaskoz/dailycodingproblem-go/issues/658)
 * [Day 325](https://github.com/vaskoz/dailycodingproblem-go/issues/660)
+* [Day 337](https://github.com/vaskoz/dailycodingproblem-go/issues/674)
 * [Day 338](https://github.com/vaskoz/dailycodingproblem-go/issues/675)
 * [Day 339](https://github.com/vaskoz/dailycodingproblem-go/issues/676)
 * [Day 340](https://github.com/vaskoz/dailycodingproblem-go/issues/679)
diff --git a/day337/problem.go b/day337/problem.go
new file mode 100644
index 0000000..888336a
--- /dev/null
+++ b/day337/problem.go
@@ -0,0 +1,87 @@
+package day337
+
+import (
+	"math/rand"
+	"time"
+)
+
+// SinglyLL is a singly linked list of any kind of value.
+// Type management falls to the user.
+type SinglyLL struct {
+	Val  interface{}
+	Next *SinglyLL
+}
+
+// nolint
+var r *rand.Rand = rand.New(rand.NewSource(time.Now().UnixNano()))
+
+// FastShuffle uniformly shuffles the singly linked list in
+// O(N) time and O(N) space.
+// Technically, O(2N) space. First N is for slice of values, second N
+// is for new Linked List (not done in-place and doesn't mutate input linked list).
+func FastShuffle(head *SinglyLL) *SinglyLL {
+	data := convertToSlice(head)
+
+	r.Shuffle(len(data), func(i, j int) {
+		data[i], data[j] = data[j], data[i]
+	})
+
+	return convertToLL(data)
+}
+
+// MemoryOptimizedShuffle uniformly shuffles the singly linked list
+// in O(N^2) time and O(1) space.
+func MemoryOptimizedShuffle(head *SinglyLL) *SinglyLL {
+	n := size(head)
+	origHolder := &SinglyLL{nil, head}
+	resultHolder := &SinglyLL{}
+	resultTail := resultHolder
+
+	for items := n; items > 0; items-- {
+		curr := origHolder
+
+		for i := 0; i < r.Intn(items); i++ {
+			curr = curr.Next
+		}
+
+		resultTail.Next = curr.Next
+		curr.Next = curr.Next.Next
+		resultTail = resultTail.Next
+		resultTail.Next = nil
+	}
+
+	return resultHolder.Next
+}
+
+func size(head *SinglyLL) int {
+	var count int
+
+	for ; head != nil; head = head.Next {
+		count++
+	}
+
+	return count
+}
+
+func convertToLL(data []interface{}) *SinglyLL {
+	holder := &SinglyLL{}
+	current := holder
+
+	for i := range data {
+		current.Next = &SinglyLL{data[i], nil}
+		current = current.Next
+	}
+
+	return holder.Next
+}
+
+func convertToSlice(head *SinglyLL) []interface{} {
+	var result []interface{}
+
+	for head != nil {
+		result = append(result, head.Val)
+		head = head.Next
+	}
+
+	return result
+}


Test patch:
diff --git a/day337/problem_test.go b/day337/problem_test.go
new file mode 100644
index 0000000..822dc58
--- /dev/null
+++ b/day337/problem_test.go
@@ -0,0 +1,83 @@
+package day337
+
+import (
+	"math/rand"
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	input                          []interface{}
+	expectedFastShuffle            []interface{}
+	expectedMemoryOptimizedShuffle []interface{}
+}{
+	{
+		[]interface{}{"a", 1, 3.5, "foobar", nil, nil, nil},
+		[]interface{}{"foobar", 1, nil, "a", nil, nil, 3.5},
+		[]interface{}{"a", 1, "foobar", nil, nil, nil, 3.5},
+	},
+}
+
+func TestFastShuffle(t *testing.T) {
+	// NOTE: Don't run tests in parallel. Setting a global variable is a race.
+	// t.Parallel()
+	r = rand.New(rand.NewSource(314159))
+
+	for _, tc := range testcases {
+		head := convertToLL(tc.input)
+		ll := FastShuffle(head)
+		result := convertToSlice(ll)
+
+		if !reflect.DeepEqual(result, tc.expectedFastShuffle) {
+			t.Errorf("Expected %v, got %v", tc.expectedFastShuffle, result)
+		}
+	}
+}
+
+func TestMemoryOptimizedShuffle(t *testing.T) {
+	// NOTE: Don't run tests in parallel. Setting a global variable is a race.
+	// t.Parallel()
+	r = rand.New(rand.NewSource(314159))
+
+	for _, tc := range testcases {
+		head := convertToLL(tc.input)
+		ll := MemoryOptimizedShuffle(head)
+		result := convertToSlice(ll)
+
+		if !reflect.DeepEqual(result, tc.expectedMemoryOptimizedShuffle) {
+			t.Errorf("Expected %v, got %v", tc.expectedMemoryOptimizedShuffle, result)
+		}
+	}
+}
+
+func BenchmarkFastShuffle(b *testing.B) {
+	large := make([]interface{}, 10_000)
+
+	for i := range large {
+		large[i] = i
+	}
+
+	head := convertToLL(large)
+
+	b.ResetTimer()
+
+	for i := 0; i < b.N; i++ {
+		head = FastShuffle(head)
+	}
+}
+
+func BenchmarkMemoryOptimizedShuffle(b *testing.B) {
+	large := make([]interface{}, 10_000)
+	for i := range large {
+		large[i] = i
+	}
+
+	head := convertToLL(large)
+
+	b.ResetTimer()
+
+	for i := 0; i < b.N; i++ {
+		head = MemoryOptimizedShuffle(head)
+	}
+}