p******o
发帖数: 4 | 1 面试官： 口头叙述的 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 是高了一些。 | f**********e
发帖数: 288 | 2 貌似runtime说错了， merge k list k*n*logn , heap n * k * logk | e********2
发帖数: 495 | 3 NlogK,
【在 f**********e 的大作中提到】
: 貌似runtime说错了， merge k list k*n*logn , heap n * k * logk
| p******o
发帖数: 4 | 4
澄清一下： N 定义为 size of input list. K 定义为 number of list.
递归调用 merge 2 sorted list: 每次merge N*K records, 递归树深度 lg(K). 所
以我回答 N*K* lg(K)
Heap: heap size K, total N*K records. 也是 N * K * lg(K)
主要问题是在实际应用中 recursive merge 2 sorted 需要多次读写disk. 我一开始回
答说merge K list 可以 code-reuse merge 2 list （本来以为要写code， 已经写了
merge 2 sorted, 写一个新函数就可），但这显然不是他想听到的
【在 e********2 的大作中提到】
: NlogK,
| f**********e
发帖数: 288 | 5 每次merge 应该识nlogn, then n*logn*lgk | e********2
发帖数: 495 | 6 N*K*logK/(memsize/4/integer_size)
了
【在 p******o 的大作中提到】
:
: 澄清一下： N 定义为 size of input list. K 定义为 number of list.
: 递归调用 merge 2 sorted list: 每次merge N*K records, 递归树深度 lg(K). 所
: 以我回答 N*K* lg(K)
: Heap: heap size K, total N*K records. 也是 N * K * lg(K)
: 主要问题是在实际应用中 recursive merge 2 sorted 需要多次读写disk. 我一开始回
: 答说merge K list 可以 code-reuse merge 2 list （本来以为要写code， 已经写了
: merge 2 sorted, 写一个新函数就可），但这显然不是他想听到的
| r*******g
发帖数: 1335 | |
|
