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.
Good morning! Here's your coding interview problem for today.
This problem was asked by Airbnb.
You are given an array
Xof floating-point numbersx1, x2, ... xn. These can be rounded up or down to create a corresponding arrayYof integersy1, y2, ... yn.Write an algorithm that finds an appropriate
Yarray with the following properties:|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.