bloomberg mars组电面

七月初考的，难度不大，mars组，是个亚洲人考的，很可能是国人，第二题想了太久，用了暴力解法肯定也不是最优解。因为他们找个不是entry level我没工作经验所以也有可能被刷了

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

gt;(100,200)。现在如果有n个人，要求一半人数去la一半人数去ny，求最少花费是多少。

不知道是不是想简单了。。一个人要么去NY要么去LA，所以选择去哪个取决于费用的差别有多大。假设对于person i，费用是（x_i, y_i），按照 y_i- x_i 排序，最小的n/2个去LA，剩下的n/2去NY，应该就是最优解了。

请问lz，去la和ny这个题怎么做呀 （没想出来...）

gggpps 发表于 2018-7-29 04:15
请问lz，去la和ny这个题怎么做呀 （没想出来...）

我当时做的时候觉得应该还有bug，但面试官说对的，就让我过了，我用了好像六个variable去分别去两个地方的最小值，还有价格差的最小值等等，然后写了一堆if的比较条件，把人移来移去，相当复杂。我后来面完想到的思路是扫一遍每个人，开两个pq，排序方式用两个价格的差值排，一个存la一个存ny，然后每次加一个人的时候加入价格小的那个城市，然后比较两个pq的size，相差大于1的话，从大的那个里面移出一个价格差最小的人放到另一个pq里面，保持两个pq的size最多差1。然后再扫一遍pq里面每个人选的那个地点的价格，求总和在输出就行，不知道还有没有bug，如果有其他大神能想到其他方法或者指出错误也行！

luke77gu 发表于 2018-7-29 04:57
我当时做的时候觉得应该还有bug，但面试官说对的，就让我过了，我用了好像六个variable去分别去两个地方 ...

我现在想了下这样做还是不对，因为每次移出去的那个人，不一定是最终结果里差价最少的，因为我是从头到尾扫一遍的。可能先全部加入，然后再去比较两个pq的size差，然后确定需要移动几个人这样比较好。

luke77gu 发表于 2018-7-29 05:03
我现在想了下这样做还是不对，因为每次移出去的那个人，不一定是最终结果里差价最少的，因为我是从头到尾 ...

em..真的想不出来..能再问下一下lz是啥时候毕业的吗

Wangdong8500 发表于 2018-7-29 11:33
不知道是不是想简单了。。一个人要么去NY要么去LA，所以选择去哪个取决于费用的差别有多大。假设对于person ...

恩，我觉得这样应该是对的，我去写几个个test case试试

补充内容 (2018-7-30 12:37):
但有个edge case挺麻烦的，奇数的时候还得判断中间那个人到底是去la还是ny便宜

我大概写了下代码，应该对了，这个test结果是输出800的
public static int sum(List<int[]> people) {
        int sum = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->(a[0]-a[1])-(b[0]-b[1]));
        for (int[] pair: people) {
            pq.offer(pair);
        }
        int size = people.size();
        int la = size/2;
        for (int i = 0; i < la; i++) {
            sum += pq.poll()[0];
        }
        if (size % 2 == 1) {
            int [] mid = pq.poll();
            sum += Math.min(mid[0], mid[1]);
        }
        while (!pq.isEmpty()) {
            sum += pq.poll()[1];
        }
        return sum;
    }

    public static void main (String [] args) {
        List<int[]> test = new ArrayList<>();
        test.add(new int[]{100,200});
        test.add(new int[]{100,300});
        test.add(new int[]{200,100});
        test.add(new int[]{100,200});
        test.add(new int[]{300,500});
        System.out.println(sum(test));
    }

Wangdong8500 发表于 2018-7-29 11:33
不知道是不是想简单了。。一个人要么去NY要么去LA，所以选择去哪个取决于费用的差别有多大。假设对于person ...

还是要谢谢你啦 大神！！！！

楼主，第1题没怎么看懂为什么要用hashmap，能再解释一下吗？