Wish phone interview挂经

多伦多的愿望 挂在了第二个phone interview上，其实我题做出来了，test case也给了而且都compile 通过了，想来想去想不通有什么被挂的理由，可能就是其他的candidate太强了所以可以直接因为背景把我pass了

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

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

然后第二个面完很快就收到hr的拒信，本来还想着根据朋友说的体做出来了以为能去onsite了，果然是在内心里给自己理了个flag嘛。有点郁闷，但也只能move on了。

eshang 发表于 2019-1-22 04:37
哦吼吼我反而觉得考官更喜欢看你用内置吧这样不用重复造轮子。。不过无所谓了，楼主加油哦
PS: 为啥我越 ...

我刚刚仔细想了想，divide and conquer的确是有限空间下sort的最优解（古人诚不欺我），因为同样是O（nlogk），用merge sort的多项式n前面的系数会比用priority queue小一点，因为merge sort里面第一遍就把一半的顺序排好了，这时候每个数字的操作次数是k，但是priority queue把一半排好的时候已经有一半都扔进去了，这时候的操作次数已经打到log(n/2)*k了。

你可以先固定有n个k个数字的list，手动把这两种O（nlogk）的polynomial算出来看看

补充内容 (2019-1-22 05:55):
nvm，我刚刚想成把所有都推到一个priority queue里了，也可以先分开来推到不同的queue里分治

eshang 发表于 2019-1-22 04:17
就是NlogK啊，这不就是最优解嘛，但是priority queue是内置的，所以代码写起来会清晰一些吧

对。。我只是在争对“会不会更快一点”在理思路。
我面试的时候不敢用太多内置的，万一考官follow up question：你知道这个内置的data strctrue的XX function是怎么实现的，答错了就尴尬了

补充内容 (2019-1-22 04:22):
*针对

消逝一风 发表于 2019-1-22 04:21
对。。我只是在争对“会不会更快一点”在理思路。
我面试的时候不敢用太多内置的，万一考官follow up qu ...

哦吼吼我反而觉得考官更喜欢看你用内置吧这样不用重复造轮子。。不过无所谓了，楼主加油哦
PS: 为啥我越回复你积分越低啊。。能不能给点大米。。快要看不了帖子了

第二个你是两个两个merge的么， 还是同时merge所有lists， 每次取k个lists中最小的

eshang 发表于 2019-1-20 02:12
第二个你是两个两个merge的么， 还是同时merge所有lists， 每次取k个lists中最小的

两个两个的，为了nlogn

消逝一风 发表于 2019-1-20 02:33
两个两个的，为了nlogn

用priority queue来同时merge K个， 会不会更快些。

eshang 发表于 2019-1-20 05:38
用priority queue来同时merge K个， 会不会更快些。

你想想，priority queue的insert的time complexity是多少？

消逝一风 发表于 2019-1-20 10:01
你想想，priority queue的insert的time complexity是多少？

不是logK嘛？

eshang 发表于 2019-1-22 02:43
不是logK嘛？

那用priority queue的方法要做多少次insert？

消逝一风 发表于 2019-1-22 04:11
那用priority queue的方法要做多少次insert？

就是NlogK啊，这不就是最优解嘛，但是priority queue是内置的，所以代码写起来会清晰一些吧