一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2316|回复: 12
收起左侧

Facebook面经!(Uber Zillow MSFT

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

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

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

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

x
Facebook.鏈枃鍘熷垱鑷1point3acres璁哄潧
一面:meeting room II. 1point 3acres 璁哄潧
二面:input:二维平面上很多点,以及一个target点;output:离target最近的k个点
用quickselect做(面试官是caltech phd,声音超级温柔的台湾妹子,不过她貌似看不太懂快排的代码。。。

Zillow. 鍥磋鎴戜滑@1point 3 acres
一面:input:一个sorted array of integers和一个mininum threshold,求array里面大于等于minimum threshold的元素的中位数
先二分找第一个>=threshold的值,然后找个median就好,面试官提醒要考虑threshold > 所有integers的corner case
.1point3acres缃
Uber面了个快排,microsoft oncampus是个中序遍历。。。。。我觉得很神奇,到现在所有的面试都是一道题,圆润的暑假全靠放水!!祝大家好运!!!. more info on 1point3acres.com

评分

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. Waral 鍗氬鏈夋洿澶氭枃绔,
请问楼主,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
啊 不对,不是快排,是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
. more info on 1point3acres.com是快排的思想,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)

嗯嗯,应该是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
. more info on 1point3acres.com
是是是是是是是是是是是是是是

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 03:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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