p*****e
发帖数: 537 | 1 电面：
第一次：印男，implement string matching and replacing
第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
onsite:
第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
第二轮：印男加国男，given a stream of data and a sliding window, implement
put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
第三轮: 吃饭
第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
个中年老印加一个中年国男，国男shadow。老印一出现就是一幅超鄙夷超不屑的臭脸。
出了一个inverted index的题，就是有一大堆doc，对doc里出现的word建inverted
index，doc很多所以是distribute在很多machine上的，问怎么实现这个inverted
index。我听了题目暗爽，这种题我准备的很充分啊！因为这题有很多解法，我就从差
到好一一说来，每个都说了为啥不好，然后引出我认为最好的那一个。可是我每说一个
老印就急吼吼的跳起来反驳我。搞了两回，我意识到可能老印就是想听最佳答案，我就
解释说我只是想list一下所有的option，我也问他你是不是prefer直接告诉你最佳答案
？他说是。我就直接给了我认为的最佳答案。
接下来还有几个相关的小问题我都忘了，有一个是关于map reduce的。最后一个，是找
出前K个最常用的word。我说用min heap找出每个machine的K个最常见word，再用一个
min heap merge这些list。奇葩的事情就出现了，老印跳出来说，不对，你用min heap
是不对的，应该用max heap！这时国男也一脸诚恳的“提醒”我说：是的，你用min
heap找出来的是最不常用的K个word哦！我我我，我当场就愣了！不会吧，俩linkedin
的老员工了，好歹是个面试官啊，居然连min heap和max heap是啥都不知道？愣了两秒
，我就给他们讲了一遍啥是min heap啥是max heap，和为啥找K个最常用的word要用min
heap而不是max heap。一遍讲我一边想：我这是来面试的还是来给linkedin的员工培
训基本data structure的？最后俩人还是将信将疑，又问了一个有关于thread的小问题
就结束了。
第五轮：小印女加小印男，也是问了一个类似在stream里找k个最大数的题，我还是用
了min heap，还好俩人都知道啥是min heap，也比较认同我的做法。然后大部分的时间
都在讨论multi threading的实现，我提到了read write lock，和三种fairness
policy，不过他俩都是一脸茫然，好像他们只知道read write lock，但不知道
fairness这回事，挺奇怪的。（另：刚又想起，这一轮还问了max point on a line一
题，leetcode上有，只要求pseudo code，我做了个square的，问小印男还有没有更快
的，他说就他所知没有了）。
第六轮：亚裔男（不是国男）加印男，问了romanToInt和intToRoman的题，intToRoman
和leetcode一样，但romanToInt要考虑很多corner case。这些corner case在leetcode
和EPI上都没有提到过。另外，好像EPI上的解法很多错误，我没看几道题就已经找出很
多错了，有的错的很离谱，大家得注意一下。
第七轮：白男加国女，问了一个design的题，design monitoring system，自我感觉是
发挥的最好的一轮。
面完以后我就觉得，成败就在第四轮，最后果然就跪在了这一轮。不过我是一点遗憾都
没有，要是给了我offer，让我去和对我天生有敌意的老印，还有分不清min heap和max
heap的人一起共事，其实也不是什么好事。还有我觉得好几个问道我multithreading
问题的人，本身对multithreading也不是很熟，像那个read write lock fairness
policy的问题，还有lock free algo的ABA问题，他们好像都不知道，那他们平时是咋
把multithreading的程序写对的啊？
所以我现在挺疑惑的：是不是我特别倒霉，碰上的都是linkedin里水平比较低的一些人
，还是linkedin的员工水平并不像原本我想的那么高？ |
w****r
发帖数: 15252 | 2 7个面试，疯了
我这个工作就电面 onsite两次就完了
大公司就是牛逼啊 |
t***t
发帖数: 6066 | 3 some guys are lucky and joined linkedin early when it's nothing. so people
from schools like santa cruz university joined and their level is pretty low
. |
n*******1
发帖数: 145 | 4 max-heap min-heap各有利弊吧 一个time n space n 一个time nlogk space k 说清楚
就行了吧 |
l*********8
发帖数: 4642 | 5 max heap, min heap这个是比较奇葩。 如果是面试者犯这种错误，提醒后不能马上反
应过来的话，估计要挂了。 |
p*****e
发帖数: 537 | 6 咋用max heap找k个最大的数 in time O(n) space O(n)? 展开说说？
【在 n*******1 的大作中提到】
: max-heap min-heap各有利弊吧 一个time n space n 一个time nlogk space k 说清楚
: 就行了吧
|
q********c
发帖数: 1774 | 7 赞一个，你的水平肯定没问题。请问你是面的那个组，是applications
team还是infrastructure?
另，heap那道题应该用max heap, 因为频率高的都保留在heap里面了。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l****i
发帖数: 2772 | 8 min heap才是保存频率高的k个
【在 q********c 的大作中提到】
: 赞一个，你的水平肯定没问题。请问你是面的那个组，是applications
: team还是infrastructure?
: 另，heap那道题应该用max heap, 因为频率高的都保留在heap里面了。
:
: 情况
|
o***g
发帖数: 2784 | 9 大牛，给我讲讲啥事min heap啥是max heap呗
为啥这里需要用min heap，不能用max heap呢？
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l****r
发帖数: 118 | 10 每次比较替换最小（不常用）的root啊。只需维护size k的 min heap.
用max heap的话得用所有词建了，size n，然后取max K次。
【在 q********c 的大作中提到】
: 赞一个，你的水平肯定没问题。请问你是面的那个组，是applications
: team还是infrastructure?
: 另，heap那道题应该用max heap, 因为频率高的都保留在heap里面了。
:
: 情况
|
|
|
n**n
发帖数: 626 | 11 http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-a
both are fine.
【在 p*****e 的大作中提到】
: 咋用max heap找k个最大的数 in time O(n) space O(n)? 展开说说？
|
a******f
发帖数: 9 | |
m*****l
发帖数: 95 | |
p**i
发帖数: 22 | 14 哪位大牛能讲讲第二轮：印男加国男，given a stream of data and a sliding
window, implement put(), getAverage()。考虑multithreading的情况。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l******i
发帖数: 880 | 15 面试官应该没错，如果n相对于k很大，我感觉还是用max heap比较好。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l******6
发帖数: 340 | 16 看来怪不得linkedIn面试官 不少版友都支持max heap ........ |
G*****n
发帖数: 19 | 17 赞楼主 鄙视第四轮
请问楼主你说
"但romanToInt要考虑很多corner case"
是什么意思呢？
你是指 IV IX 这种情况吗？
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l****i
发帖数: 2772 | 18 详细解释听听？
【在 l******i 的大作中提到】
: 面试官应该没错，如果n相对于k很大，我感觉还是用max heap比较好。
:
: 情况
|
o********t
发帖数: 1655 | 19 投诉那个阿三，这个不投诉就太软弱了
不去也不能让他好过了。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
t***t
发帖数: 6066 | 20 should use min-heap.
sign, so many here as clueless as the a3 interviewer.
【在 l******i 的大作中提到】
: 面试官应该没错，如果n相对于k很大，我感觉还是用max heap比较好。
:
: 情况
|
|
|
p*****e
发帖数: 537 | 21 我要是投诉阿三，岂不是连国男也一起投诉了？他也说用min heap不对来着
【在 o********t 的大作中提到】
: 投诉那个阿三，这个不投诉就太软弱了
: 不去也不能让他好过了。
:
: 情况
|
o********t
发帖数: 1655 | 22 你可以只投诉阿三啊。怎么一根筋。。。
我发现你们码农的思维太过程序化。被两个人刁难了谁规定只能投诉两个人否则不能投
诉？
【在 p*****e 的大作中提到】
: 我要是投诉阿三，岂不是连国男也一起投诉了？他也说用min heap不对来着
|
p**o
发帖数: 3409 | 23 http://hg.python.org/cpython/file/2.7/Lib/heapq.py
参考python标准库的nlargest()算法（第221行），
就是用一个大小为n的min-heap；
同理，nsmallest()应该用max-heap来求。
【在 o***g 的大作中提到】
: 大牛，给我讲讲啥事min heap啥是max heap呗
: 为啥这里需要用min heap，不能用max heap呢？
:
: 情况
|
p*****e
发帖数: 537 | |
l****r
发帖数: 118 | 25 投诉他的态度啊，你总不能投诉他不懂该用min heap吧
【在 p*****e 的大作中提到】
: 我要是投诉阿三，岂不是连国男也一起投诉了？他也说用min heap不对来着
|
p*****e
发帖数: 537 | 26 怎么投诉他态度？说他啥都没说就对我一脸鄙夷？他可以解释说他天生就是一副臭脸，
对他老板都一样。投诉他我每说一句话他都跳起来反驳？他可以解释说是
miscommunication，说他不想听我给他分析其他方法的缺点，只想听最佳答案。
我不觉得我complain会对最终结果有任何的改变，不过我确实和recruiter交流过这些
concern，当然是比较委婉的表达方式。
不过版上有xdjm要面LinkedIn，我可以告诉你们这俩人的名字，你们可以提防一点。
【在 l****r 的大作中提到】
: 投诉他的态度啊，你总不能投诉他不懂该用min heap吧
|
o********t
发帖数: 1655 | 27 不是为了改变结果，是为了你自己出口气，二是打击一下烙印的嚣张气焰，对后面的同
胞有利
【在 p*****e 的大作中提到】
: 怎么投诉他态度？说他啥都没说就对我一脸鄙夷？他可以解释说他天生就是一副臭脸，
: 对他老板都一样。投诉他我每说一句话他都跳起来反驳？他可以解释说是
: miscommunication，说他不想听我给他分析其他方法的缺点，只想听最佳答案。
: 我不觉得我complain会对最终结果有任何的改变，不过我确实和recruiter交流过这些
: concern，当然是比较委婉的表达方式。
: 不过版上有xdjm要面LinkedIn，我可以告诉你们这俩人的名字，你们可以提防一点。
|
p*****e
发帖数: 537 | 28 其实比起那个阿三来，我对那个国男更觉得惋惜。本来LinkedIn面试安排一个shadow，
就是为了做做笔记啊，大家有分歧的时候可以做个补充啊啥的。阿三很水很笨这不是很
正常么？但国男也是这么水么？在阿三刁难我的时候他也啥都不说啥都不做，他那个
shadow真的只是个shadow而已啊！ |
p*****e
发帖数: 537 | 29 我明白你的好意，不过我真的不生气，就像我帖子里写的，和这样的人共事不一定是件
好事，所以他们据我对我来说也不是一件坏事，所以我没啥生气没啥惋惜的。
至于对后面的同胞而言，我面完的第二天recruiter来收集面试意见，我就委婉的和他
提过这些concern，相信他应该明白是怎么回事了。
【在 o********t 的大作中提到】
: 不是为了改变结果，是为了你自己出口气，二是打击一下烙印的嚣张气焰，对后面的同
: 胞有利
|
l****r
发帖数: 118 | 30 我前几年面过一次公司，当时有一个interviewer态度不好，经常打断我的话，然后用
很多带着不屑的反问，我面完了立马向HR投诉了他。然后HR和我道歉，说他那个人确实
有问题，以前也被其他人投诉过。结果完了一样给我发了offer。
投诉不是打官司，不需要证据，一个反馈而已。
【在 p*****e 的大作中提到】
: 怎么投诉他态度？说他啥都没说就对我一脸鄙夷？他可以解释说他天生就是一副臭脸，
: 对他老板都一样。投诉他我每说一句话他都跳起来反驳？他可以解释说是
: miscommunication，说他不想听我给他分析其他方法的缺点，只想听最佳答案。
: 我不觉得我complain会对最终结果有任何的改变，不过我确实和recruiter交流过这些
: concern，当然是比较委婉的表达方式。
: 不过版上有xdjm要面LinkedIn，我可以告诉你们这俩人的名字，你们可以提防一点。
|
|
|
p**i
发帖数: 22 | 31 哪位大牛能讲讲第二轮：印男加国男，given a stream of data and a sliding
window, implement put(), getAverage()。考虑multithreading的情况。 |
c**********8
发帖数: 1052 | 32 楼主水平好强，那些design，多线程什么的其实感觉最能区分出candidate的水平，
algo啥只的是基础
我曾经在M有一轮也是我说一句，后面三句等着我，连续打断我几次，就算我思路不对
，就让我改就行了，那人还要说好几句类比（真的是用非技术的例子类比）说我为什么
不对。在一个地方卡了好几分钟，其实明明不是思路不对，是没听我说完。
楼主加油
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
p********n
发帖数: 165 | 33 max heap 有max heap的做法
min heap 有min heap的做法，最终复杂度差不多，决定于k 和n的关系。。。
光刷leetcode是不行的。 |
m*****n
发帖数: 2152 | 34 既然是用map reduce，n应该很大很大，要考虑momery不足的情况，用min heap节省空
间。
多出logk的时间复杂度应该没什么。
L家这么水，估计楼主是因为太强了，被拒的。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
r****7
发帖数: 2282 | 35 本版硬说max heap可以做的都是为了显得自己高明或者为了显得自己和L家比较近么。
。。
这个用max heap做还不如说排序呢。
BTW，我觉得你好强，是平时接触分布式和多线程就很多吗？
time
【在 p*****e 的大作中提到】
: 我明白你的好意，不过我真的不生气，就像我帖子里写的，和这样的人共事不一定是件
: 好事，所以他们据我对我来说也不是一件坏事，所以我没啥生气没啥惋惜的。
: 至于对后面的同胞而言，我面完的第二天recruiter来收集面试意见，我就委婉的和他
: 提过这些concern，相信他应该明白是怎么回事了。
|
p*****e
发帖数: 537 | 36 我是菜鸟我知道...我要是很强估计其他的interviewer也会保我了...
【在 m*****n 的大作中提到】
: 既然是用map reduce，n应该很大很大，要考虑momery不足的情况，用min heap节省空
: 间。
: 多出logk的时间复杂度应该没什么。
: L家这么水，估计楼主是因为太强了，被拒的。
:
: 情况
|
m*****n
发帖数: 2152 | 37 其他nlog(n)排序方法要额外空间，就heap不要。
【在 r****7 的大作中提到】
: 本版硬说max heap可以做的都是为了显得自己高明或者为了显得自己和L家比较近么。
: 。。
: 这个用max heap做还不如说排序呢。
: BTW，我觉得你好强，是平时接触分布式和多线程就很多吗？
:
: time
|
m*****n
发帖数: 2152 | 38 有个词叫over qualify，如果水平远超同事甚至是manager，对group团结没好处。而且
，说不定会担心招来了，马上又跳槽。
【在 p*****e 的大作中提到】
: 我是菜鸟我知道...我要是很强估计其他的interviewer也会保我了...
|
e********r
发帖数: 24 | 39 are you serious?
【在 m*****n 的大作中提到】
: 其他nlog(n)排序方法要额外空间，就heap不要。
|
e********r
发帖数: 24 | |
|
|
w*****c
发帖数: 7276 | |
o***g
发帖数: 2784 | 42 我觉得今天HM写的那个就是给你写的，人家没好意思直接在你主题下写
从你的文章中感觉出来你已经很牛了
【在 p*****e 的大作中提到】
: 我是菜鸟我知道...我要是很强估计其他的interviewer也会保我了...
|
p*****e
发帖数: 537 | 43 恩，看了HM写的那个，觉得很中肯。其实我也没觉得我被黑了，不过recruiter很明确
的告诉了我主要问题就是在那一轮，所以我也很想知道我的问题到底出在哪儿了？
而且我在面试的时候是很注意要表现的humble一些的，所以虽然那个老印一开始总是跳
出来说我说的不对，我也就是很平静的问他你是不是prefer一个optimal的solution就
ok了，他说是，我给了他我认为的optimal solution，后来他也安生了一阵子，直到那
个min heap/max heap的问题出现。
【在 o***g 的大作中提到】
: 我觉得今天HM写的那个就是给你写的，人家没好意思直接在你主题下写
: 从你的文章中感觉出来你已经很牛了
|
t********e
发帖数: 1169 | |
g****t
发帖数: 2751 | 45 尼玛一个破找工作的网站，尼玛整那么多画画肠子的程序有个屁用 |
z*******3
发帖数: 13709 | 46 是应该用min heap，因为pop出来的是min而不是max
但是你的答题没有觉察出对方的意图
stream那个，用concurrenthashmap
考官三番五次提醒threading也是想听到你说这个东西
这个其实就是考jdk1.5的new feature，core java的基本功
楼主的java经验也不丰富
所以多数时候说的是书本上的东西，比如读写锁这些
不match也正常，工作和理论还是有距离的
如果google面，用python的话，估计楼主就过了 |
z*******3
发帖数: 13709 | 47 不过min heap还是max heap真心不重要
你就是做成min&max heap又怎样？两头都能pop就好了
能pop最小也能pop最大的，反正insert效率都是一样的
这只是定义，对方的理解是把min想成你存最小值了
就象空穴来风，明明文字上意思是言之有据
但是无数人认为这个是扯蛋的意思
纠结这个就有些书呆了，无所谓，互相理解一下
如果你想结合理论的话，pirorityqueue就是基于heap的实现
这个是我从swjtuer那边偷来的
多线程对方考点还真的不是fairness strategy
对方其实目的很简单，就想知道你知道不知道最常用的core java类是什么
inverted index那题估计也不是纯粹考理论，应该是希望看到类似半海那种答案
半海遇到过类似的问题，问的是distributed lock
半海答案很简单，用zookeeper
就过了 |
z*******3
发帖数: 13709 | 48 面试次数多说明l家内部要不要楼主有争议
所以补了几个
楼主的解决方案不能说是错的
但是毕竟工作中比较少这么做
l家估计认为楼主有潜力，值得培养
就看内部人愿意不愿意培养了
【在 w****r 的大作中提到】
: 7个面试，疯了
: 我这个工作就电面 onsite两次就完了
: 大公司就是牛逼啊
|
z*******3
发帖数: 13709 | 49 楼主说的min heap是data structure里面的min heap
data structure里面所谓的min heap有特殊的定义，min指的是root
但是面试官说的max heap意思是max value的heap（包括min&max heap)
max说的是values，而不是root
严格说来，是max values的min heap
我神经快错乱了
这种题目其实深入下去很恶心，红黑树就在后面，如果说treemap的，要小心点
http://my.oschina.net/leejun2005/blog/135085
【在 p**o 的大作中提到】
: http://hg.python.org/cpython/file/2.7/Lib/heapq.py
: 参考python标准库的nlargest()算法（第221行），
: 就是用一个大小为n的min-heap；
: 同理，nsmallest()应该用max-heap来求。
|
z*******3
发帖数: 13709 | 50 看别人博客上说
楼主用的min heap其实就是treemap的方式
其开销要大于priorityqueue |
|
|
z*******3
发帖数: 13709 | |
z*******3
发帖数: 13709 | 52 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
s*****r
发帖数: 43070 | 53 烙印的态度有问题
LZ回答问题也有些动车洗车，这样会让面试官反感，在一个问题上不要耽误太多时间。
国人表达能力一般比较弱，说太多容易让人犯晕，会被认为没有思路。表达能力强的可
以多解释，多动车洗车，很多老美烙印喜欢这样。 |
z*******3
发帖数: 13709 | 54 priority queue的add和remove实现你看懂了没？
我看得晕头转向的
看懂了，插入删除都有讲究，光min heap是不够的
priority queue是王道，洗澡去了
【在 s*****r 的大作中提到】
: 烙印的态度有问题
: LZ回答问题也有些动车洗车，这样会让面试官反感，在一个问题上不要耽误太多时间。
: 国人表达能力一般比较弱，说太多容易让人犯晕，会被认为没有思路。表达能力强的可
: 以多解释，多动车洗车，很多老美烙印喜欢这样。
|
k******e
发帖数: 19 | 55
情况
你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
TOP K的问题。
- 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
的就REPLACE ROOT，然后将其 SIFT DOWN。
－ 用MAXHEAP的话，空间复杂度是O（N）， 时间复杂度是 O（KlogN）。
这个办法只能用在N不是太大的时候，可以先HEAPIFY，用时O（N）。现在你的ROOT
是最大的，把ROOT拿掉放进你的RESULT里，你的HEAP的ROOT空了，把最后一个元素放进
ROOT，SIFT DOWN， 又得到一个MAXHEAP，重复刚才的操作K次，得到你的RESULT.
两种方法都没错，而且也不一定哪个就更好，就算光是看时间复杂度，NlogK和KlogN哪
个好也要看你的K和N是多大。
你在面试的时候试图教育面试官，这个不管到哪你都会碰壁的（不是要为那个臭脸阿三
辩护，臭脸阿三最惹人厌）。我有个朋友最近面试失败就是败在没有跟着面试官的思路
走，任何HINT都不愿意TAKE，一味地按照自己的思路走。你想想，如果你是面试官，你
试图提出一些HINT，对方全部不听，你会不会觉得对方有些ARROGANT？
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
k******e
发帖数: 19 | 56 这个解释得很清楚了：
http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
【在 k******e 的大作中提到】
:
: 情况
: 你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
: 这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
: TOP K的问题。
: - 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
: 这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
: 就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
: 后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
: 的就REPLACE ROOT，然后将其 SIFT DOWN。
|
s*****r
发帖数: 43070 | 57 都是general hiring，面试官都是临时拼凑的，没有group团结这一说
【在 m*****n 的大作中提到】
: 有个词叫over qualify，如果水平远超同事甚至是manager，对group团结没好处。而且
: ，说不定会担心招来了，马上又跳槽。
|
s*****r
发帖数: 43070 | 58 公正的评论一下，L家的项目还是很有趣的，能学到不少东西，不少项目都是full
stack，要负责前段，后端，data modeling，大型网站的数据流程，数据分析，每个项
目只有一两个人去做，亚历山大。适合刚毕业的小码农，不适合喜欢混日子的老码农。
吐槽活累事多钱少，股价很蛋疼
超级赞美食堂的饭菜质量，很多菜比外面的餐馆都强，年底的shutdown相当于放长假。
【在 g****t 的大作中提到】
: 尼玛一个破找工作的网站，尼玛整那么多画画肠子的程序有个屁用
|
s**x
发帖数: 7506 | 59
I am surprised max heap is even an option here.
My only explanation is people get confused by min max heap.
I never liked linkedin. Good luck with 楼主，take it easy and bless.
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
z*******3
发帖数: 13709 | 60 re这个
这句话可以证明他们其实想的不是定以上的min/max root heap，而是max/min values
heap
"这时国男也一脸诚恳的“提醒”我说：是的，你用min heap找出来的是最不常用的K个
word哦"
【在 s**x 的大作中提到】
:
: I am surprised max heap is even an option here.
: My only explanation is people get confused by min max heap.
: I never liked linkedin. Good luck with 楼主，take it easy and bless.
|
|
|
u*****n
发帖数: 126 | 61 Bless楼主。你一定能够去更好的地方。
有这样的同事，不去也罢。 |
m*****l
发帖数: 95 | 62 maxHeap妥妥的O(n)空间复杂度
【在 m*****n 的大作中提到】
: 其他nlog(n)排序方法要额外空间，就heap不要。
|
m*****n
发帖数: 2152 | 63 对doc里出现的word建inverted index的那道题，烙印要的最佳答案是什么？
是用B-Tree吗？
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
j**********3
发帖数: 3211 | 64 design monitoring system
能说说这个怎么design的么？谢谢lz |
p*****e
发帖数: 537 | 65 我用的是c++，而且thread是最后一个小题，和前面的没啥关联。
【在 z*******3 的大作中提到】
: 是应该用min heap，因为pop出来的是min而不是max
: 但是你的答题没有觉察出对方的意图
: stream那个，用concurrenthashmap
: 考官三番五次提醒threading也是想听到你说这个东西
: 这个其实就是考jdk1.5的new feature，core java的基本功
: 楼主的java经验也不丰富
: 所以多数时候说的是书本上的东西，比如读写锁这些
: 不match也正常，工作和理论还是有距离的
: 如果google面，用python的话，估计楼主就过了
|
p*****e
发帖数: 537 | 66 这道题自我感觉不是在考multithreading，因为从头到尾都没有提到thread，最后那个
thread的小题和这个inverted index没啥关系，这一轮应该是在考大数据处理。
【在 z*******3 的大作中提到】
: 不过min heap还是max heap真心不重要
: 你就是做成min&max heap又怎样？两头都能pop就好了
: 能pop最小也能pop最大的，反正insert效率都是一样的
: 这只是定义，对方的理解是把min想成你存最小值了
: 就象空穴来风，明明文字上意思是言之有据
: 但是无数人认为这个是扯蛋的意思
: 纠结这个就有些书呆了，无所谓，互相理解一下
: 如果你想结合理论的话，pirorityqueue就是基于heap的实现
: 这个是我从swjtuer那边偷来的
: 多线程对方考点还真的不是fairness strategy
|
p*****e
发帖数: 537 | 67 哦～是了是了，老印和国男一定想的是max value heap，所以他们一再坚持用min heap
（估计他们想的是min value heap）是错的！
当时有点愣，就光顾想为啥他们说min heap不对了，没反应过来这个啊！要是能想到赵
策兄说的这一点就好了！
【在 z*******3 的大作中提到】
: 楼主说的min heap是data structure里面的min heap
: data structure里面所谓的min heap有特殊的定义，min指的是root
: 但是面试官说的max heap意思是max value的heap（包括min&max heap)
: max说的是values，而不是root
: 严格说来，是max values的min heap
: 我神经快错乱了
: 这种题目其实深入下去很恶心，红黑树就在后面，如果说treemap的，要小心点
: http://my.oschina.net/leejun2005/blog/135085
|
p*****e
发帖数: 537 | 68 冤枉啊，他们当时没提示我任何思路，我就完全说自己思路来着。而且有前面说的老印
只想听我的optimal solution，我都不敢扯别的option，怕他烦啊！
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
p*****e
发帖数: 537 | 69 啥是“动车洗车”？
【在 s*****r 的大作中提到】
: 烙印的态度有问题
: LZ回答问题也有些动车洗车，这样会让面试官反感，在一个问题上不要耽误太多时间。
: 国人表达能力一般比较弱，说太多容易让人犯晕，会被认为没有思路。表达能力强的可
: 以多解释，多动车洗车，很多老美烙印喜欢这样。
|
l*********8
发帖数: 4642 | 70 东扯西扯吧：）
【在 p*****e 的大作中提到】
: 啥是“动车洗车”？
|
|
|
p*****e
发帖数: 537 | 71 就是有一堆server，每个server上都run一个或多个service，每个service都产生一些
需要monitor的数据，比如throughput啊，error啊等等。然后在client端就把某个
window内的数据给show出来，就跟你看股票的报价图一样。
【在 j**********3 的大作中提到】
: design monitoring system
: 能说说这个怎么design的么？谢谢lz
|
E*******1
发帖数: 3464 | 72 楼主可能面试时候没说清楚，min或max应该都行，说清楚不是太难。有时候面试官和面
试的交流会有些问题，双方不知道对方在说同一个问题，楼主过于执着于一种解法(也
可能只知道这个解法)，可能也表示了对其他方法的鄙视，反正把人家搞毛了
【在 n**n 的大作中提到】
: http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-a
: both are fine.
|
m********n
发帖数: 211 | 73 找工作最主要的是让人感觉愿意和你一起工作，有能力只是一方面，合作起来舒服不舒
服也很重要。你去面试，并不是为了证明老子永远正确，事实上工作上的很多问题，并
没有绝对的对错，反过来说，换了你来招人，也不想找一个自以为是的，能力知识这些
，在我们这个层次，干我们这些活，其实大家都脚碰脚，合作愉快才是关键。你要是纠
结于min max之分，脸红脖子粗得还要另一个面试官出言调解，就没有看到症结所在，
下次还要跌跟头。
面试也好工作也罢，和学校考试是不一样的，不要太一根筋了。
★ 发自iPhone App: ChineseWeb 8.7 |
o**********e
发帖数: 18403 | 74 LZ挺好， LS建议好。
就投诉烙印说： not professional, keeps
interrupting me.
不用提国男。 烙印要黑就黑个大烙印，
小虾米不用太费神。 越高越危险。 |
j**********3
发帖数: 3211 | 75 谢谢lz
【在 p*****e 的大作中提到】
: 就是有一堆server，每个server上都run一个或多个service，每个service都产生一些
: 需要monitor的数据，比如throughput啊，error啊等等。然后在client端就把某个
: window内的数据给show出来，就跟你看股票的报价图一样。
|
b****f
发帖数: 138 | |
t*********7
发帖数: 255 | |
g*****g
发帖数: 212 | |
d********3
发帖数: 25 | 79 赞啊，求林先生分享经验和细节，in case我们以后遇到类似情况捉急
【在 l****r 的大作中提到】
: 我前几年面过一次公司，当时有一个interviewer态度不好，经常打断我的话，然后用
: 很多带着不屑的反问，我面完了立马向HR投诉了他。然后HR和我道歉，说他那个人确实
: 有问题，以前也被其他人投诉过。结果完了一样给我发了offer。
: 投诉不是打官司，不需要证据，一个反馈而已。
|
R*********d
发帖数: 34 | 80 建议楼主看看CC150 18.6第五版的solution， 或者第四版20.6的solution，这儿有点
confuse的，第五版solution写的是Min Heap，但实际first create一个max heap，通
过添加删除操作最后得到的是min heap。 第四版solution写的是Max Heap，但实际
first create一个min heap， 通过添加删除操作最后得到的是Max Heap。我觉得面试
官有点抠字眼。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
|
|
c******e
发帖数: 558 | |
t*********l
发帖数: 844 | 82 min-heap: k + (n-k)logk
max-heap: n + klogn
除非k很大，否则max-heap当然更快
【在 t***t 的大作中提到】
: should use min-heap.
: sign, so many here as clueless as the a3 interviewer.
|
g*********e
发帖数: 14401 | 83
关键是n很大，maxheap的空间要求是n，minheap空间只要k
【在 t*********l 的大作中提到】
: min-heap: k + (n-k)logk
: max-heap: n + klogn
: 除非k很大，否则max-heap当然更快
|
b********r
发帖数: 620 | 84 多谢大牛花时间解释的这么清楚，我也是今天才知道堆可以有所谓的大小之分。不过我
一般会给面官讲清楚，我的堆是多大，然后根是最大值最小值。这样一讲，都清楚了。
可能楼主误会为面官不认可他的数据结构，头脑没有及时转过来。
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
w**6
发帖数: 12 | 85 童鞋们遇上了变态的一定要投诉。如果被投诉几次了，他再出来害人的机会就小多了。
不嫌麻烦的再到glassdoor等去发帖子。 |
e*****i
发帖数: 182 | 86 谢各位，长知识了呢
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
j********x
发帖数: 2330 | 87 你傻逼啊，shadow的在feedback根本不算数的。。。
【在 p*****e 的大作中提到】
: 其实比起那个阿三来，我对那个国男更觉得惋惜。本来LinkedIn面试安排一个shadow，
: 就是为了做做笔记啊，大家有分歧的时候可以做个补充啊啥的。阿三很水很笨这不是很
: 正常么？但国男也是这么水么？在阿三刁难我的时候他也啥都不说啥都不做，他那个
: shadow真的只是个shadow而已啊！
|
b*****d
发帖数: 39 | 88 我觉得楼主实力很强！bless！我也一直以为min-heap是正解，刚才看了这个geek4geek
的讲解，感觉max-heap和min-heap都可以。而却好像确实当n >> k时，max-heap的时间
复杂度是(klogn)是比min-heap的时间复杂度O(nlogk)要好。当然max-heap的代价是空
间复杂度比较高。
楼主加油，一定会有好的offer的。加油。 |
b******k
发帖数: 5 | 89 问个傻问题~大家讨论最多的那个第四轮的题~要求的是找出K个最常见的word~应该是说
频率最高~为什么大家讨论的貌似都是值得大小呢？
贴的链接也是在说“k largest(or smallest) elements in an array”
还是说先过一遍所有word~找出所有词的频率~再来用这个算法？
这样的话~空间复杂度是不是还要考虑字典的大小呢？
还是说这个复杂度里面的n就是字典的大小？ |
s*******m
发帖数: 228 | 90 能讲讲
stream那个，用concurrenthashmap。。
其实没明白这个题，
sliding window 是干嘛的？
【在 z*******3 的大作中提到】
: 是应该用min heap，因为pop出来的是min而不是max
: 但是你的答题没有觉察出对方的意图
: stream那个，用concurrenthashmap
: 考官三番五次提醒threading也是想听到你说这个东西
: 这个其实就是考jdk1.5的new feature，core java的基本功
: 楼主的java经验也不丰富
: 所以多数时候说的是书本上的东西，比如读写锁这些
: 不match也正常，工作和理论还是有距离的
: 如果google面，用python的话，估计楼主就过了
|
|
|
s*******m
发帖数: 228 | 91 这个题是什么意思？
有个数据流，一个固定的窗口，可以想象成流划过窗口，
返回窗口中数据的平均值？
这么理解对吗
【在 p**i 的大作中提到】
: 哪位大牛能讲讲第二轮：印男加国男，given a stream of data and a sliding
: window, implement put(), getAverage()。考虑multithreading的情况。
|
c****8
发帖数: 76 | 92 Inverted Index 那个分布式的解法，谁能给我连接？想学习学习。 |
g****v
发帖数: 971 | 93 这个题有什么trick的地方么，这个题的考点是什么？
【在 p*****e 的大作中提到】
: 就是有一堆server，每个server上都run一个或多个service，每个service都产生一些
: 需要monitor的数据，比如throughput啊，error啊等等。然后在client端就把某个
: window内的数据给show出来，就跟你看股票的报价图一样。
|
s*******m
发帖数: 228 | 94 同求
【在 c****8 的大作中提到】
: Inverted Index 那个分布式的解法，谁能给我连接？想学习学习。
|
i*******t
发帖数: 79 | 95 明白了，miniheap是这么用的啊。。。这好像确实不太主流
我有一个问题！！！！
楼主说“用min heap找出每个machine的K个最常见word”
先不说min还是max吧，难道K个最常见的词肯定出现在某个machine上的top K里么？？？
我看怎么就是一个基本的mapreduce问题，先数，然后加，然后再来一遍排序呢。
都说mapreduce了，如果n很大装不进内存就加机器就行了，但是我还是觉得人家没想考
heap
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
g*******n
发帖数: 8 | |
c******n
发帖数: 4965 | 97 ft 难道只有我一个人看出来 明摆着 k 小于（大大小于）N 么？
您刷题刷晕了？
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
c******n
发帖数: 4965 | 98 你说的不对， max heap. 时间你说的那只是建成了堆。“以后” 再抽出k个的时间，
建堆已经就是 nlogn 了， 明摆着不 make sense
geek4geek
【在 b*****d 的大作中提到】
: 我觉得楼主实力很强！bless！我也一直以为min-heap是正解，刚才看了这个geek4geek
: 的讲解，感觉max-heap和min-heap都可以。而却好像确实当n >> k时，max-heap的时间
: 复杂度是(klogn)是比min-heap的时间复杂度O(nlogk)要好。当然max-heap的代价是空
: 间复杂度比较高。
: 楼主加油，一定会有好的offer的。加油。
|
c******n
发帖数: 4965 | 99 我觉得你态度不是很适合
现在的公司面人都很牛逼， 你得毕恭毕敬让他们耍牛逼一会， 说你们这真牛等等，要
不最直接就是 culture fit 把你搞掉。
其实就是投其所好骗进去拿高工资混日子呗，然后做自己的小公司。 这就是我的目标
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
p*****e
发帖数: 537 | 100 电面：
第一次：印男，implement string matching and replacing
第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
onsite:
第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
第二轮：印男加国男，given a stream of data and a sliding window, implement
put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
第三轮: 吃饭
第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
个中年老印加一个中年国男，国男shadow。老印一出现就是一幅超鄙夷超不屑的臭脸。
出了一个inverted index的题，就是有一大堆doc，对doc里出现的word建inverted
index，doc很多所以是distribute在很多machine上的，问怎么实现这个inverted
index。我听了题目暗爽，这种题我准备的很充分啊！因为这题有很多解法，我就从差
到好一一说来，每个都说了为啥不好，然后引出我认为最好的那一个。可是我每说一个
老印就急吼吼的跳起来反驳我。搞了两回，我意识到可能老印就是想听最佳答案，我就
解释说我只是想list一下所有的option，我也问他你是不是prefer直接告诉你最佳答案
？他说是。我就直接给了我认为的最佳答案。
接下来还有几个相关的小问题我都忘了，有一个是关于map reduce的。最后一个，是找
出前K个最常用的word。我说用min heap找出每个machine的K个最常见word，再用一个
min heap merge这些list。奇葩的事情就出现了，老印跳出来说，不对，你用min heap
是不对的，应该用max heap！这时国男也一脸诚恳的“提醒”我说：是的，你用min
heap找出来的是最不常用的K个word哦！我我我，我当场就愣了！不会吧，俩linkedin
的老员工了，好歹是个面试官啊，居然连min heap和max heap是啥都不知道？愣了两秒
，我就给他们讲了一遍啥是min heap啥是max heap，和为啥找K个最常用的word要用min
heap而不是max heap。一遍讲我一边想：我这是来面试的还是来给linkedin的员工培
训基本data structure的？最后俩人还是将信将疑，又问了一个有关于thread的小问题
就结束了。
第五轮：小印女加小印男，也是问了一个类似在stream里找k个最大数的题，我还是用
了min heap，还好俩人都知道啥是min heap，也比较认同我的做法。然后大部分的时间
都在讨论multi threading的实现，我提到了read write lock，和三种fairness
policy，不过他俩都是一脸茫然，好像他们只知道read write lock，但不知道
fairness这回事，挺奇怪的。（另：刚又想起，这一轮还问了max point on a line一
题，leetcode上有，只要求pseudo code，我做了个square的，问小印男还有没有更快
的，他说就他所知没有了）。
第六轮：亚裔男（不是国男）加印男，问了romanToInt和intToRoman的题，intToRoman
和leetcode一样，但romanToInt要考虑很多corner case。这些corner case在leetcode
和EPI上都没有提到过。另外，好像EPI上的解法很多错误，我没看几道题就已经找出很
多错了，有的错的很离谱，大家得注意一下。
第七轮：白男加国女，问了一个design的题，design monitoring system，自我感觉是
发挥的最好的一轮。
面完以后我就觉得，成败就在第四轮，最后果然就跪在了这一轮。不过我是一点遗憾都
没有，要是给了我offer，让我去和对我天生有敌意的老印，还有分不清min heap和max
heap的人一起共事，其实也不是什么好事。还有我觉得好几个问道我multithreading
问题的人，本身对multithreading也不是很熟，像那个read write lock fairness
policy的问题，还有lock free algo的ABA问题，他们好像都不知道，那他们平时是咋
把multithreading的程序写对的啊？
所以我现在挺疑惑的：是不是我特别倒霉，碰上的都是linkedin里水平比较低的一些人
，还是linkedin的员工水平并不像原本我想的那么高？ |
|
|
w****r
发帖数: 15252 | 101 7个面试，疯了
我这个工作就电面 onsite两次就完了
大公司就是牛逼啊 |
t***t
发帖数: 6066 | 102 some guys are lucky and joined linkedin early when it's nothing. so people
from schools like santa cruz university joined and their level is pretty low
. |
n*******1
发帖数: 145 | 103 max-heap min-heap各有利弊吧 一个time n space n 一个time nlogk space k 说清楚
就行了吧 |
p*****e
发帖数: 537 | 104 咋用max heap找k个最大的数 in time O(n) space O(n)? 展开说说？
【在 n*******1 的大作中提到】
: max-heap min-heap各有利弊吧 一个time n space n 一个time nlogk space k 说清楚
: 就行了吧
|
q********c
发帖数: 1774 | 105 赞一个，你的水平肯定没问题。请问你是面的那个组，是applications
team还是infrastructure?
另，heap那道题应该用max heap, 因为频率高的都保留在heap里面了。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l****i
发帖数: 2772 | 106 min heap才是保存频率高的k个
【在 q********c 的大作中提到】
: 赞一个，你的水平肯定没问题。请问你是面的那个组，是applications
: team还是infrastructure?
: 另，heap那道题应该用max heap, 因为频率高的都保留在heap里面了。
:
: 情况
|
o***g
发帖数: 2784 | 107 大牛，给我讲讲啥事min heap啥是max heap呗
为啥这里需要用min heap，不能用max heap呢？
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l****r
发帖数: 118 | 108 每次比较替换最小（不常用）的root啊。只需维护size k的 min heap.
用max heap的话得用所有词建了，size n，然后取max K次。
【在 q********c 的大作中提到】
: 赞一个，你的水平肯定没问题。请问你是面的那个组，是applications
: team还是infrastructure?
: 另，heap那道题应该用max heap, 因为频率高的都保留在heap里面了。
:
: 情况
|
n**n
发帖数: 626 | 109 http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-a
both are fine.
【在 p*****e 的大作中提到】
: 咋用max heap找k个最大的数 in time O(n) space O(n)? 展开说说？
|
a******f
发帖数: 9 | 110 上来吐槽一下并支持楼主
第四轮是面试官错了。 |
|
|
m*****l
发帖数: 95 | |
p**i
发帖数: 22 | 112 哪位大牛能讲讲第二轮：印男加国男，given a stream of data and a sliding
window, implement put(), getAverage()。考虑multithreading的情况。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l******i
发帖数: 880 | 113 面试官应该没错，如果n相对于k很大，我感觉还是用max heap比较好。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l******6
发帖数: 340 | 114 看来怪不得linkedIn面试官 不少版友都支持max heap ........ |
G*****n
发帖数: 19 | 115 赞楼主 鄙视第四轮
请问楼主你说
"但romanToInt要考虑很多corner case"
是什么意思呢？
你是指 IV IX 这种情况吗？
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
l****i
发帖数: 2772 | 116 详细解释听听？
【在 l******i 的大作中提到】
: 面试官应该没错，如果n相对于k很大，我感觉还是用max heap比较好。
:
: 情况
|
o********t
发帖数: 1655 | 117 投诉那个阿三，这个不投诉就太软弱了
不去也不能让他好过了。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
t***t
发帖数: 6066 | 118 should use min-heap.
sign, so many here as clueless as the a3 interviewer.
【在 l******i 的大作中提到】
: 面试官应该没错，如果n相对于k很大，我感觉还是用max heap比较好。
:
: 情况
|
p*****e
发帖数: 537 | 119 我要是投诉阿三，岂不是连国男也一起投诉了？他也说用min heap不对来着
【在 o********t 的大作中提到】
: 投诉那个阿三，这个不投诉就太软弱了
: 不去也不能让他好过了。
:
: 情况
|
o********t
发帖数: 1655 | 120 你可以只投诉阿三啊。怎么一根筋。。。
我发现你们码农的思维太过程序化。被两个人刁难了谁规定只能投诉两个人否则不能投
诉？
【在 p*****e 的大作中提到】
: 我要是投诉阿三，岂不是连国男也一起投诉了？他也说用min heap不对来着
|
|
|
p**o
发帖数: 3409 | 121 http://hg.python.org/cpython/file/2.7/Lib/heapq.py
参考python标准库的nlargest()算法（第221行），
就是用一个大小为n的min-heap；
同理，nsmallest()应该用max-heap来求。
【在 o***g 的大作中提到】
: 大牛，给我讲讲啥事min heap啥是max heap呗
: 为啥这里需要用min heap，不能用max heap呢？
:
: 情况
|
p*****e
发帖数: 537 | |
l****r
发帖数: 118 | 123 投诉他的态度啊，你总不能投诉他不懂该用min heap吧
【在 p*****e 的大作中提到】
: 我要是投诉阿三，岂不是连国男也一起投诉了？他也说用min heap不对来着
|
p*****e
发帖数: 537 | 124 怎么投诉他态度？说他啥都没说就对我一脸鄙夷？他可以解释说他天生就是一副臭脸，
对他老板都一样。投诉他我每说一句话他都跳起来反驳？他可以解释说是
miscommunication，说他不想听我给他分析其他方法的缺点，只想听最佳答案。
我不觉得我complain会对最终结果有任何的改变，不过我确实和recruiter交流过这些
concern，当然是比较委婉的表达方式。
不过版上有xdjm要面LinkedIn，我可以告诉你们这俩人的名字，你们可以提防一点。
【在 l****r 的大作中提到】
: 投诉他的态度啊，你总不能投诉他不懂该用min heap吧
|
o********t
发帖数: 1655 | 125 不是为了改变结果，是为了你自己出口气，二是打击一下烙印的嚣张气焰，对后面的同
胞有利
【在 p*****e 的大作中提到】
: 怎么投诉他态度？说他啥都没说就对我一脸鄙夷？他可以解释说他天生就是一副臭脸，
: 对他老板都一样。投诉他我每说一句话他都跳起来反驳？他可以解释说是
: miscommunication，说他不想听我给他分析其他方法的缺点，只想听最佳答案。
: 我不觉得我complain会对最终结果有任何的改变，不过我确实和recruiter交流过这些
: concern，当然是比较委婉的表达方式。
: 不过版上有xdjm要面LinkedIn，我可以告诉你们这俩人的名字，你们可以提防一点。
|
p*****e
发帖数: 537 | 126 其实比起那个阿三来，我对那个国男更觉得惋惜。本来LinkedIn面试安排一个shadow，
就是为了做做笔记啊，大家有分歧的时候可以做个补充啊啥的。阿三很水很笨这不是很
正常么？但国男也是这么水么？在阿三刁难我的时候他也啥都不说啥都不做，他那个
shadow真的只是个shadow而已啊！ |
p*****e
发帖数: 537 | 127 我明白你的好意，不过我真的不生气，就像我帖子里写的，和这样的人共事不一定是件
好事，所以他们据我对我来说也不是一件坏事，所以我没啥生气没啥惋惜的。
至于对后面的同胞而言，我面完的第二天recruiter来收集面试意见，我就委婉的和他
提过这些concern，相信他应该明白是怎么回事了。
【在 o********t 的大作中提到】
: 不是为了改变结果，是为了你自己出口气，二是打击一下烙印的嚣张气焰，对后面的同
: 胞有利
|
l****r
发帖数: 118 | 128 我前几年面过一次公司，当时有一个interviewer态度不好，经常打断我的话，然后用
很多带着不屑的反问，我面完了立马向HR投诉了他。然后HR和我道歉，说他那个人确实
有问题，以前也被其他人投诉过。结果完了一样给我发了offer。
投诉不是打官司，不需要证据，一个反馈而已。
【在 p*****e 的大作中提到】
: 怎么投诉他态度？说他啥都没说就对我一脸鄙夷？他可以解释说他天生就是一副臭脸，
: 对他老板都一样。投诉他我每说一句话他都跳起来反驳？他可以解释说是
: miscommunication，说他不想听我给他分析其他方法的缺点，只想听最佳答案。
: 我不觉得我complain会对最终结果有任何的改变，不过我确实和recruiter交流过这些
: concern，当然是比较委婉的表达方式。
: 不过版上有xdjm要面LinkedIn，我可以告诉你们这俩人的名字，你们可以提防一点。
|
p**i
发帖数: 22 | 129 哪位大牛能讲讲第二轮：印男加国男，given a stream of data and a sliding
window, implement put(), getAverage()。考虑multithreading的情况。 |
c**********8
发帖数: 1052 | 130 楼主水平好强，那些design，多线程什么的其实感觉最能区分出candidate的水平，
algo啥只的是基础
我曾经在M有一轮也是我说一句，后面三句等着我，连续打断我几次，就算我思路不对
，就让我改就行了，那人还要说好几句类比（真的是用非技术的例子类比）说我为什么
不对。在一个地方卡了好几分钟，其实明明不是思路不对，是没听我说完。
楼主加油
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
|
|
p********n
发帖数: 165 | 131 max heap 有max heap的做法
min heap 有min heap的做法，最终复杂度差不多，决定于k 和n的关系。。。
光刷leetcode是不行的。 |
m*****n
发帖数: 2152 | 132 既然是用map reduce，n应该很大很大，要考虑momery不足的情况，用min heap节省空
间。
多出logk的时间复杂度应该没什么。
L家这么水，估计楼主是因为太强了，被拒的。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
r****7
发帖数: 2282 | 133 本版硬说max heap可以做的都是为了显得自己高明或者为了显得自己和L家比较近么。
。。
这个用max heap做还不如说排序呢。
BTW，我觉得你好强，是平时接触分布式和多线程就很多吗？
time
【在 p*****e 的大作中提到】
: 我明白你的好意，不过我真的不生气，就像我帖子里写的，和这样的人共事不一定是件
: 好事，所以他们据我对我来说也不是一件坏事，所以我没啥生气没啥惋惜的。
: 至于对后面的同胞而言，我面完的第二天recruiter来收集面试意见，我就委婉的和他
: 提过这些concern，相信他应该明白是怎么回事了。
|
p*****e
发帖数: 537 | 134 我是菜鸟我知道...我要是很强估计其他的interviewer也会保我了...
【在 m*****n 的大作中提到】
: 既然是用map reduce，n应该很大很大，要考虑momery不足的情况，用min heap节省空
: 间。
: 多出logk的时间复杂度应该没什么。
: L家这么水，估计楼主是因为太强了，被拒的。
:
: 情况
|
m*****n
发帖数: 2152 | 135 其他nlog(n)排序方法要额外空间，就heap不要。
【在 r****7 的大作中提到】
: 本版硬说max heap可以做的都是为了显得自己高明或者为了显得自己和L家比较近么。
: 。。
: 这个用max heap做还不如说排序呢。
: BTW，我觉得你好强，是平时接触分布式和多线程就很多吗？
:
: time
|
m*****n
发帖数: 2152 | 136 有个词叫over qualify，如果水平远超同事甚至是manager，对group团结没好处。而且
，说不定会担心招来了，马上又跳槽。
【在 p*****e 的大作中提到】
: 我是菜鸟我知道...我要是很强估计其他的interviewer也会保我了...
|
e********r
发帖数: 24 | 137 are you serious?
【在 m*****n 的大作中提到】
: 其他nlog(n)排序方法要额外空间，就heap不要。
|
e********r
发帖数: 24 | |
w*****c
发帖数: 7276 | |
o***g
发帖数: 2784 | 140 我觉得今天HM写的那个就是给你写的，人家没好意思直接在你主题下写
从你的文章中感觉出来你已经很牛了
【在 p*****e 的大作中提到】
: 我是菜鸟我知道...我要是很强估计其他的interviewer也会保我了...
|
|
|
p*****e
发帖数: 537 | 141 恩，看了HM写的那个，觉得很中肯。其实我也没觉得我被黑了，不过recruiter很明确
的告诉了我主要问题就是在那一轮，所以我也很想知道我的问题到底出在哪儿了？
而且我在面试的时候是很注意要表现的humble一些的，所以虽然那个老印一开始总是跳
出来说我说的不对，我也就是很平静的问他你是不是prefer一个optimal的solution就
ok了，他说是，我给了他我认为的optimal solution，后来他也安生了一阵子，直到那
个min heap/max heap的问题出现。
【在 o***g 的大作中提到】
: 我觉得今天HM写的那个就是给你写的，人家没好意思直接在你主题下写
: 从你的文章中感觉出来你已经很牛了
|
t********e
发帖数: 1169 | |
z*******3
发帖数: 13709 | 143 是应该用min heap，因为pop出来的是min而不是max
但是你的答题没有觉察出对方的意图
stream那个，用concurrenthashmap
考官三番五次提醒threading也是想听到你说这个东西
这个其实就是考jdk1.5的new feature，core java的基本功
楼主的java经验也不丰富
所以多数时候说的是书本上的东西，比如读写锁这些
不match也正常，工作和理论还是有距离的
如果google面，用python的话，估计楼主就过了 |
z*******3
发帖数: 13709 | 144 不过min heap还是max heap真心不重要
你就是做成min&max heap又怎样？两头都能pop就好了
能pop最小也能pop最大的，反正insert效率都是一样的
这只是定义，对方的理解是把min想成你存最小值了
就象空穴来风，明明文字上意思是言之有据
但是无数人认为这个是扯蛋的意思
纠结这个就有些书呆了，无所谓，互相理解一下
如果你想结合理论的话，pirorityqueue就是基于heap的实现
这个是我从swjtuer那边偷来的
多线程对方考点还真的不是fairness strategy
对方其实目的很简单，就想知道你知道不知道最常用的core java类是什么
inverted index那题估计也不是纯粹考理论，应该是希望看到类似半海那种答案
半海遇到过类似的问题，问的是distributed lock
半海答案很简单，用zookeeper
就过了 |
z*******3
发帖数: 13709 | 145 面试次数多说明l家内部要不要楼主有争议
所以补了几个
楼主的解决方案不能说是错的
但是毕竟工作中比较少这么做
l家估计认为楼主有潜力，值得培养
就看内部人愿意不愿意培养了
【在 w****r 的大作中提到】
: 7个面试，疯了
: 我这个工作就电面 onsite两次就完了
: 大公司就是牛逼啊
|
z*******3
发帖数: 13709 | 146 楼主说的min heap是data structure里面的min heap
data structure里面所谓的min heap有特殊的定义，min指的是root
但是面试官说的max heap意思是max value的heap（包括min&max heap)
max说的是values，而不是root
严格说来，是max values的min heap
我神经快错乱了
这种题目其实深入下去很恶心，红黑树就在后面，如果说treemap的，要小心点
http://my.oschina.net/leejun2005/blog/135085
【在 p**o 的大作中提到】
: http://hg.python.org/cpython/file/2.7/Lib/heapq.py
: 参考python标准库的nlargest()算法（第221行），
: 就是用一个大小为n的min-heap；
: 同理，nsmallest()应该用max-heap来求。
|
z*******3
发帖数: 13709 | 147 看别人博客上说
楼主用的min heap其实就是treemap的方式
其开销要大于priorityqueue |
z*******3
发帖数: 13709 | |
z*******3
发帖数: 13709 | 149 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
s*****r
发帖数: 43070 | 150 烙印的态度有问题
LZ回答问题也有些动车洗车，这样会让面试官反感，在一个问题上不要耽误太多时间。
国人表达能力一般比较弱，说太多容易让人犯晕，会被认为没有思路。表达能力强的可
以多解释，多动车洗车，很多老美烙印喜欢这样。 |
|
|
z*******3
发帖数: 13709 | 151 priority queue的add和remove实现你看懂了没？
我看得晕头转向的
看懂了，插入删除都有讲究，光min heap是不够的
priority queue是王道，洗澡去了
【在 s*****r 的大作中提到】
: 烙印的态度有问题
: LZ回答问题也有些动车洗车，这样会让面试官反感，在一个问题上不要耽误太多时间。
: 国人表达能力一般比较弱，说太多容易让人犯晕，会被认为没有思路。表达能力强的可
: 以多解释，多动车洗车，很多老美烙印喜欢这样。
|
k******e
发帖数: 19 | 152
情况
你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
TOP K的问题。
- 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
的就REPLACE ROOT，然后将其 SIFT DOWN。
－ 用MAXHEAP的话，空间复杂度是O（N）， 时间复杂度是 O（KlogN）。
这个办法只能用在N不是太大的时候，可以先HEAPIFY，用时O（N）。现在你的ROOT
是最大的，把ROOT拿掉放进你的RESULT里，你的HEAP的ROOT空了，把最后一个元素放进
ROOT，SIFT DOWN， 又得到一个MAXHEAP，重复刚才的操作K次，得到你的RESULT.
两种方法都没错，而且也不一定哪个就更好，就算光是看时间复杂度，NlogK和KlogN哪
个好也要看你的K和N是多大。
你在面试的时候试图教育面试官，这个不管到哪你都会碰壁的（不是要为那个臭脸阿三
辩护，臭脸阿三最惹人厌）。我有个朋友最近面试失败就是败在没有跟着面试官的思路
走，任何HINT都不愿意TAKE，一味地按照自己的思路走。你想想，如果你是面试官，你
试图提出一些HINT，对方全部不听，你会不会觉得对方有些ARROGANT？
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
k******e
发帖数: 19 | 153 这个解释得很清楚了：
http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
【在 k******e 的大作中提到】
:
: 情况
: 你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
: 这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
: TOP K的问题。
: - 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
: 这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
: 就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
: 后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
: 的就REPLACE ROOT，然后将其 SIFT DOWN。
|
s*****r
发帖数: 43070 | 154 都是general hiring，面试官都是临时拼凑的，没有group团结这一说
【在 m*****n 的大作中提到】
: 有个词叫over qualify，如果水平远超同事甚至是manager，对group团结没好处。而且
: ，说不定会担心招来了，马上又跳槽。
|
s*****r
发帖数: 43070 | 155 公正的评论一下，L家的项目还是很有趣的，能学到不少东西，不少项目都是full
stack，要负责前段，后端，data modeling，大型网站的数据流程，数据分析，每个项
目只有一两个人去做，亚历山大。适合刚毕业的小码农，不适合喜欢混日子的老码农。
吐槽活累事多钱少，股价很蛋疼
超级赞美食堂的饭菜质量，很多菜比外面的餐馆都强，年底的shutdown相当于放长假。
【在 g****t 的大作中提到】
: 尼玛一个破找工作的网站，尼玛整那么多画画肠子的程序有个屁用
|
s**x
发帖数: 7506 | 156
I am surprised max heap is even an option here.
My only explanation is people get confused by min max heap.
I never liked linkedin. Good luck with 楼主，take it easy and bless.
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
z*******3
发帖数: 13709 | 157 re这个
这句话可以证明他们其实想的不是定以上的min/max root heap，而是max/min values
heap
"这时国男也一脸诚恳的“提醒”我说：是的，你用min heap找出来的是最不常用的K个
word哦"
【在 s**x 的大作中提到】
:
: I am surprised max heap is even an option here.
: My only explanation is people get confused by min max heap.
: I never liked linkedin. Good luck with 楼主，take it easy and bless.
|
u*****n
发帖数: 126 | 158 Bless楼主。你一定能够去更好的地方。
有这样的同事，不去也罢。 |
m*****l
发帖数: 95 | 159 maxHeap妥妥的O(n)空间复杂度
【在 m*****n 的大作中提到】
: 其他nlog(n)排序方法要额外空间，就heap不要。
|
m*****n
发帖数: 2152 | 160 对doc里出现的word建inverted index的那道题，烙印要的最佳答案是什么？
是用B-Tree吗？
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
|
|
j**********3
发帖数: 3211 | 161 design monitoring system
能说说这个怎么design的么？谢谢lz |
p*****e
发帖数: 537 | 162 我用的是c++，而且thread是最后一个小题，和前面的没啥关联。
【在 z*******3 的大作中提到】
: 是应该用min heap，因为pop出来的是min而不是max
: 但是你的答题没有觉察出对方的意图
: stream那个，用concurrenthashmap
: 考官三番五次提醒threading也是想听到你说这个东西
: 这个其实就是考jdk1.5的new feature，core java的基本功
: 楼主的java经验也不丰富
: 所以多数时候说的是书本上的东西，比如读写锁这些
: 不match也正常，工作和理论还是有距离的
: 如果google面，用python的话，估计楼主就过了
|
p*****e
发帖数: 537 | 163 这道题自我感觉不是在考multithreading，因为从头到尾都没有提到thread，最后那个
thread的小题和这个inverted index没啥关系，这一轮应该是在考大数据处理。
【在 z*******3 的大作中提到】
: 不过min heap还是max heap真心不重要
: 你就是做成min&max heap又怎样？两头都能pop就好了
: 能pop最小也能pop最大的，反正insert效率都是一样的
: 这只是定义，对方的理解是把min想成你存最小值了
: 就象空穴来风，明明文字上意思是言之有据
: 但是无数人认为这个是扯蛋的意思
: 纠结这个就有些书呆了，无所谓，互相理解一下
: 如果你想结合理论的话，pirorityqueue就是基于heap的实现
: 这个是我从swjtuer那边偷来的
: 多线程对方考点还真的不是fairness strategy
|
p*****e
发帖数: 537 | 164 哦～是了是了，老印和国男一定想的是max value heap，所以他们一再坚持用min heap
（估计他们想的是min value heap）是错的！
当时有点愣，就光顾想为啥他们说min heap不对了，没反应过来这个啊！要是能想到赵
策兄说的这一点就好了！
【在 z*******3 的大作中提到】
: 楼主说的min heap是data structure里面的min heap
: data structure里面所谓的min heap有特殊的定义，min指的是root
: 但是面试官说的max heap意思是max value的heap（包括min&max heap)
: max说的是values，而不是root
: 严格说来，是max values的min heap
: 我神经快错乱了
: 这种题目其实深入下去很恶心，红黑树就在后面，如果说treemap的，要小心点
: http://my.oschina.net/leejun2005/blog/135085
|
p*****e
发帖数: 537 | 165 冤枉啊，他们当时没提示我任何思路，我就完全说自己思路来着。而且有前面说的老印
只想听我的optimal solution，我都不敢扯别的option，怕他烦啊！
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
p*****e
发帖数: 537 | 166 啥是“动车洗车”？
【在 s*****r 的大作中提到】
: 烙印的态度有问题
: LZ回答问题也有些动车洗车，这样会让面试官反感，在一个问题上不要耽误太多时间。
: 国人表达能力一般比较弱，说太多容易让人犯晕，会被认为没有思路。表达能力强的可
: 以多解释，多动车洗车，很多老美烙印喜欢这样。
|
l*********8
发帖数: 4642 | 167 东扯西扯吧：）
【在 p*****e 的大作中提到】
: 啥是“动车洗车”？
|
p*****e
发帖数: 537 | 168 就是有一堆server，每个server上都run一个或多个service，每个service都产生一些
需要monitor的数据，比如throughput啊，error啊等等。然后在client端就把某个
window内的数据给show出来，就跟你看股票的报价图一样。
【在 j**********3 的大作中提到】
: design monitoring system
: 能说说这个怎么design的么？谢谢lz
|
E*******1
发帖数: 3464 | 169 楼主可能面试时候没说清楚，min或max应该都行，说清楚不是太难。有时候面试官和面
试的交流会有些问题，双方不知道对方在说同一个问题，楼主过于执着于一种解法(也
可能只知道这个解法)，可能也表示了对其他方法的鄙视，反正把人家搞毛了
【在 n**n 的大作中提到】
: http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-a
: both are fine.
|
m********n
发帖数: 211 | 170 找工作最主要的是让人感觉愿意和你一起工作，有能力只是一方面，合作起来舒服不舒
服也很重要。你去面试，并不是为了证明老子永远正确，事实上工作上的很多问题，并
没有绝对的对错，反过来说，换了你来招人，也不想找一个自以为是的，能力知识这些
，在我们这个层次，干我们这些活，其实大家都脚碰脚，合作愉快才是关键。你要是纠
结于min max之分，脸红脖子粗得还要另一个面试官出言调解，就没有看到症结所在，
下次还要跌跟头。
面试也好工作也罢，和学校考试是不一样的，不要太一根筋了。
★ 发自iPhone App: ChineseWeb 8.7 |
|
|
o**********e
发帖数: 18403 | 171 LZ挺好， LS建议好。
就投诉烙印说： not professional, keeps
interrupting me.
不用提国男。 烙印要黑就黑个大烙印，
小虾米不用太费神。 越高越危险。 |
j**********3
发帖数: 3211 | 172 谢谢lz
【在 p*****e 的大作中提到】
: 就是有一堆server，每个server上都run一个或多个service，每个service都产生一些
: 需要monitor的数据，比如throughput啊，error啊等等。然后在client端就把某个
: window内的数据给show出来，就跟你看股票的报价图一样。
|
b****f
发帖数: 138 | |
t*********7
发帖数: 255 | |
g*****g
发帖数: 212 | |
d********3
发帖数: 25 | 176 赞啊，求林先生分享经验和细节，in case我们以后遇到类似情况捉急
【在 l****r 的大作中提到】
: 我前几年面过一次公司，当时有一个interviewer态度不好，经常打断我的话，然后用
: 很多带着不屑的反问，我面完了立马向HR投诉了他。然后HR和我道歉，说他那个人确实
: 有问题，以前也被其他人投诉过。结果完了一样给我发了offer。
: 投诉不是打官司，不需要证据，一个反馈而已。
|
R*********d
发帖数: 34 | 177 建议楼主看看CC150 18.6第五版的solution， 或者第四版20.6的solution，这儿有点
confuse的，第五版solution写的是Min Heap，但实际first create一个max heap，通
过添加删除操作最后得到的是min heap。 第四版solution写的是Max Heap，但实际
first create一个min heap， 通过添加删除操作最后得到的是Max Heap。我觉得面试
官有点抠字眼。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
c******e
发帖数: 558 | |
t*********l
发帖数: 844 | 179 min-heap: k + (n-k)logk
max-heap: n + klogn
除非k很大，否则max-heap当然更快
【在 t***t 的大作中提到】
: should use min-heap.
: sign, so many here as clueless as the a3 interviewer.
|
g*********e
发帖数: 14401 | 180
关键是n很大，maxheap的空间要求是n，minheap空间只要k
【在 t*********l 的大作中提到】
: min-heap: k + (n-k)logk
: max-heap: n + klogn
: 除非k很大，否则max-heap当然更快
|
|
|
b********r
发帖数: 620 | 181 多谢大牛花时间解释的这么清楚，我也是今天才知道堆可以有所谓的大小之分。不过我
一般会给面官讲清楚，我的堆是多大，然后根是最大值最小值。这样一讲，都清楚了。
可能楼主误会为面官不认可他的数据结构，头脑没有及时转过来。
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
e*****i
发帖数: 182 | 182 谢各位，长知识了呢
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
j********x
发帖数: 2330 | 183 你傻逼啊，shadow的在feedback根本不算数的。。。
【在 p*****e 的大作中提到】
: 其实比起那个阿三来，我对那个国男更觉得惋惜。本来LinkedIn面试安排一个shadow，
: 就是为了做做笔记啊，大家有分歧的时候可以做个补充啊啥的。阿三很水很笨这不是很
: 正常么？但国男也是这么水么？在阿三刁难我的时候他也啥都不说啥都不做，他那个
: shadow真的只是个shadow而已啊！
|
b*****d
发帖数: 39 | 184 我觉得楼主实力很强！bless！我也一直以为min-heap是正解，刚才看了这个geek4geek
的讲解，感觉max-heap和min-heap都可以。而却好像确实当n >> k时，max-heap的时间
复杂度是(klogn)是比min-heap的时间复杂度O(nlogk)要好。当然max-heap的代价是空
间复杂度比较高。
楼主加油，一定会有好的offer的。加油。 |
b******k
发帖数: 5 | 185 问个傻问题~大家讨论最多的那个第四轮的题~要求的是找出K个最常见的word~应该是说
频率最高~为什么大家讨论的貌似都是值得大小呢？
贴的链接也是在说“k largest(or smallest) elements in an array”
还是说先过一遍所有word~找出所有词的频率~再来用这个算法？
这样的话~空间复杂度是不是还要考虑字典的大小呢？
还是说这个复杂度里面的n就是字典的大小？ |
s*******m
发帖数: 228 | 186 能讲讲
stream那个，用concurrenthashmap。。
其实没明白这个题，
sliding window 是干嘛的？
【在 z*******3 的大作中提到】
: 是应该用min heap，因为pop出来的是min而不是max
: 但是你的答题没有觉察出对方的意图
: stream那个，用concurrenthashmap
: 考官三番五次提醒threading也是想听到你说这个东西
: 这个其实就是考jdk1.5的new feature，core java的基本功
: 楼主的java经验也不丰富
: 所以多数时候说的是书本上的东西，比如读写锁这些
: 不match也正常，工作和理论还是有距离的
: 如果google面，用python的话，估计楼主就过了
|
s*******m
发帖数: 228 | 187 这个题是什么意思？
有个数据流，一个固定的窗口，可以想象成流划过窗口，
返回窗口中数据的平均值？
这么理解对吗
【在 p**i 的大作中提到】
: 哪位大牛能讲讲第二轮：印男加国男，given a stream of data and a sliding
: window, implement put(), getAverage()。考虑multithreading的情况。
|
c****8
发帖数: 76 | 188 Inverted Index 那个分布式的解法，谁能给我连接？想学习学习。 |
g****v
发帖数: 971 | 189 这个题有什么trick的地方么，这个题的考点是什么？
【在 p*****e 的大作中提到】
: 就是有一堆server，每个server上都run一个或多个service，每个service都产生一些
: 需要monitor的数据，比如throughput啊，error啊等等。然后在client端就把某个
: window内的数据给show出来，就跟你看股票的报价图一样。
|
s*******m
发帖数: 228 | 190 同求
【在 c****8 的大作中提到】
: Inverted Index 那个分布式的解法，谁能给我连接？想学习学习。
|
|
|
i*******t
发帖数: 79 | 191 明白了，miniheap是这么用的啊。。。这好像确实不太主流
我有一个问题！！！！
楼主说“用min heap找出每个machine的K个最常见word”
先不说min还是max吧，难道K个最常见的词肯定出现在某个machine上的top K里么？？？
我看怎么就是一个基本的mapreduce问题，先数，然后加，然后再来一遍排序呢。
都说mapreduce了，如果n很大装不进内存就加机器就行了，但是我还是觉得人家没想考
heap
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
g*******n
发帖数: 8 | |
c******n
发帖数: 4965 | 193 ft 难道只有我一个人看出来 明摆着 k 小于（大大小于）N 么？
您刷题刷晕了？
【在 k******e 的大作中提到】
: 这个解释得很清楚了：
: http://www.ardendertat.com/2011/05/30/my-favorite-interview-que
|
c******n
发帖数: 4965 | 194 你说的不对， max heap. 时间你说的那只是建成了堆。“以后” 再抽出k个的时间，
建堆已经就是 nlogn 了， 明摆着不 make sense
geek4geek
【在 b*****d 的大作中提到】
: 我觉得楼主实力很强！bless！我也一直以为min-heap是正解，刚才看了这个geek4geek
: 的讲解，感觉max-heap和min-heap都可以。而却好像确实当n >> k时，max-heap的时间
: 复杂度是(klogn)是比min-heap的时间复杂度O(nlogk)要好。当然max-heap的代价是空
: 间复杂度比较高。
: 楼主加油，一定会有好的offer的。加油。
|
c******n
发帖数: 4965 | 195 我觉得你态度不是很适合
现在的公司面人都很牛逼， 你得毕恭毕敬让他们耍牛逼一会， 说你们这真牛等等，要
不最直接就是 culture fit 把你搞掉。
其实就是投其所好骗进去拿高工资混日子呗，然后做自己的小公司。 这就是我的目标
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
o******h
发帖数: 1142 | 196 请教大牛。
我只见过找出k个最小的数用heap的解法。
找出前K个最常用的word应该怎么变一下呢？要统计每个word出现的次数？能否详细说
说。
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
y****3
发帖数: 825 | 197 >>given a stream of data and a sliding
>>: window, implement put(), getAverage()。考虑multithreading的情况。
大牛请教：用C++做的话，有没有类似ConcurrentHashMap的类？怎么在C++里做出个Non
-blocking thread-safe hash map? Boost里没看到，多线程得用读写锁吧？ |
o****d
发帖数: 2835 | 198 那个monitoring的问题基本就是time series database要干的事 有不同metrics
可以参考opentsdb influxdb之类的
★ 发自iPhone App: ChineseWeb 1.0.6
★ 发自iPhone App: ChineseWeb 1.0.6
【在 g****v 的大作中提到】
: 这个题有什么trick的地方么，这个题的考点是什么？
|
s*******u
发帖数: 220 | 199 +1; bless.
情况
【在 p*****e 的大作中提到】
: 电面：
: 第一次：印男，implement string matching and replacing
: 第二次：国男，producer consumer,谢谢中国小弟弟出了这个我非常熟悉的题
: onsite:
: 第一轮：hiring manager，主要就是谈project，我讲了我最近在做的一个OO design的
: 东西，因为和面的组没啥关系，看得出来hiring manager是耐着性子听我说完的 :-P
: 第二轮：印男加国男，given a stream of data and a sliding window, implement
: put(), getAverage(),和另外一个function（忘了是啥了）。考虑multithreading的情况
: 第三轮: 吃饭
: 第四轮：最坑爹的一轮，recruiter告诉我也是跪在了这一轮，所以多说两句。来的是
|
