G家电面(已挂)

原帖地址:mitbbs

面试官: 口头叙述的 Merge two sorted list
Me:接口是LinkedList还是Array?
面试官: 每种接口有什么优缺点
Me: 回答这是需求问题,LinkedList不需要临时存储空间
面试官:分析空间复杂度
Me: O(1) and O(n), 继续问需要用什么写Code
面试官:随便
Me: 写了标准实现with class Node {int val, Node next}, merge(Node head1, Node
head2)
面试官:为什么自定义Node class, 不用java.util.LinkedList?
Me: … (这个真没仔细想过,胡乱答的)
面试官:纠缠各种java code 细节 of Node class: public, private, constructor等
Me: 回答以为是主要写算法,可以重写Node class to production ready.
面试官: 不用了,如何实现Merge K sorted list
Me: 可以递归调用Merge two sorted list, 或heap
面试官: 每种实现有什么优缺点,分析复杂度
Me: 分析了复杂度,分享两种都是 N * K * lg(K)
面试官:继续纠缠优缺点,最后提示N很大的情况硬盘读写次数。
Me: 要写code 吗?
面试官: 不需要

面完后我感觉还可以,一周以后悲剧。感觉题虽然简单(5 分钟),问答却很细节,坑
很多,没实际做过大规模merge sort的不容易答圆满。感觉bar 是高了一些。