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.         }


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts