10月12号面的onsite, 题目因为太简单, 就挑两个稍微有点难度的说说:
-
LC 原题, merge K sorted arrays, 唯一就是告诉你数据量可能很大, 我用min-heap做的, heap里面存row的pointer或者row id + current position啥的struct都可以, priority queue; 论坛的朋友如果你有效率更高或者速度更快的, 请留下你的算法. (因为被告知是speed/efficiency挂了, 一脸苦笑, 这个理由也是够搞笑的, 我自己做的还真的心里清楚)
-
求一个binary tree 里离一个给定node距离小于K的所有节点的集合, 这个也是简单到想笑, 主要就是创建一个hash table存下parent node, 然后用BFS就好了.
-
system design, recruiter不给别的feedback, 但是明说system design是positive, 所以也没啥好说的, 题目是设计一个service, 供用户查询任何时间段内的数据信息(之前面过类似的, 查询股票信息系统啥的), 难点在于aggregator知不知道, 怎么数据库sharding, cache怎么用, 怎么做分布式, 还有就是要分析和算QPS, 怎么优化存储, retention的处理等等.
还有两轮的题目, 因为实在太简单了, 我都没啥印象了, 就是LC上easy差不多的题.
面完本以为安心等offer, 结果收到邮件被拒, 还不死心给recruitor打了电话, 结果是不透露具体信息, 然后请来年再面. 感觉挺莫名其妙和有点生气的, 因为所有题目基本都是秒杀, 然后面试官时间充分到给我每轮出2-3个题, 还有5-10分钟聊天. 没有任何卡壳或者说hint啥的. system design也是positive, 完全想不通哪里能挂我. 今年果然脸不行 😔.
希望大家有好运拿到心仪的offer
匿了
补充内容 (2018-11-2 01:54):
对不起, 时间写错了, 是10/19面的
补充内容 (2018-11-2 02:19):
别被那个叫 kxace 的人给误导了, 他的复杂度分析是错的, 别因为他面试给弄错了
补充内容 (2018-11-2 22:18):
很多朋友可能没搞清楚题意, 第一题是lintcode上的题目, 是sorted arrays不是linkedlists, 不是链表题, 竟然有O(1)的空间复杂度蹦出来, 请看清楚题目. 另外, 其实面试官有说, 要实时维护一个排序好的输出.
tz38546
(和睦堂主)
2
第一题数据量大的话 比如K很大这样复杂度为 knlog(k*n) k为list个数,n为长度
不如二分两两merge 时间复杂度 k/2 * 2 * n + k / 4 * 4 * n + … + k * n = log(k) * k * n
correct me if i’'m wrong
tz38546
(和睦堂主)
3
BST K nearest neighbors也不是最优
你的算法课真的是白上了…
你额外用一个array 记录index, 请问你找到当前array里最小的element的操作复杂度是多少??不用heap用array, 那你是不是得遍历一下求当前最小值?? 这个复杂度就这样被你吃了?? 你能O(1)找到, 然后current index + 1 ??
留了两条言, 结果最基本的都不会, 还是要多努力啊, 这样是肯定要挂的
999999
(厚德载物)
5
第一题我稍微写一下,用priority queue时间复杂度最优是没有问题的,但反馈中提到了speed / efficiency那就是期望对性能有相当程度的理解。这里的性能并不是纸上谈兵的时间复杂度,而是真正执行时机器所花的时间。
比方说:
(1) 考虑一个"naive"的实现:将所有的array拼接起来先放在output数组中,然后调用std::sort直接in-place排序output数组,比起heap哪个方法快,底层的原理是什么?
这点可能出乎很多人的预料,其实只有在k比较小的时候(例如32以下)或者是元素总数量非常大的情况下(例如100个million以上),heap的实际执行时间才优于"naive"的sort方法。这点楼主可以自己写代码测试一下。
我这边提供一个参考代码,用g++ -std=c++14 -O3 MergeSortedArrays.cpp可以编译:
比如说1024个row,每个row有65536个元素,那么执行结果基本上会显示naive sort比heap merge要快一倍。
当然面试的时候肯定还是写heap代码,但是关键在于,一边写代码,一边要告诉面试官“根据我的经验,这样使用heap的代码只是面试时用用,在实际项目的典型场景下面,性能还不如拼接数组后直接sort,原因在于:(1) heap本身的overhead,(2) 树状结构访问时cache locality方面的问题 (3) sift down/up操作对于CPU branch prediction不友好,等等
(2) 如果使用标准库提供的容器/算法,要分析其不足之处
比如楼主提到了用priority queue,不管是C++和Java,其标准接口只是top()/peek()、pop()/poll()、push()/offer()这三个方法。
然而对于Merge K Sorted Arrays这道题目来说,只使用标准库提供的方法并不是效率最高的,其存在冗余操作:每次从heap中pop一个元素出来,为了维护堆结构会进行一次siftDown;而每次push一个元素,都会进行一次siftUp —— 也就是每merge一个元素需要进行两次时间为log(k)的sift(滚动)操作。但是,如果我们自己去写一个针对这道题目的heap的话,是可以每merge一个元素只进行一次siftDown的。
参考代码也在(1)中所给的文件里,执行后会发现"customized heap"性能是要比标准库priority queue要好的,但是没有快很多 —— 原因在于标准库有很多edge case的优化而这边只是简单写一下 —— 但至少在面试时要提到使用标准库时的这一不足之处。
(3) 即使是简单的题目也有很多拓展知识可以impress面试官 —— 特别是如果你让面试官自己都能学到新的东西的话
还是merge k sorted array这个问题,其实在C++的标准库libstdc++中有多线程实现的代码:
这个代码相当复杂,主要难题在于要将所有k个数组均匀分割(parition)成多段,每一段的元素不相交,参考这篇文章:
https://github.com/jqdocshare/docs/blob/master/multiseq_partition.pdf
以及C++标准库中parallel部分作者讨论并行多路归并排序(Parallel Multiway Mergesort)的ppt,从第11页开始:
楼主,如果是k个array,每个Array长度为n
那么总共需要sort的元素数目为kn
那么用heap sort 时间复杂度应该是kn * log(k*n)吧? (参照heap sort average performance O(nlogn))
空间复杂度,用queue的话是o(k)
您觉得呢?
补充内容 (2018-11-7 09:52):
而且,用heap sort 每个元素都要进heap一次,出heap一次,感觉 时间复杂度应该是kn * log(kn)。
0572C
(豆豆)
7
手机上补充不了,应该还有个就是可以并行进行merge sort
0572C
(豆豆)
8
空间复杂度是priority queue好,不算最后结束占的n,只用k,merge sort需要额外n。如果把最后结果算的空间算上,就是priority queue需要额外k。
时间复杂度啥priority queue是每个数字都要经历一次logk,merge sort 的话并不算每个数字都要logk。理论上有个巨长无比的数组最后合并,只需要n时间。
很久不做算法题了,可能这儿说的不对。但是,逻辑上就是外排序最后用merge sort是有原因的。
我服你的敢说, 张口闭口 discuss里面有, 自己没背下来强行秀一波吗???
这两个月运气差到爆炸, 开了三年的车, lease到期的前一个月被淹了, 引擎全换, 花了1.5W, 艾玛, 所有事情全在这俩月
首先, 面试官是个中国哥们, 面完很开心, 我俩中文聊天的时候给我讲了会给strong positive; 回到你的问题, 为啥不是最优?? DFS要考虑实际应用中会stack overflow.
别的不说, 两两merge的空间复杂度恐怕你就过不去, 题目已经讲了很明确数据量会很大. 不然我直接一个set 就搞定了, 还两两merge啥, O(n)解决
补充内容 (2018-11-2 01:43):
加上insertion的logn, nlogn, 但是空间复杂度是O(n); 这个是面试官明确说了空间复杂度不过
时间我写错了, 是10月19号面的, 昨天给的消息, 11天左右吧