Google 店面一 09/252015

leixiang5 发表于 2015-9-26 00:32
"This is an optimization over method 1 if QuickSort is used as a sorting algorithm in first step.  ...

就感觉最差的情况是n2

leixiang5 发表于 2015-9-26 00:32
"This is an optimization over method 1 if QuickSort is used as a sorting algorithm in first step.  ...

最坏确实到n^2. 对于一般情况可以O(n)解决。。

找第k大的应该是用quick select吧，记得复杂度O（N）

谢谢楼主！～～G的模式果然没套路可言，每个人都不一样

mikegrup 发表于 2015-9-26 10:48
谢谢楼主！～～G的模式果然没套路可言，每个人都不一样

我问了下我的面试官。。每个software engineer可以当面试官。。题目又是他们自己出。。所以就会让每个人面试的经历不同。。所以g面试还要带点运气。。

leixiang5 发表于 2015-9-26 21:44
我问了下我的面试官。。每个software engineer可以当面试官。。题目又是他们自己出。。所以就会让每个人 ...

酱紫 请问你面试经验是啥，求分享

leixiang5 发表于 2015-9-26 00:32
"This is an optimization over method 1 if QuickSort is used as a sorting algorithm in first step.  ...

O(n)是average，worst case是O(n^2)。

快排worst case也是O(n^2)啊

Python最大的特点是duck-typing!

aiweiwei 发表于 2015-9-26 10:13
多谢大神指点。对，我当时也跟面试官说，我自己yy觉得python应该还是compile的，感觉像是在run的时候现去 ...

假设你要找 k-th max value in array A.
Keep 一个 min-heap，存储目前为止遇到的 k 个最大的数。
从头到尾遍历一遍 A：
当 heap size < k 的时候， insert into min-heap；
当 heap size == k 的时候，比较当前值和 min-heap 的 head ，如果当前值较小就忽略，反之 pop heap then insert 当前值。
循环结束后 pop heap 就是 k-th max 。

Running time：
min-heap insert / pop : O(log k) worst/average case
所以 overall 是 O(n log k) worst/average case

和 Quickselect （就是LZ提到的方法）相比， min-heap 法 worst case 更快，但 average case 稍稍逊色。关键看 worst case 是否有要求了。

楼主 原来google是接受用python面试的？？ 我学长在google里工作 他和我说：你刷题最后不要python 因为我们用c++和java的多，你面试用python我会很不爽。。。。

搞得我不敢用python呢。。。。