C*7
发帖数: 234 | 1 国女，第一题找n个数中最大的k个，我说用size为k＋1的min heap，放满，然后循环里
不断
poll和add。她觉得结果不对，我就写了下伪码示意（她没让我写代码，我是为了给她
讲明白）
minHeap(k+1)
for(){
heap.poll();
heap.add();
}
她认为不正确，说如果先遇到前k大的结果就不对了（此处我也不知道她在想什么），
我就给她解释＋测试，她又想到别的情况，换各种测试，10多分钟浪费在这，她终于觉
得好像没错。中间我试图给她个台阶，说quick select方法更快，但她完全不理会，继
续纠缠heap的正确性。后来终于跟我说，她想要的解法时size为k的heap，循环里先
peek再根据情况add。如果是讨论复杂度我完全理解，为什么方法不一样就认为是错的
，水平实在很让我吃惊，到最后也没跟我提quick select方法，目测已经超出了她的知
识范围
第二题不知从哪粘过来的，背景还是红色的。。在string末尾添加字符串，使原string
成为回文，返回需要添加的最小string。跟leetcode的Shortest Palindrome差不多，
那题我是一次过的。循环中两种情况：以字母为中心；以字母间隔为中心。她问我为什
么要考虑第二种情况，我是连画图，再举例，她愣是不明白，最后说要回去再想想。
结果给我来个据信。各位不用怀疑我面试中的态度，我是绝对耐心＋各种给台阶说可能
是我没说清
又一次不得不提到烙印，对比实在太明显，前一天推特电面，merge k个iterator of
list，也是用的heap，中间对iterator的操作跟他的要求有点出入，改了一遍，之后给
了onsite |
j*****8
发帖数: 3635 | 2 k size min heap就可以阿，为啥你要用k+1
不过有时候是这样，当你已经有一个预期的答案，而对方给了一个不一样的，有的人会
一时半会反应不过来
【在 C*7 的大作中提到】
: 国女，第一题找n个数中最大的k个，我说用size为k＋1的min heap，放满，然后循环里
: 不断
: poll和add。她觉得结果不对，我就写了下伪码示意（她没让我写代码，我是为了给她
: 讲明白）
: minHeap(k+1)
: for(){
: heap.poll();
: heap.add();
: }
: 她认为不正确，说如果先遇到前k大的结果就不对了（此处我也不知道她在想什么），
|
I*******g
发帖数: 7600 | 3 报上名字来。
【在 C*7 的大作中提到】
: 国女，第一题找n个数中最大的k个，我说用size为k＋1的min heap，放满，然后循环里
: 不断
: poll和add。她觉得结果不对，我就写了下伪码示意（她没让我写代码，我是为了给她
: 讲明白）
: minHeap(k+1)
: for(){
: heap.poll();
: heap.add();
: }
: 她认为不正确，说如果先遇到前k大的结果就不对了（此处我也不知道她在想什么），
|
C*7
发帖数: 234 | 4 k＋1在循环里很好写，比较直观的想到的，她要是说space用多了或者不是最优解，我
完全理解，可是时间都浪费在验证正确性上了。这么简单的操作，还非要我一个数一个
数的演示，演示了至少5个test case她才放心，简直把我雷翻了
【在 j*****8 的大作中提到】
: k size min heap就可以阿，为啥你要用k+1
: 不过有时候是这样，当你已经有一个预期的答案，而对方给了一个不一样的，有的人会
: 一时半会反应不过来
|
C*7
发帖数: 234 | 5 电话一开始说了个名字，没记住，我倒是也很想找她聊一聊
【在 I*******g 的大作中提到】
: 报上名字来。
|
m*****n
发帖数: 204 | 6 你这个是不对吧，需要先add()后poll(). 试试K＝1，输入3，2，1，你的结果是1.
【在 C*7 的大作中提到】
: 国女，第一题找n个数中最大的k个，我说用size为k＋1的min heap，放满，然后循环里
: 不断
: poll和add。她觉得结果不对，我就写了下伪码示意（她没让我写代码，我是为了给她
: 讲明白）
: minHeap(k+1)
: for(){
: heap.poll();
: heap.add();
: }
: 她认为不正确，说如果先遇到前k大的结果就不对了（此处我也不知道她在想什么），
|
C*7
发帖数: 234 | 7 是，我省略了先把heap放满，电话里说了，她也不是对这块有质疑
【在 m*****n 的大作中提到】
: 你这个是不对吧，需要先add()后poll(). 试试K＝1，输入3，2，1，你的结果是1.
|
m*****n
发帖数: 204 | 8 我也错了，她说的先比再加才是对的。
【在 m*****n 的大作中提到】
: 你这个是不对吧，需要先add()后poll(). 试试K＝1，输入3，2，1，你的结果是1.
|
s*****r
发帖数: 43070 | 9 打算聊啥
【在 C*7 的大作中提到】
: 电话一开始说了个名字，没记住，我倒是也很想找她聊一聊
|
C*7
发帖数: 234 | 10 问问为什么不给过，第二题想明白没有
【在 s*****r 的大作中提到】
: 打算聊啥
|
|
|
s*****r
发帖数: 43070 | 11 heap不是先比再加吗，也许LZ的heap比较特殊，反正俺没看懂他的pseudo code
【在 m*****n 的大作中提到】
: 我也错了，她说的先比再加才是对的。
|
j*****8
发帖数: 3635 | 12 对，那个国女的是对的
本来就是k size heap，每次先和peek 比较，然后再插入或者discard
【在 m*****n 的大作中提到】
: 我也错了，她说的先比再加才是对的。
|
C*7
发帖数: 234 | 13 是，我同意这解法正确。我的解法在哪里会有错？她最后也同意我解法没错，她给的测
试都没问题
【在 j*****8 的大作中提到】
: 对，那个国女的是对的
: 本来就是k size heap，每次先和peek 比较，然后再插入或者discard
|
b**********5
发帖数: 7881 | 14 傻逼。 自己好好再去想想。 K+1就不用peek， 再compare， 再决定嫁不嫁。。。
【在 s*****r 的大作中提到】
: heap不是先比再加吗，也许LZ的heap比较特殊，反正俺没看懂他的pseudo code
|
s*****r
发帖数: 43070 | 15 晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
俺大概知道为啥被据了
【在 b**********5 的大作中提到】
: 傻逼。 自己好好再去想想。 K+1就不用peek， 再compare， 再决定嫁不嫁。。。
|
b**********5
发帖数: 7881 | 16 你傻逼啊， k和K+1， 滚他妈的一边去！！！！ 还有， 你认为这个heap是存在哪里的
？？！！
【在 s*****r 的大作中提到】
: 晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
: 俺大概知道为啥被据了
|
C*7
发帖数: 234 | 17 汗，她给我讲了她的方法以后，我给她分析了两种复杂度，她的在某些情况下更好一些
，如果早讨论复杂度，我也不是不能想到她的方法。再说有quick select快吗？
【在 s*****r 的大作中提到】
: 晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
: 俺大概知道为啥被据了
|
s*****r
发帖数: 43070 | 18 他的code还是有bug，第K+1个数不比就踢走，然后去比K和K-1
【在 b**********5 的大作中提到】
: 你傻逼啊， k和K+1， 滚他妈的一边去！！！！ 还有， 你认为这个heap是存在哪里的
: ？？！！
|
b**********5
发帖数: 7881 | 19 我觉得你和那个中国女面试官， 有一比， 估计更蠢。。。
【在 s*****r 的大作中提到】
: 他的code还是有bug，第K+1个数不比就踢走，然后去比K和K-1
|
s*****r
发帖数: 43070 | 20 你再认真想想，别光发泄
【在 b**********5 的大作中提到】
: 我觉得你和那个中国女面试官， 有一比， 估计更蠢。。。
|
|
|
C*7
发帖数: 234 | 21 莫非heap是靠手动排序的？
【在 s*****r 的大作中提到】
: 他的code还是有bug，第K+1个数不比就踢走，然后去比K和K-1
|
s*****r
发帖数: 43070 | 22 child node无序，需要比较两次才能决定谁是最小的
【在 C*7 的大作中提到】
: 莫非heap是靠手动排序的？
|
f**********e
发帖数: 288 | 23 不管怎么样， 总要给第二个电面麻。。太无情了。。 |
C*7
发帖数: 234 | 24 peek和poll都是取heap里最小值，只是决定插入不插入的区别，比较两次是什么意思
【在 s*****r 的大作中提到】
: child node无序，需要比较两次才能决定谁是最小的
|
l****3
发帖数: 3 | 25 。。。半瓶醋可以不发言，但是最好不要乱发言
【在 s*****r 的大作中提到】
: 晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
: 俺大概知道为啥被据了
|
l****3
发帖数: 3 | 26 size k 的heap和size k+1的heap，空间复杂度是一样的，你的方法没有问题。如果她
说你的方法空间复杂度不如她的，那就只能呵呵了，遇到这样的不懂装懂的，你也没有
办法
【在 C*7 的大作中提到】
: 汗，她给我讲了她的方法以后，我给她分析了两种复杂度，她的在某些情况下更好一些
: ，如果早讨论复杂度，我也不是不能想到她的方法。再说有quick select快吗？
|
s*****r
发帖数: 43070 | 27 你个二货，知道heap.add()怎么写吗，你要能写出来，就知道为啥会fail他
【在 l****3 的大作中提到】
: 。。。半瓶醋可以不发言，但是最好不要乱发言
|
C*7
发帖数: 234 | 28 poll包含siftdown，add包含siftup，你想说啥到底
【在 s*****r 的大作中提到】
: 你个二货，知道heap.add()怎么写吗，你要能写出来，就知道为啥会fail他
|
b**********5
发帖数: 7881 | 29 你是new cop？ 这个switsuer屁都不懂的， 你跟它去纠结？！ 我狗儿子放的屁， 都
要比他的帖子有营养
【在 C*7 的大作中提到】
: poll包含siftdown，add包含siftup，你想说啥到底
|
C*7
发帖数: 234 | 30 哈哈，我这不是想看看他是咋误解的，仿佛回到了面试当天
【在 b**********5 的大作中提到】
: 你是new cop？ 这个switsuer屁都不懂的， 你跟它去纠结？！ 我狗儿子放的屁， 都
: 要比他的帖子有营养
|
|
|
C*7
发帖数: 234 | 31 我知道你咋想的了，你是不是认为pq初始化的时候还没有排序，第一个poll取不到最小
值？但initialize pq都是一个一个add进去的，莫非能快捷无序初始化？
【在 s*****r 的大作中提到】
: 你个二货，知道heap.add()怎么写吗，你要能写出来，就知道为啥会fail他
|
L*********s
发帖数: 3063 | 32 大家为什么都用min heap呢？
min heap时间复杂度是 O(n*log k) = O (log(k^n)) 啊
用max heap的话时间复杂度是 O(n+ k*log n) = O(n+ log(n^k)) 啊
你们不知道 k^n 一般远大于 n^k吗？所以用max heap更快啊
另外Frederickson有一篇文章说用max heap可以达到O(n+k*log k).
http://www.sciencedirect.com/science/article/pii/S0890540183710
(文章中是求n个数中最小的k个，所以文章中用min heap, 如果是求最大的k个就用max
heap) |
C*7
发帖数: 234 | 33 会不会n太大放不下。这个题给了n大约在几十万，k大约在几千，但讨论中没提到
max
【在 L*********s 的大作中提到】
: 大家为什么都用min heap呢？
: min heap时间复杂度是 O(n*log k) = O (log(k^n)) 啊
: 用max heap的话时间复杂度是 O(n+ k*log n) = O(n+ log(n^k)) 啊
: 你们不知道 k^n 一般远大于 n^k吗？所以用max heap更快啊
: 另外Frederickson有一篇文章说用max heap可以达到O(n+k*log k).
: http://www.sciencedirect.com/science/article/pii/S0890540183710
: (文章中是求n个数中最小的k个，所以文章中用min heap, 如果是求最大的k个就用max
: heap)
|
w*****1
发帖数: 6807 | 34 说说我的见解，估计纠结在第一个题，因为我个人认为很可能是面试官想考你的东西没
考出来，所有最后导致“被黑”
从面试的过程来看，她好像不需要你写代码。那么她想要的考的大概是想看看你都知道
有多少种方法(至少3种吧，多多益善)可以做出来，然后再问问每种方法的复杂度，她
的本意并不是想纠结于具体的代码。可能最后不知道怎么就聊到具体的代码然后去
argue了。如果回答的时候先问问这些，可能结果会好很多。
不过说实话，面试的时候哪能想这么多。LZ有实力，肯定能找到好工作。 |
L*********s
发帖数: 3063 | 35 嗯有道理，如果n是非常非常大的stream，确实只能用min stack
【在 C*7 的大作中提到】
: 会不会n太大放不下。这个题给了n大约在几十万，k大约在几千，但讨论中没提到
:
: max
|
l********g
发帖数: 35 | 36 我觉得楼主的算法是正确的，不过复杂度比k size的要高一些，特别是遇到前k是最大
的情况，做了很多无用的add和poll。 |
h******k
发帖数: 13418 | 37 这贴就是胡扯了。
【在 s*****r 的大作中提到】
: 晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
: 俺大概知道为啥被据了
|
L*********s
发帖数: 3063 | 38 你这是拿k+1的worst case和k比
两个算法average复杂度，各自worst case复杂度都是同样量级，差别很小
楼主的算法也完全正确
【在 l********g 的大作中提到】
: 我觉得楼主的算法是正确的，不过复杂度比k size的要高一些，特别是遇到前k是最大
: 的情况，做了很多无用的add和poll。
|
xt
发帖数: 17532 | 39 为什么不用partition来做呢？
【在 C*7 的大作中提到】
: 国女，第一题找n个数中最大的k个，我说用size为k＋1的min heap，放满，然后循环里
: 不断
: poll和add。她觉得结果不对，我就写了下伪码示意（她没让我写代码，我是为了给她
: 讲明白）
: minHeap(k+1)
: for(){
: heap.poll();
: heap.add();
: }
: 她认为不正确，说如果先遇到前k大的结果就不对了（此处我也不知道她在想什么），
|
l********g
发帖数: 35 | 40 我同意，但是对于任何的case, K size的算法都一定不会比k+1的差，这就是区别。
【在 L*********s 的大作中提到】
: 你这是拿k+1的worst case和k比
: 两个算法average复杂度，各自worst case复杂度都是同样量级，差别很小
: 楼主的算法也完全正确
|
|
|
L*********s
发帖数: 3063 | 41 不一定吧，在前k+1个数是最大的情况下，K size就比k+1 size的差.比如
n=9, k=5,
输入[4,5,6,7,8,9,1,2,3]
【在 l********g 的大作中提到】
: 我同意，但是对于任何的case, K size的算法都一定不会比k+1的差，这就是区别。
|
p****6
发帖数: 724 | 42 这话都敢说
[在 swjtuer (灌水和coding都要敲键盘) 的大作中提到：]
：晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
：
：........... |
T****U
发帖数: 3344 | 43 纠结速度和空间优化的话，这题最优是quick select, lz了然于心
max
【在 L*********s 的大作中提到】
: 大家为什么都用min heap呢？
: min heap时间复杂度是 O(n*log k) = O (log(k^n)) 啊
: 用max heap的话时间复杂度是 O(n+ k*log n) = O(n+ log(n^k)) 啊
: 你们不知道 k^n 一般远大于 n^k吗？所以用max heap更快啊
: 另外Frederickson有一篇文章说用max heap可以达到O(n+k*log k).
: http://www.sciencedirect.com/science/article/pii/S0890540183710
: (文章中是求n个数中最小的k个，所以文章中用min heap, 如果是求最大的k个就用max
: heap)
|
l*****i
发帖数: 13 | 44 能
长度n的数组建堆是O(n), 从空堆一个一个加进去是nlogn
【在 C*7 的大作中提到】
: 我知道你咋想的了，你是不是认为pq初始化的时候还没有排序，第一个poll取不到最小
: 值？但initialize pq都是一个一个add进去的，莫非能快捷无序初始化？
|
f**********n
发帖数: 258 | 45 k=2
input={2 1 4 3}
k+1=3
minHeap(k+1)={4 3 2}
for(){
heap.poll(); // 2 is pop out so the minHeap becomes {4 3}
heap.add(); // 1 is add to minHeap so it becomes {4 3 1}
}
the heap still needs to pop out the top min to become correct result {4 3}. |
h******k
发帖数: 13418 | 46 是哦，如果LZ的态度方面没什么问题，应该再给个机会
【在 f**********e 的大作中提到】
: 不管怎么样， 总要给第二个电面麻。。太无情了。。
|
w**2
发帖数: 29 | 47 当时没明白别人的算法，事后想想总该明白了。国女怎么样都该给个机会。
【在 h******k 的大作中提到】
: 是哦，如果LZ的态度方面没什么问题，应该再给个机会
|
l******s
发帖数: 3045 | 48 国女本来就想安安静静地考个quick sort交差，你们给人家出难题，这事闹的。
前两天哥面试一家，题目写hashtable，哥选了prime number做array的长度，阿三实在
不明白为什么，哥于是老老实实改成2000，皆大欢喜。不过阿三反应很快，上网搜了一
下马上说我说得对。总之，面试就低调点，别呛火。
【在 w**2 的大作中提到】
: 当时没明白别人的算法，事后想想总该明白了。国女怎么样都该给个机会。
|
