Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 118
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given a sorted list of integers, square the elements and give the output in sorted order.

For example, given `[-9, -2, 0, 2, 3]`, return `[0, 4, 4, 9, 81]`.

Pull request:
Day118
Resolves #246.

Patch:
diff --git a/README.md b/README.md
index a27ef47..b2c7ff2 100644
--- a/README.md
+++ b/README.md
@@ -126,4 +126,5 @@ problems from
 * [Day 114](https://github.com/vaskoz/dailycodingproblem-go/issues/237)
 * [Day 115](https://github.com/vaskoz/dailycodingproblem-go/issues/238)
 * [Day 116](https://github.com/vaskoz/dailycodingproblem-go/issues/242)
+* [Day 118](https://github.com/vaskoz/dailycodingproblem-go/issues/246)
 * [Day 120](https://github.com/vaskoz/dailycodingproblem-go/issues/248)
diff --git a/day118/problem.go b/day118/problem.go
new file mode 100644
index 0000000..14eda9d
--- /dev/null
+++ b/day118/problem.go
@@ -0,0 +1,52 @@
+package day118
+
+import (
+	"sort"
+)
+
+// SquareElementsSortedBrute returns the squared result of every element of the param.
+// Runs in O(N log N) due to sorting the results.
+func SquareElementsSortedBrute(sorted []int) []int {
+	result := make([]int, len(sorted))
+	for i := range sorted {
+		result[i] = sorted[i] * sorted[i]
+	}
+	sort.Ints(result)
+	return result
+}
+
+// SquareElementsSortedLinear returns the squared result of every element of the param.
+// Runs in O(N) due to merging two sorted lists into the result.
+func SquareElementsSortedLinear(sorted []int) []int {
+	result := make([]int, 0, len(sorted))
+	firstPositiveIndex := 0
+	for i := range sorted {
+		if sorted[i] >= 0 {
+			firstPositiveIndex = i
+			break
+		}
+	}
+	negI, posI := firstPositiveIndex-1, firstPositiveIndex
+	for {
+		if negI >= 0 && posI < len(sorted) {
+			a := sorted[negI] * sorted[negI]
+			b := sorted[posI] * sorted[posI]
+			if a < b {
+				result = append(result, a)
+				negI--
+			} else {
+				result = append(result, b)
+				posI++
+			}
+		} else if negI >= 0 {
+			result = append(result, sorted[negI]*sorted[negI])
+			negI--
+		} else if posI < len(sorted) {
+			result = append(result, sorted[posI]*sorted[posI])
+			posI++
+		} else {
+			break
+		}
+	}
+	return result
+}


Test patch:
diff --git a/day118/problem_test.go b/day118/problem_test.go
new file mode 100644
index 0000000..171cea6
--- /dev/null
+++ b/day118/problem_test.go
@@ -0,0 +1,48 @@
+package day118
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	input, expected []int
+}{
+	{[]int{-9, -2, 0, 2, 3}, []int{0, 4, 4, 9, 81}},
+	{[]int{-20, -19, -18, -17, -16, -15, -14, -13, -12, -11, -10, -9,
+		-2, 0, 2, 3, 4, 5, 7, 10, 12, 14, 18, 20, 22, 24, 25, 26, 27, 29, 30},
+		[]int{0, 4, 4, 9, 16, 25, 49, 81, 100, 100, 121, 144, 144, 169, 196, 196,
+			225, 256, 289, 324, 324, 361, 400, 400, 484, 576, 625, 676, 729, 841, 900}},
+}
+
+func TestSquareElementsSortedBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SquareElementsSortedBrute(tc.input); !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+func BenchmarkSquareElementsSortedBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SquareElementsSortedBrute(tc.input)
+		}
+	}
+}
+
+func TestSquareElementsSortedLinear(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SquareElementsSortedLinear(tc.input); !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+func BenchmarkSquareElementsSortedLinear(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SquareElementsSortedLinear(tc.input)
+		}
+	}
+}