新鲜出炉的Bloomberg电面！！！MARS组

刚刚电面完MARS组。其实本来昨天就要结束这个电面，可是面到一半，准备写代码的时候，codepair崩了。。真是心塞，然后重新约了今天，继续了昨天的

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

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

天还有另外一个Search的组面试，希望能拿到个onsite吧，好久没去扭腰了。

这个题在别的帖子里看到了。可以这么考虑，假设k=1，选一个去NY的，让总的cost最小，怎么选？每个人的<costToNY, costToSF>简写成<x, y>

假设现在选了一个participant去NY，他的cost是<x, y>，然后想找一个去了SF的替换他，让总的cost最小，那么另一个人的cost是<x1, y1>
替换后，去NY从x变成x1，变化是x1-x，去SF从y1变成y，变化是y-y1
这个替换过程会造成总的cost的变化是：(x1 - x) + (y - y1)，为了让这个替换使得总cost变小，需要(x1 - x) + (y - y1) < 0 变形成 x1 - y1 < x - y
也就是需要新替换的人的x1 - y1小于当前去NY的那个人的x -y，所以问题就变成了选出x - y最小的那个数

如果选k个人，就是做k次这样的选择，不超过一半，就是k小于等于一半，最后变成选Top K（这里是x - y最小的k个）的问题，可以排序，或者维护一个max heap里保存k个最小的
时间复杂度就是O(nlogk)

wesker1988 发表于 2018-7-30 10:47
我觉得第二题最简单的做法就是另个帖子里有人提到的以每个人去两地的差值排序，先把一地的最大容量填满，然 ...

同意阿。和ｚｈａｏｃｏｎｇ２８的分析类似。但，其实算个差值，排个序就可以拉。比如一开始假设所有人去ＳＦ，然后挑出一般人去ＮＹ。每挑一个人对整体ｃｏｓｔ的影响是增加ｃｏｓｔＮＹ－ｃｏｓｔＳＦ。对ｃｏｓｔＮＹ－ｃｏｓｔＳＦ排序，找出最小的那些就是。

coderpad崩了。。。。。楼主好运，我也马上电面了

楼主能详细说下第二题是怎么回事吗？没看太懂

北极猪一只 发表于 2018-7-19 07:14
楼主能详细说下第二题是怎么回事吗？没看太懂

我想是应该怎么分配这些人才能使总cost最小

gabelois 发表于 2018-7-19 08:10
我想是应该怎么分配这些人才能使总cost最小

返回最小的cost就可以，没有说需要把具体怎么分配找出来。
比如<500, 600>
       <100, 300>
这是两个人
那最小cost就是 100 + 600 = 700

backtrack？

gabelois 发表于 2018-7-19 08:25
backtrack？

怎么做？穷举嘛？然后backtrack？只需要求cost的值就好了。感觉像是dp。。

第二题的意思是不是participant要不去ny要不去sf？要求一半人去ny，一半人去sf？

UCLA_andy 发表于 2018-7-19 08:13
返回最小的cost就可以，没有说需要把具体怎么分配找出来。
比如
      

请问下，那个最多一半是什么意思？