Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 355
Good morning! Here's your coding interview problem for today.

This problem was asked by Airbnb.

You are given an array `X` of floating-point numbers `x1, x2, ... xn`. These can be rounded up or down to create a corresponding array `Y` of integers `y1, y2, ... yn`.

Write an algorithm that finds an appropriate `Y` array with the following properties:

* The rounded sums of both arrays should be equal.
* The absolute pairwise difference between elements is minimized. In other words, `|x1- y1| + |x2- y2| + ... + |xn- yn|` should be as small as possible.
For example, suppose your input is `[1.3, 2.3, 4.4]`. In this case you cannot do better than `[1, 2, 5]`, which has an absolute difference of `|1.3 - 1| + |2.3 - 2| + |4.4 - 5| = 1`.

Pull request:
Day355
Resolves #704.

Patch:
diff --git a/README.md b/README.md
index ad8a13b..52917c6 100644
--- a/README.md
+++ b/README.md
@@ -340,6 +340,7 @@ problems from
 * [Day 350](https://github.com/vaskoz/dailycodingproblem-go/issues/695)
 * [Day 352](https://github.com/vaskoz/dailycodingproblem-go/issues/699)
 * [Day 353](https://github.com/vaskoz/dailycodingproblem-go/issues/701)
+* [Day 355](https://github.com/vaskoz/dailycodingproblem-go/issues/704)
 * [Day 356](https://github.com/vaskoz/dailycodingproblem-go/issues/705)
 * [Day 359](https://github.com/vaskoz/dailycodingproblem-go/issues/708)
 * [Day 360](https://github.com/vaskoz/dailycodingproblem-go/issues/709)
diff --git a/day355/problem.go b/day355/problem.go
new file mode 100644
index 0000000..afb13ba
--- /dev/null
+++ b/day355/problem.go
@@ -0,0 +1,76 @@
+package day355
+
+import (
+	"sort"
+)
+
+type index struct {
+	pos int
+	val float64
+}
+
+// FindY returns the value of Y that meets the requirements
+// of the problem.
+// Runs in O(N log N) time and O(N) space due to sorting
+// the data by fractional value.
+func FindY(x []float64) []int {
+	var sumX float64
+
+	var sumY int
+
+	data := make([]index, len(x))
+
+	for pos, val := range x {
+		data[pos] = index{pos, val}
+		sumX += val
+		sumY += int(val)
+	}
+
+	// sort by smallest fractional value.
+	sort.Slice(data, func(i, j int) bool {
+		di := data[i].val - float64(int(data[i].val))
+		dj := data[j].val - float64(int(data[j].val))
+		return di < dj
+	})
+
+	yLow := make([]int, len(x))
+	sumXlow := int(sumX)
+	yLowOnes := sumXlow - sumY
+	yHighOnes := yLowOnes + 1
+
+	var yLowDiff float64
+
+	for i := 0; i < len(data)-yLowOnes; i++ {
+		pos := data[i].pos
+		yLow[pos] = int(data[i].val)
+		yLowDiff += data[i].val - float64(yLow[pos])
+	}
+
+	for i := len(data) - yLowOnes; i < len(data); i++ {
+		pos := data[i].pos
+		yLow[pos] = int(data[i].val) + 1
+		yLowDiff += float64(yLow[pos]) - data[i].val
+	}
+
+	var yHighDiff float64
+
+	yHigh := make([]int, len(x))
+
+	for i := 0; i < len(data)-yHighOnes; i++ {
+		pos := data[i].pos
+		yHigh[pos] = int(data[i].val)
+		yHighDiff += (data[i].val - float64(yHigh[pos]))
+	}
+
+	for i := len(data) - yHighOnes; i < len(data); i++ {
+		pos := data[i].pos
+		yHigh[pos] = int(data[i].val) + 1
+		yHighDiff += (float64(yHigh[pos]) - data[i].val)
+	}
+
+	if yLowDiff < yHighDiff {
+		return yLow
+	}
+
+	return yHigh
+}


Test patch:
diff --git a/day355/problem_test.go b/day355/problem_test.go
new file mode 100644
index 0000000..2fbfa15
--- /dev/null
+++ b/day355/problem_test.go
@@ -0,0 +1,43 @@
+package day355
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	x []float64
+	y []int
+}{
+	{
+		[]float64{1.3, 2.3, 4.4},
+		[]int{1, 2, 5},
+	},
+	{
+		[]float64{4.4, 1.3, 2.3},
+		[]int{5, 1, 2},
+	},
+	{
+		[]float64{1.5, 2.9, 4.55},
+		[]int{1, 3, 5},
+	},
+}
+
+func TestFindY(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if y := FindY(tc.x); !reflect.DeepEqual(y, tc.y) {
+			t.Errorf("Expected %v, got %v", tc.y, y)
+		}
+	}
+}
+
+func BenchmarkFindY(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FindY(tc.x)
+		}
+	}
+}