logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
讨论个常见的面试题:一个数据流里面随时找出median
avatar
讨论个常见的面试题:一个数据流里面随时找出median# JobHunting - 待字闺中
i*n
1 楼
method 1: keep a balanced binary search tree
method 2(theoretically work): keep a min heap, a max heap, keep it balanced
and all elements in min heap > all elements in max heap (tricky to solve
this, still figuring out)
Welcome to discuss an efficient way ha~
avatar
g*e
2 楼
method 1 能行吗？怎么保证左右子树的元素一样多？
avatar
i*n
3 楼
equal to the problem of : findKthElement in a binary search tree
using a balanced binary search tree means the median is near the top
avatar
h*w
4 楼
the method 1 assume build up balanced binary search three. If the number is
odd, then the root is median. If the number is even, I don't know~~
do not understand the 2nd solution, any one knows?
avatar
a*y
5 楼
用第二种办法吧
avl 树能保证两边节点个数一样多么

balanced

【在 i*******n 的大作中提到】
: method 1: keep a balanced binary search tree
: method 2(theoretically work): keep a min heap, a max heap, keep it balanced
: and all elements in min heap > all elements in max heap (tricky to solve
: this, still figuring out)
: Welcome to discuss an efficient way ha~
avatar
z*t
6 楼
Share a blog on this interview question:
http://codercareer.blogspot.com/2012/01/no-30-median-in-stream.
Enjoy it:)

balanced

【在 i*******n 的大作中提到】
: method 1: keep a balanced binary search tree
: method 2(theoretically work): keep a min heap, a max heap, keep it balanced
: and all elements in min heap > all elements in max heap (tricky to solve
: this, still figuring out)
: Welcome to discuss an efficient way ha~
相关阅读
紧急求助：朋友被告plagiarism要被退学STEM OPT 的EAD 拿到前可以换工作吗求内部推荐：Google, Bloomberg, Microsoft请问什么是 employee at willH1B 学校到工业界请问limo要给小费吗问个multi threading code 题，同时请问高手mutil threading 编程有什么好书，网站和教程推荐？四月提交H1B的朋友们收到reciept了么?lump sum 是什么意思, 请教relocation fee, 谢谢！报个口头offer，该从不？下周onsite，求bless 加问题Bloomberg previsor online technical assessmentbackground check,国内的Master没有显示，怎么办？Amazon on site面试， 攒RP, 求祝福弱问onsite的时候，是不是所有presentation都要做PPT？比如G家？Google Onsite见几个人？刚刚结束一个skype面试，2个小时，求祝福。工业界H1B换non－profit H1B要什么手续？能不能有点离奇的点子为什么提交简历每个公司需要race,gender信息？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。