Bloomberg 12.13 尚有余温的Onsite两轮游

小鱼小玉 发表于 2017-12-29 11:27
天哪，楼主这么牛竟然也没过。。。。感觉你的解法都很优秀啊。。。想哭

我这次发挥只能说中规中矩吧，没到无可挑剔的地步。确实第一轮找第二小的数，我第一版本写完，他给出了那个test cases之后我一脑抽想都没仔细想就直接说这个corner cases我没考虑到……然后立马把程序改动了一下。我觉得我应该死在这儿了吧，连你自己都认为这道算easy的题目都有bug，毕竟是第一题印象很重要。

hawkingsecond 发表于 2017-12-30 00:54
我这次发挥只能说中规中矩吧，没到无可挑剔的地步。确实第一轮找第二小的数，我第一版本写完，他给出了那 ...

但我觉得第一题的follow up，两个size 为k的合并取top k，如果用二分做的话就是一道hard题了。。。要求你写出来吗这题？

第一问是维护两个变量, 用来记录最小两个元素的index. 遍历数组, 比较当前值和这两个index对应的元素. 发现更小的元素就更新index.

第二问是第一问的扩展. 使用quick select可以搞定. 不需要额外内存. 时间复杂度是O(kn).

第三问 是divide and conquer的方法做归并.

楼主没作出第二问可能是他们不接受的原因.

simplify 发表于 2017-12-30 12:59
第一问是维护两个变量, 用来记录最小两个元素的index. 遍历数组, 比较当前值和这两个index对应的元素. 发现 ...

针对第二问，第一轮过程感觉有点曲折，其实我一开始说最简单的用一个struct绑定index和value然后扔到priority queue里面，面试官不满意，不让我另建struct…………然后，我记得我是说了我面经里的解法和quick select的思路，之后面试官对我另建一个数组存index然后之后改动数组只改动index的思路不是很清楚，我这块儿和他解释了好久，后来是另外一个面试官看不下去了帮我向他解释的。

我那轮就是由于解释这个index花了不少时间，之后就全在解释那个算法了…………对quick select他们没咋的问。
不过quick select由于只能用On的时间选出第k大的数，这题最终要按顺序返回所有前k小的数，所以最终要对它们排序还要一个klogk。这道题还有要求就是不能修改原数组，所以还得On的空间存index数组。我说的那解法时间复杂度上不是最优的，就是不知道为啥选这个来问我…………

我这轮几乎全程都是和那个口音哥交流，但是沟通不是特别顺畅，感觉有时候你说出一种解法他不算特别满意，这时候你得拼命猜他脑子里想要的什么解法…………

小鱼小玉 发表于 2017-12-30 00:13
但我觉得第一题的follow up，两个size 为k的合并取top k，如果用二分做的话就是一道hard题了。。。要求你 ...

我除了第一题要手写代码，其他都是讲解思路。二个排序数组取topk写起来其实很麻烦的，当时我还心里一惊不会让我手写这个算法吧，那真的没把握完全bug free

luyuzhuangdeyez 发表于 2017-12-29 04:51
大神们想问下这个followup可以用维护一个size为k的Max heap来做么，空间复杂度为O（k）时间复杂度为O（nl ...

用lc的kth largest  number in array quick select方法做，o1 space and on time

hawkingsecond 发表于 2017-12-31 03:45
针对第二问，第一轮过程感觉有点曲折，其实我一开始说最简单的用一个struct绑定index和value然后扔到prio ...

quick select是可以选出前k个最小,不仅仅是第k个. 我觉得比较好的方法有可能是生成一个vector <pair<int, int>> (element, index). 这样就可以对新数组操作.

我觉得如果原数组不能改动的话,就直接用divide and conquer, 把一个大小为k的pq传入, 这样时间复杂度是nlognlogk.

lz第二题双指针是怎么做的?

simplify 发表于 2017-12-31 12:41
lz第二题双指针是怎么做的?

lc上面关于tree有原题，child表示bst中从root开始一直往右子树走的rightmost node，即最大值。parent为child的parent，然后child若有左子树则去左子树的rightmost节点，若没有则parent为第二大的值。

我觉得找到题如果followup一下，就是类似于用stack构建一个tree的iterator，lc上也有原题