BB 6月末挂经

网上海投的new grad岗，直接安排了电面。一个三哥，感觉不怎么友好，不等把话讲完就一直问问题。一个题目，讲了思路，没等写就问有没有更好的方法，又说了一个，还问有没有更好的。没想出来就写的第二个。

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

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

看了楼主的解释，想了半天才想明白，其实是个数学推导问题。

可以这么考虑，假设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
也就是需要去SF的那个人的x1 - y1小于当前去NY的那个人的x - y，所以问题就变成了选出x - y最小的那个数

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

能具体说说这个做法的有效性嚒

houqingniao 发表于 2018-7-13 10:11
能具体说说这个做法的有效性嚒

假设ab两个地方，k个去a，随机分k个去a，然后为了优化会把b中的一些挪到a里交换，tuple[0]-tuple[1]就是把这个tuple挪b总cost减少的量，如果tuple=[100,300]差是负值就是总cost会增加，差值正数就是总cost会减少， 差越小绝对值越大，就是挪到b后cost增加的越多，min k就会留在a里。所以就是个heap求min k的问题，时间复杂度O(k+(n-k)logk).如果说的不对请帮忙指正。。

希望楼主 能够再接再厉

可否问下楼主投的啥职位呃 BB官网上还没有2018fall new grad 的opening吧。 已加米

DavidLi210 发表于 2018-7-24 12:49
可否问下楼主投的啥职位呃 BB官网上还没有2018fall new grad 的opening吧。 已加米

米呢米呢，别光说不加啊😂我6月初海投的，岗位是去年年底po出来的，2018 Software Engineer - 64159

LATTES 发表于 2018-7-24 13:05
米呢米呢，别光说不加啊😂我6月初海投的，岗位是去年年底po出来的，2018 Software Engineer - 641 ...

我去 不知道现在还能不能投

补充内容 (2018-7-24 13:40):
话说 你建议现在投吗

补充内容 (2018-7-24 13:42):
投这个岗位

DavidLi210 发表于 2018-7-24 13:40
我去 不知道现在还能不能投

补充内容 (2018-7-24 13:40):

反正不知道满没满，投呗，再不投等啥时候投，而且听说他们家没冷冻？我不确定

这个有点tricky啊。。。。把题目理解清楚就简单了