真慫阿, 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.....
: 一紧张就出错阿。
相关阅读
公司面试情商实战题intern好还是contractor好？给大家提供一些工作信息google 一题CareerCup 13.9的solution有memory leak包子答谢！！公司file的H1B 现在under review，自己能办加急吗？再发帖求big big big bless报一个embedded software engineer的offer急求skype面试经验H1b生效前有一两个月黑着 可行不？OPT extension 求 bless[Postdoc Job in Biophotonics] Johns Hopkins (转载)急：grace period若提交H1B的申请，还可以cap-gap？google 一道dp 题请教两个题今天听 Principle Architect 们的seminar如果接受了offer 办H1B transfer期间 可以再reject这个offer么求指教做测试开发的如何转纯开发？？opt等的快疯了诚恳请求JOB TITLE帮助！复杂背景, 多谢大家了！