真慫阿, Facebook 1st phone interview,# JobHunting - 待字闺中
u*l
1 楼
问了一个问题，
里面有用到排序的复杂度。
我知道是 nlogn, 居然鬼使神差的一直用logn.....
一紧张就出错阿。
里面有用到排序的复杂度。
我知道是 nlogn, 居然鬼使神差的一直用logn.....
一紧张就出错阿。
r*o
2 楼
啥问题啊。
【在 u*l 的大作中提到】
: 问了一个问题，
: 里面有用到排序的复杂度。
: 我知道是 nlogn, 居然鬼使神差的一直用logn.....
: 一紧张就出错阿。
【在 u*l 的大作中提到】
: 问了一个问题，
: 里面有用到排序的复杂度。
: 我知道是 nlogn, 居然鬼使神差的一直用logn.....
: 一紧张就出错阿。
u*l
3 楼
很简单，一串数，找前k个最小的。
【在 r****o 的大作中提到】
: 啥问题啊。
【在 r****o 的大作中提到】
: 啥问题啊。
x*r
4 楼
这个题可以O(n)做，见http://en.wikipedia.org/wiki/Selection_algorithm
【在 u*l 的大作中提到】
: 很简单，一串数，找前k个最小的。
【在 u*l 的大作中提到】
: 很简单，一串数，找前k个最小的。
w*1
5 楼
谢谢楼上的链接
l*a
6 楼
I am confused of the explaination
=============================================
Direct application of the quick sort based selection algorithm
The quick sort based selection algorithm can be used to find k smallest or
k largest elements. To find k smallest elements find the kth smallest
element using the median of medians quick sort based algorithm. After the
partition that finds the kth smallest element, all the elements smaller
than the kth smaller element will be present left to the kth eleme
【在 x****r 的大作中提到】
: 这个题可以O(n)做，见http://en.wikipedia.org/wiki/Selection_algorithm
=============================================
Direct application of the quick sort based selection algorithm
The quick sort based selection algorithm can be used to find k smallest or
k largest elements. To find k smallest elements find the kth smallest
element using the median of medians quick sort based algorithm. After the
partition that finds the kth smallest element, all the elements smaller
than the kth smaller element will be present left to the kth eleme
【在 x****r 的大作中提到】
: 这个题可以O(n)做，见http://en.wikipedia.org/wiki/Selection_algorithm
y*i
7 楼
这个不是CLRS上的例题么
【在 u*l 的大作中提到】
: 很简单，一串数，找前k个最小的。
【在 u*l 的大作中提到】
: 很简单，一串数，找前k个最小的。
d*e
8 楼
它这里是说，如果用一个random的pivot，worse case可能是O(n^2)，
而用median of median找到一个好的pivot，需要O(n)，再应用Select找
k-th element，这里主要是花在partition上面，也是O(n)，worse case
也是O(n)，那么 (k-1) smallest/largest elements就在k-th的左/右边.
【在 l*****a 的大作中提到】
: I am confused of the explaination
: =============================================
: Direct application of the quick sort based selection algorithm
: The quick sort based selection algorithm can be used to find k smallest or
: k largest elements. To find k smallest elements find the kth smallest
: element using the median of medians quick sort based algorithm. After the
: partition that finds the kth smallest element, all the elements smaller
: than the kth smaller element will be present left to the kth eleme
而用median of median找到一个好的pivot，需要O(n)，再应用Select找
k-th element，这里主要是花在partition上面，也是O(n)，worse case
也是O(n)，那么 (k-1) smallest/largest elements就在k-th的左/右边.
【在 l*****a 的大作中提到】
: I am confused of the explaination
: =============================================
: Direct application of the quick sort based selection algorithm
: The quick sort based selection algorithm can be used to find k smallest or
: k largest elements. To find k smallest elements find the kth smallest
: element using the median of medians quick sort based algorithm. After the
: partition that finds the kth smallest element, all the elements smaller
: than the kth smaller element will be present left to the kth eleme
k*e
9 楼
linear selection
CLRS里面的
【在 u*l 的大作中提到】
: 很简单，一串数，找前k个最小的。
CLRS里面的
【在 u*l 的大作中提到】
: 很简单，一串数，找前k个最小的。
q*u
10 楼
你这个id太牛了。
鬼使神差这个，就恰好会在那种紧张的时候冒出来
问了一个问题，
里面有用到排序的复杂度。
我知道是 nlogn, 居然鬼使神差的一直用logn.....
一紧张就出错阿。
【在 u*l 的大作中提到】
: 问了一个问题，
: 里面有用到排序的复杂度。
: 我知道是 nlogn, 居然鬼使神差的一直用logn.....
: 一紧张就出错阿。
鬼使神差这个，就恰好会在那种紧张的时候冒出来
问了一个问题，
里面有用到排序的复杂度。
我知道是 nlogn, 居然鬼使神差的一直用logn.....
一紧张就出错阿。
【在 u*l 的大作中提到】
: 问了一个问题，
: 里面有用到排序的复杂度。
: 我知道是 nlogn, 居然鬼使神差的一直用logn.....
: 一紧张就出错阿。
相关阅读
为什么我的简历浏览量一直是0（包子酬谢）[Google] Arangement of blocksH1B和OPT 一问myvisajobs.com 的 smart apply 靠谱吗？投简历投的头大这两天有收到H1b receipt的吗工作了一年半了，打算开始骑驴找马OPT 和 PHD毕业时间的问题祝大家农历新年发大财啊，斑竹发包子吧pre-opt 期间可以答辩么后天有个onsite，求祝福，谢谢问下一个关于打零工的比较复杂的问题~~~~~~问一个编程语言的问题面试完后和领导吃饭点什么好Bloomberg Jan/31Google Onsite 面经很水的大龄cs master在湾区能找到啥样的工作呢?大公司的hr也会不靠谱！[Algo]dutch flag problemfacebook phone面试题