狗家电面

刚电话的，发帖攒人品求offer T.T

就俩问题，
数组求平均数，没啥好说的
followup 数组很大怎么办

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

得到每个host的中位数后能排除差不多一半的答案咯，嘴炮一下即可

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

假设数组size为n，找median就是找第n/2大的数。所以做法是先找一个pivot（假设是数组的第一个数）， 用这个pivot找，把小于它的数都放到左边，大于它的数都放到右边，如果正好是第n/2大，就返回。否则在数 目大的一边，继续找，对吧？

idatascience 发表于 2018-5-4 04:16
你当时答得time complexity是多少呀？

partition我随口说的平均nlgn最坏n^2，经过他的分析（在我看来已经不算hint了）平均n才对…最后他还问我是不是第一次店面谷歌，反正我觉得是跪了

这头像是leetcode的那个人吗

devilnut 发表于 2018-5-2 04:54
这头像是leetcode的那个人吗

借史蒂芬大神的光求offer

这题如果回答说用MapReduce来做也可以吗？

enderskeeper 发表于 2018-5-3 09:57
这题如果回答说用MapReduce来做也可以吗？

我不清楚诶…这些内容全都忘了…

得到每个host的中位数之后能排除一半的答案？

wang2579 发表于 2018-5-4 01:38
嗯，就是这意思…我貌似复杂度xjb说了，followup我能感觉到电话那头撇着嘴说了句you are close to right  ...

你当时答得time complexity是多少呀？