boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 优步面试,哎。。。
相关主题
请教leetcode一道题目 Median of Two Sorted Arrays
刷题刷到没自信了
Quick selection for k unsorted arrays
find median for k sorted arrays
找2个sorted array中的第K小的元素,有O(lgn)方法吗?
问个面试题
哪里有讲k-way merge的?
[算法] unsorted array
找第K个最小的元素
请问两道题
相关话题的讨论汇总
话题: array话题: median话题: 个数话题: binary话题: leetcode
进入JobHunting版参与讨论
1 (共1页)
m******g
发帖数: 100
1
上来就一道median of M sorted array.
以前做过,不过忘了。是不是太弱了。。
h*********i
发帖数: 2605
2
告他性骚扰

【在 m******g 的大作中提到】
: 上来就一道median of M sorted array.
: 以前做过,不过忘了。是不是太弱了。。

m******g
发帖数: 100
3
哈哈:)
l********s
发帖数: 276
4
Leetcode 上是两个厘米找median, 现在都是m个里面找median了。看了bar又高了?
l********r
发帖数: 221
5
leetcode hard题呀,M array中找就更难啦。
是on-site还是店面题目呀?

【在 m******g 的大作中提到】
: 上来就一道median of M sorted array.
: 以前做过,不过忘了。是不是太弱了。。

h*********n
发帖数: 11319
6
cao 太变态了

【在 m******g 的大作中提到】
: 上来就一道median of M sorted array.
: 以前做过,不过忘了。是不是太弱了。。

m******g
发帖数: 100
7
就是个电话面试。三哥。
l********r
发帖数: 221
8
三哥就是狠呀,就是想turn down你的节奏。电面有次遇到个三姐 尼玛那个水平差呀,
答得再好她也搞不懂 最好还把我turn down了

【在 m******g 的大作中提到】
: 就是个电话面试。三哥。
g****1
发帖数: 6
9
是map组的面试吗?如果是的话,我去onsite时候和你碰到过一样的题目,应该是同一
个人
抛开三哥什么不说,我觉得这道题还是挺好的,如果你会从两个array里找到medium,
那从m个里面找我感觉思路其实差不多,而且这题目我个人认为他并不是要你把code写
得bug free,只要写歌大概思路没错应该就可以
t*****n
发帖数: 2578
10
我靠
两个里找我都找不出。m个里咋找?
相关主题
find median for k sorted arrays
找2个sorted array中的第K小的元素,有O(lgn)方法吗?
问个面试题
哪里有讲k-way merge的?
进入JobHunting版参与讨论
l********e
发帖数: 103
11
请问一下什么思路啊?

【在 g****1 的大作中提到】
: 是map组的面试吗?如果是的话,我去onsite时候和你碰到过一样的题目,应该是同一
: 个人
: 抛开三哥什么不说,我觉得这道题还是挺好的,如果你会从两个array里找到medium,
: 那从m个里面找我感觉思路其实差不多,而且这题目我个人认为他并不是要你把code写
: 得bug free,只要写歌大概思路没错应该就可以

a*******g
发帖数: 1221
12
这个怎么找?我知道两个里找median的话有类似binary search,leetcode原题。
M怎么找?用个heap?类似merged sort之类的,但估计肯定有更快的。
W***o
发帖数: 6519
13
把全部lists 放进heap 里头?


: 我靠

: 两个里找我都找不出。m个里咋找?



【在 t*****n 的大作中提到】
: 我靠
: 两个里找我都找不出。m个里咋找?

l********n
发帖数: 9
14
特密我只会找一个的 十个字
t*****n
发帖数: 2578
15
言归正传
m个到底咋做?
2个的leetcode有解答
1个的我自己会二分法
m个的大家教我一下
t*********l
发帖数: 566
16
我有个算法。。。有点笨哈。。
对整个int 空间binary search
low = -2^31 high = 2^31
将每个mid 的值放到每个array里去binary search,返回最接近的小于它的index, 记
作M_i. 这个过程是M个Log(S_i), S_i 是每个array长度。
将{M_i}加起来,看是否和N/2 相等,N是总的个数。
如果大了, 说明mid对应的值过大,high = mid; 不然,说明mid对应值过小,往右边
找。
32 * M * log(S).
32 是因为,二分找最多32次。
不知道对不对。
a**********6
发帖数: 4
17
第一步找出m个中位数里面最小的,把最小的那个array删去前一半(中位数肯定不在这
里面),假设删去k个数,现在问题变成找中位-k数;
第二步找每个array里,(中位-k)/m位置上的数,共有m个,这里面最小的,删这个
array一半;
第三步。。。
最后找到中位数

【在 t*****n 的大作中提到】
: 言归正传
: m个到底咋做?
: 2个的leetcode有解答
: 1个的我自己会二分法
: m个的大家教我一下

t*****9
发帖数: 569
18
我当年被考了道 Median of M un-sorted Arrays。出题的是个老中,还是校友,
转行cs的。见习的是个小中。当时我那个尴尬啊。。

【在 m******g 的大作中提到】
: 上来就一道median of M sorted array.
: 以前做过,不过忘了。是不是太弱了。。

f*****i
发帖数: 835
19
Unsorted其实简单些,放一起就好了

【在 t*****9 的大作中提到】
: 我当年被考了道 Median of M un-sorted Arrays。出题的是个老中,还是校友,
: 转行cs的。见习的是个小中。当时我那个尴尬啊。。

l*3
发帖数: 2279
20
这题应该这么做:
对每个array,只需要确认它里面是否有一个元素是median就行,这是简单的,用
binary search做如下的事情:
对于某个待检查的元素,利用binary search找出这M个数组中,每个数组内比它小和比
它大的元素个数,如果是median的话,就必须满足比它小的个数是小于N/2的,而比它
大的是大于N/2的。然后根据个数来判断这个待检查的元素是小了还是大了,这样就可
以在外层循环用binary search来继续判断。
对每个array都做如上的事情,最后总的cost是 O(M * log(N)^2),其中N是M个数组里
size最大的那个(或者你也可以认为是总的元素个数,这个不会影响asymptotic cost
u****p
发帖数: 526
21
三哥估计给他答案也看不懂,专门来黑人的吧

【在 m******g 的大作中提到】
: 就是个电话面试。三哥。
1 (共1页)
进入JobHunting版参与讨论
相关主题
请问两道题
昨天有人讲过的啥de啥的是怎么回事有人知道么
re: 面试归来,上面经回馈各位战友
问个amazon面试题
问一个merge k sorted array的问题
被Facebook的面试的一道题目难倒了
弱问,啥是median of an array?
两个sorted array找median
一个算法题:Selecting median of three sorted arrays
Amazon二面
相关话题的讨论汇总
话题: array话题: median话题: 个数话题: binary话题: leetcode