Round numbers - Airbnb

https://github.com/allaboutjst/airbnb/blob/master/README.md

Given an array of numbers A = [x1, x2, ..., xn] and T = Round(x1+x2+... +xn). We want to find a way to round each element in A such that after rounding we get a new array B = [y1, y2, ...., yn] such that y1+y2+...+yn = T where yi = Floor(xi) or Ceil(xi), ceiling or floor of xi.

We also want to minimize sum |x_i-y_i|

17. Round Prices: 每个数统一向下取整，然后判断其sum与原近似值sum差值多少来决定有多少数需要向上取整，然后根据小数部分排序，拥有较小的小数部分的数向下取整，其他的向上取整
https://github.com/allaboutjst/airbnb/blob/master/src/main/java/round_prices/RoundPrices.java

        public int[] roundUp(double[] arr) {
            int n = arr.length;
            NumWithDiff[] arrWithDiff = new NumWithDiff[n];
            double sum = 0.0;
            int floorSum = 0;
            for (int i = 0; i < n; i++) {
                int floor = (int) arr[i];
                int ceil = floor;
                if (floor < arr[i]) ceil++;
                floorSum += floor;
                sum += arr[i];
                arrWithDiff[i] = new NumWithDiff(ceil, ceil - arr[i]);
            }

            int num = (int) Math.round(sum);
            int diff = num - floorSum;
            Arrays.sort(arrWithDiff, new Comparator<NumWithDiff>() {
                @Override
                public int compare(NumWithDiff n1, NumWithDiff n2) {
                    if (n1.diffWithCeil <= n2.diffWithCeil) return -1;
                    else return 1;
                }
            });
            // Arrays.sort(arrWithDiff, (a, b) -> (Double.compare(b.diffWithCeil, a.diffWithCeil)));

            int[] res = new int[n];
            int i = 0;
            for (; i < diff; i++) {
                res[i] = arrWithDiff[i].num; // 这些放ceil
            }
            for (; i < n; i++) {
                res[i] = arrWithDiff[i].num - 1; // 剩下的只放floor
            }
            return res;
        }

        class NumWithDiff {
            int num;
            double diffWithCeil;

            public NumWithDiff(int n, double c) {
                this.num = n;
                this.diffWithCeil = c;
            }
        }

        public int[] roundUp(double[] prices) {
            if (prices == null || prices.length == 0) {
                return new int[0];
            }

            int[] res = new int[prices.length];

            double sum = 0;
            int roundSum = 0;
            Number[] numbers = new Number[prices.length];
            for (int i = 0; i < prices.length; i++) {
                numbers[i] = new Number(prices[i], i);
                sum += prices[i];
                roundSum += (int) Math.round(prices[i]);
                res[i] = (int) Math.round(prices[i]);
            }
            int sumRound = (int) Math.round(sum);

            if (sumRound == roundSum) {
                return res;
            } else if (sumRound > roundSum) {
                Arrays.sort(numbers, (a, b) -> (Double.compare(b.frac, a.frac)));
                int count = sumRound - roundSum;
                for (int i = 0; i < prices.length; i++) {
                    Number num = numbers[i];
                    if (num.frac < 0.5 && count > 0) {
                        res[num.index] = (int) Math.ceil(num.val);
                        count--;
                    } else {
                        res[num.index] = (int) Math.round(num.val);
                    }
                }
            } else {
                Arrays.sort(numbers, (a, b) -> (Double.compare(a.frac, b.frac)));
                int count = roundSum - sumRound;
                for (int i = 0; i < prices.length; i++) {
                    Number num = numbers[i];
                    if (num.frac >= 0.5 && count > 0) {
                        res[num.index] = (int) Math.floor(num.val);
                        count--;
                    } else {
                        res[num.index] = (int) Math.round(num.val);
                    }
                }
            }

            return res;
        }

        class Number {
            double val;
            double frac;
            int index;

            Number(double val, int index) {
                this.val = val;
                this.frac = val - Math.floor(val);
                this.index = index;
            }
        }

https://discuss.leetcode.com/topic/246/round-numbers

When you book on airbnb the total price is:

Total price = base price + service fee + cleaning fee + ...

input : array of decimals ~ X
output : array of int ~ Y

But they need to satisfy the condition:

1. sum(Y) = round(sum(x))
2. minmize (|y1-x1| + |y2-x2| + ... + |yn-xn|)

Example1:
input = 30.3, 2.4, 3.5
output = 30 2 4

Example2:
input = 30.9, 2.4, 3.9
output = 31 2 4

airbnb面试题汇总
先将所有floor(x)加起来统计出如果所有都floor的话还差多少，按照ceil以后需要加的价格排序，贪心取最小的补齐即可。

def roundNum(self, input):
    output = map(lambda x: floor(x), input)
    remain = int(round(sum(input)) - sum(output))
    it = sorted(enumerate(input), key=lambda x: x[1] - floor(x[1]))
    for _ in xrange(remain):
        output[it.pop()[0]] += 1
    return output

//c++
vector<int> roundNumber(vector<double>& prices) {
    vector<int> ans;
    int got = 0;
    double all = 0.0;
    vector<pair<double, int> > s_prices;
    for (int i = 0; i < prices.size(); ++i) {
        double price = prices[i];
        int tmp = int(floor(price));
        got += tmp;
        ans.push_back(tmp);
        all += price;
        s_prices.push_back(make_pair(price, i));
    }
    sort (s_prices.begin(), s_prices.end(),
         [](pair<double, int> a, pair<double, int> b)
         { return a.first - floor(a.first) > b.first - floor(b.first);});
    for (int i = 0; i < int(round(all)) - got; ++i) {
        ans[s_prices[i].second]++;
    }
    return ans;
}

from math import floor

def roundNumbers(input):
    output = map(lambda x: floor(x), input)
    remain = round(sum(input) - sum(output))
    
    it = sorted(enumerate(input), key=lambda i: i[1] - floor(i[1]))
    for _ in range(remain):
        output[it.pop()[0]] += 1

    return output

https://github.com/joseph5wu/LeetCode/blob/master/src/airbnb/roundsSum/Solution.java
public static int[] round(double[] nums) {
    // calculate the round sum, and then sort the nums with the difference between ceiling
    // and then make those close to ceil be ceiling, close to floor be floor
    NumWithDiff[] diffNums = new NumWithDiff[nums.length];
    double sum = 0.0;
    int floorSum = 0;
    for(int i = 0; i < nums.length; i++) {
        double num = nums[i];
        int floor = (int) num;
        int ceil = floor;
        if(floor < num) {
            ceil++;
        }
        floorSum += floor;
        sum += num;
        diffNums[i] = new NumWithDiff(ceil, ceil - num);
    }

    // sort the diffNums
    Arrays.sort(diffNums, new Comparator<NumWithDiff>() {
        public int compare(NumWithDiff n1, NumWithDiff n2) {
            if(n1.diff <= n2.diff) {
                return -1;
            }
            return 1;
        }
    });

    int roundSum = (int)Math.round(sum);
    int toCeilNum = roundSum - floorSum;
    int[] results = new int[nums.length];
    int i = 0;
    while(i < toCeilNum) {
        results[i] = diffNums[i].num;
        i++;
    }
    while(i < nums.length) {
        results[i] = diffNums[i].num - 1;
        i++;
    }
    return results;
}
https://github.com/gabhi/leetcode-1/blob/master/b/Rounding.java
public int[] round(Double[] input) {
  if(input == null || input.length == 0) return new int[0];

  Queue<Double> minCeil = new PriorityQueue<Double>(input.length, new Comparator<Double>() {
    public int compare(Double x, Double y) {
      return Double.compare(Math.ceil(x) - x, Math.ceil(y) - y);
    }
  });
  // Get offset
  Double sum = 0.0;
  int floorSum = 0;
  int[] res = new int[input.length];
  for(int i = 0; i < input.length; i++) {
    sum += input[i];
    int floor = (int) Math.floor(input[i]);
    floorSum += floor;
    res[i] = floor;
    minCeil.add(input[i]);
  }
  // Numbers contributing to larger
  int offset = (int) Math.round(sum) - floorSum;
  Set<Double> mins = new HashSet<>();
  for(int i = 0; i < offset; i++) {
    mins.add(minCeil.poll());
  }

  for(int i = 0; i < res.length && offset > 0; i++) {
    if(mins.contains(input[i])) {
      res[i]++;
      offset--;
    }
  }
  return res;
}

https://stackoverflow.com/questions/792460/how-to-round-floats-to-integers-while-preserving-their-sum

http://www.1point3acres.com/bbs/thread-161001-1-1.html

Given an array of numbers A = [x1, x2, ..., xn] and T = Round(x1+x2+... +xn).

We want to find a way to round each element in A such that after rounding we get a new array B = [y1, y2, ...., yn] such that y1+y2+...+yn = T where  yi = Floor(xi) or Ceil(xi), ceiling or floor of xi.

We also want to minimize sum |x_i-y_i|

float也行。然后还要考虑正负。

http://www.1point3acres.com/bbs/thread-156061-1-1.html
像LC里的text justification, regular expression matching在他家都算是热身题，感觉大部分题自己都不能独立做出来，比如csv parser, 之类

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=146539
他们公司list价格分成好几个部分，但是都是整数，如果在美金是整数，到了欧洲的网页显示汇率转换之后就变成了floating point，然后要round成整数，但是全部加起来round，和单独round再加起来，结果会不一样
# base price    100 =>  131.13   => 131
# cleaning fee   20 =>   26.23   => 26
# service fee    10 =>   13.54   => 14
# tax                5 =>    6.5      => 7
#                        =>  177.4E   => 178E
# sum           135$ => 178.93E => 179E 
鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
那么问题就来了，给个input list of floating points, 要求output list of integers, 满足以下两个constraint， 就是和跟Round(x1+x2+... +xn)的结果一样，但是minimize output 和input的绝对值差之和
#Input: A = [x1, x2, ..., xn]
# Sum T = Round(x1+x2+... +xn)  ;  178.93E => 179
# Output: B = [y1, y2, ...., yn]

# Constraint #1: y1+y2+...+yn = T
# Constraint #2: minimize sum(abs(diff(xi - yi)))

举例. visit 1point3acres.com for more.
# A = [1.2, 2.3, 3.4]
# Round(1.2 + 2.3 + 3.4) = 6.9 => 7
# 1 + 2 + 3 => 6
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
# 1 + 3 + 3 => 7. 鍥磋鎴戜滑@1point 3 acres
# 0.2 + 0.7 + 0.4 = 1.3

# 1 + 2 + 4 => 7
# 0.2 + 0.3 + 0.6 = 1.1
所以[1,2,4]比[1,3,3]要好

1.         // 思路就是先把所有floor加起来，然后看差多少，然后把多少个floor转成ceil
2.         // 转的时候按照num本身与ceil的距离排序
3.         public static int[] getNearlyArrayWithSameSum(double[] arr) {
4.                 NumWithDiff[] arrWithDiff = new NumWithDiff[arr.length];
5.                 double sum = 0.0;
6.                 int floorSum = 0;
7.                 for (int i = 0; i < arr.length; i++) {
8.                         int floor = (int)arr[i];
9.                         int ceil = floor;
10.                         if (floor < arr[i]) ceil++; // 查是不是4.0这种floor/ceil都是本身的
11.                         floorSum += floor;
12.                         sum += arr[i];. 1point3acres.com/bbs
13.                         arrWithDiff[i] = new NumWithDiff(ceil, ceil - arr[i]); // 把ceil都放在数组里面进行比较
14.                 }
15.                 int num = (int) Math.round(sum);
16.                 int diff = num - floorSum;
17.                 Arrays.sort(arrWithDiff, new Comparator<NumWithDiff>() {
18.                         public int compare(NumWithDiff n1, NumWithDiff n2) {. from: 1point3acres.com/bbs 
19.                                 if (n1.diffWithCeil <= n2.diffWithCeil) return -1;
20.                                 else return 1;
21.                         }
22.                 });. from: 1point3acres.com/bbs 
23.                 int[] res = new int[arr.length];
24.                 int i = 0;. From 1point 3acres bbs
25.                 for (; i < diff; i++) {. 1point3acres.com/bbs
26.                         res[i] = arrWithDiff[i].num; // 这些放ceil
27.                 }
28.                 for (; i < arr.length; i++) {
29.                         res[i] = arrWithDiff[i].num - 1; // 剩下的只放floor
30.                 }
31.                 return res;
32.         }