Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 251
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given an array of a million integers between zero and a billion, out of order, how can you efficiently sort it? Assume that you cannot store an array of a billion elements in memory.

Pull request description:
Day251
Resolves #517 .

Patch:
diff --git a/README.md b/README.md
index 12d5343..dd4989b 100644
--- a/README.md
+++ b/README.md
@@ -261,3 +261,4 @@ problems from
 * [Day 247](https://github.com/vaskoz/dailycodingproblem-go/issues/510)
 * [Day 248](https://github.com/vaskoz/dailycodingproblem-go/issues/512)
 * [Day 249](https://github.com/vaskoz/dailycodingproblem-go/issues/514)
+* [Day 251](https://github.com/vaskoz/dailycodingproblem-go/issues/517)
diff --git a/day251/problem.go b/day251/problem.go
new file mode 100644
index 0000000..1595d39
--- /dev/null
+++ b/day251/problem.go
@@ -0,0 +1,32 @@
+package day251
+
+// RadixSortInt32 sorts int32's using radix sort.
+// Runs in linear time. O(w*n)
+func RadixSortInt32(nums []int32) {
+	var max int32
+	for _, v := range nums {
+		if v > max {
+			max = v
+		}
+	}
+	exp := int32(1)
+	for max/exp > 0 {
+		CountingSort(nums, exp)
+		exp *= 10
+	}
+}
+
+// CountingSort is a counting sort for int32's.
+func CountingSort(nums []int32, exp int32) {
+	counts := make([][]int32, 10)
+	for _, v := range nums {
+		pos := (v / exp) % 10
+		counts[pos] = append(counts[pos], v)
+	}
+	start := 0
+	for _, c := range counts {
+		end := start + len(c)
+		copy(nums[start:end], c)
+		start = end
+	}
+}


Test patch:
diff --git a/day251/problem_test.go b/day251/problem_test.go
new file mode 100644
index 0000000..e8c6f20
--- /dev/null
+++ b/day251/problem_test.go
@@ -0,0 +1,48 @@
+package day251
+
+import (
+	"reflect"
+	"sort"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	input, sorted []int32
+}{
+	{[]int32{170, 45, 75, 90, 802, 24, 2, 66}, []int32{2, 24, 45, 66, 75, 90, 170, 802}},
+}
+
+func TestRadixSortInt32(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		copied := make([]int32, len(tc.input))
+		copy(copied, tc.input)
+		RadixSortInt32(copied)
+		if !reflect.DeepEqual(copied, tc.sorted) {
+			t.Errorf("Expected %v, got %v", tc.sorted, copied)
+		}
+	}
+}
+
+func BenchmarkRadixSortInt32(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			copied := make([]int32, len(tc.input))
+			copy(copied, tc.input)
+			RadixSortInt32(copied)
+		}
+	}
+}
+
+func BenchmarkStdLibSort(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			copied := make([]int32, len(tc.input))
+			copy(copied, tc.input)
+			sort.Slice(copied, func(i, j int) bool {
+				return copied[i] < copied[j]
+			})
+		}
+	}
+}