c***n
发帖数: 921 | 1 MS 电面
给定一个random数组 和一个函数 f。 f以一个数组为input，输出 median of this 数
组。f takes O（n）time
怎样得出1st quantile of a given array
提示用2次f
我没答上来。怎么做啊？ |
m********l
发帖数: 4394 | 2 啊?
不就是median of median?
【在 c***n 的大作中提到】
: MS 电面
: 给定一个random数组 和一个函数 f。 f以一个数组为input，输出 median of this 数
: 组。f takes O（n）time
: 怎样得出1st quantile of a given array
: 提示用2次f
: 我没答上来。怎么做啊？
|
c***n
发帖数: 921 | 3 具体？
【在 m********l 的大作中提到】
: 啊?
: 不就是median of median?
|
m********l
发帖数: 4394 | 4
你用啥语言?
f的parameter type 是啥?
【在 c***n 的大作中提到】
: 具体？
|
O******n
发帖数: 1505 | 5 get median of array
scan all entries below median to form a new array
get median of new array
right?
【在 c***n 的大作中提到】
: MS 电面
: 给定一个random数组 和一个函数 f。 f以一个数组为input，输出 median of this 数
: 组。f takes O（n）time
: 怎样得出1st quantile of a given array
: 提示用2次f
: 我没答上来。怎么做啊？
|
r*******y
发帖数: 1081 | 6 How can f take O(n) time to find the median ?
【在 c***n 的大作中提到】
: MS 电面
: 给定一个random数组 和一个函数 f。 f以一个数组为input，输出 median of this 数
: 组。f takes O（n）time
: 怎样得出1st quantile of a given array
: 提示用2次f
: 我没答上来。怎么做啊？
|
m********l
发帖数: 4394 | 7 magic
【在 r*******y 的大作中提到】
: How can f take O(n) time to find the median ?
|
c***n
发帖数: 921 | 8 悲剧了。这么简单都没答上来。
【在 O******n 的大作中提到】
: get median of array
: scan all entries below median to form a new array
: get median of new array
: right?
|
r*******y
发帖数: 1081 | 9 more details or link ? thanks
【在 m********l 的大作中提到】
: magic
|
f****4
发帖数: 1359 | 10 clrs 9.3
【在 r*******y 的大作中提到】
: more details or link ? thanks
|
m****i
发帖数: 650 | 11 quick sort to find the nth element in an array in O(n). Check the hack
google interview from MIT |
