一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4072|回复: 12
收起左侧

Facebook面经!(Uber Zillow MSFT

[复制链接] |试试Instant~ |关注本帖
begg930 发表于 2015-11-26 01:02:15 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
Facebook
一面:meeting room II
二面:input:二维平面上很多点,以及一个target点;output:离target最近的k个点-google 1point3acres
用quickselect做(面试官是caltech phd,声音超级温柔的台湾妹子,不过她貌似看不太懂快排的代码。。。

Zillow
一面:input:一个sorted array of integers和一个mininum threshold,求array里面大于等于minimum threshold的元素的中位数
先二分找第一个>=threshold的值,然后找个median就好,面试官提醒要考虑threshold > 所有integers的corner case

Uber面了个快排,microsoft oncampus是个中序遍历。。。。。我觉得很神奇,到现在所有的面试都是一道题,圆润的暑假全靠放水!!祝大家好运!!!

评分

1

查看全部评分

bobzhang2004 发表于 2015-11-26 01:51:12 来自手机 | 显示全部楼层
请问楼主,facebook第二题是建一个class见面放x y 和笛卡尔距离吗,然后快排吗?
回复 支持 反对

使用道具 举报

 楼主| begg930 发表于 2015-11-26 02:22:22 | 显示全部楼层
bobzhang2004 发表于 2015-11-26 01:51. From 1point 3acres bbs
请问楼主,facebook第二题是建一个class见面放x y 和笛卡尔距离吗,然后快排吗?

对的~对ddddddddddddddddddd

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| begg930 发表于 2015-11-26 05:21:54 | 显示全部楼层
bobzhang2004 发表于 2015-11-26 01:51
请问楼主,facebook第二题是建一个class见面放x y 和笛卡尔距离吗,然后快排吗?

啊 不对,不是快排,是quick select,O(n)的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-11-26 13:38:51 | 显示全部楼层
begg930 发表于 2015-11-26 05:21. 1point 3acres 璁哄潧
啊 不对,不是快排,是quick select,O(n)的

谢谢,口误, 是quick select
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-27 00:01:23 | 显示全部楼层
begg930 发表于 2015-11-26 02:22
对的~对ddddddddddddddddddd

求问 quick select是什么意思呀。。这题我只会用最小堆。。
回复 支持 反对

使用道具 举报

 楼主| begg930 发表于 2015-11-27 00:09:18 | 显示全部楼层
小A要当码农 发表于 2015-11-27 00:01
求问 quick select是什么意思呀。。这题我只会用最小堆。。

是快排的思想,partition之后返回的数组,左半部分全部小于右半部分,数数有几个,够k了在左边递归找前k个,不够k在右边递归找不够的个数。。。。不太懂的话可以看这个https://www.youtube.com/watch?v=aOhyCdxGJvY

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-27 00:33:38 | 显示全部楼层
begg930 发表于 2015-11-27 00:09
是快排的思想,partition之后返回的数组,左半部分全部小于右半部分,数数有几个,够k了在左边递归找前k ...

额,多谢告知啦, 但是这个方法不能保证O(n)呀? 最坏情况还是O(n^2)吧?
回复 支持 反对

使用道具 举报

 楼主| begg930 发表于 2015-11-27 01:14:52 | 显示全部楼层
小A要当码农 发表于 2015-11-27 00:33
额,多谢告知啦, 但是这个方法不能保证O(n)呀? 最坏情况还是O(n^2)吧?

算法导论上证明的是O(n)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-27 02:00:38 | 显示全部楼层
begg930 发表于 2015-11-27 01:14. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
算法导论上证明的是O(n)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
嗯嗯,应该是average case O(n), 刚写了一下,感觉好容易出bug。。。 多谢楼主的分享啦,
回复 支持 反对

使用道具 举报

caffery24 发表于 2016-1-6 00:16:08 | 显示全部楼层
begg930 发表于 2015-11-27 00:09
是快排的思想,partition之后返回的数组,左半部分全部小于右半部分,数数有几个,够k了在左边递归找前k ...

楼主这个题是不是其实是一个加强版的find kth largest number
回复 支持 反对

使用道具 举报

 楼主| begg930 发表于 2016-1-7 21:54:21 | 显示全部楼层
caffery24 发表于 2016-1-6 00:16
楼主这个题是不是其实是一个加强版的find kth largest number

是是是是是是是是是是是是是是

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

哈哈贼 发表于 2016-1-29 06:24:43 | 显示全部楼层
好羡慕楼主,我也好像要FB的offer
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-14 03:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表