This question I've heard from friend of mine who, recently, had a phone interview with AirBnB.
Here is the question:
Total booking price = base price + service fee + cleaning fee + ...
Create a function which satisfy following condition:
Input: An array of decimals ~ X
Output: An array of integers ~ Y
sum(Y) = round(sum(x))
minimize the value of (|y1-x1| + |y2-x2| +… + |yn-xn|)
Example 1:
input = [0.3, 0.5, 0.6, 0.8, 0.9, 2.1, 3.4]
output = [ 0, 1, 1, 1, 1, 2, 3 ]
Example 2:
input = [0.5, 7.6, 47.4]
output = [ 1, 8, 47 ]
I've decided to solve it in my free time using Javascript, here is my solution:
//let numbers = [0.3, 0.5, 0.6, 0.8, 0.9, 2.1, 3.4]; // input
//let numbers = [0.7, 0.7, 0.8];
//let numbers = [0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1];
//let numbers = [3.7, 1.7, 0.8];
let numbers = [0.5, 7.6, 47.4];
function roundNumbers(input) {
let flooredNumbers = input.map(function(a){return Math.floor(a)});
let sumLeft = Math.round(sum(input)) - sum(flooredNumbers);
let sorted = [];
input.forEach(function(a,i){
sorted.push({
idx: i,
elm: (a-Math.floor(a))
})
});
sorted.sort(function(a,b){ return b.elm - a.elm});
let i = 0;
while(i < sumLeft) {
flooredNumbers[sorted[i].idx] += 1;
i++;
}
return flooredNumbers;
}
function sum(arr) {
return arr.reduce((a, b) => a + b, 0);
}
roundNumbers(numbers);