推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3928|回复: 12
收起左侧

Facebook面经!(Uber Zillow MSFT

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

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

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

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

x
Facebook
一面:meeting room II
二面:input:二维平面上很多点,以及一个target点;output:离target最近的k个点
用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 来自手机 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
请问楼主,facebook第二题是建一个class见面放x y 和笛卡尔距离吗,然后快排吗?
回复 支持 反对

使用道具 举报

 楼主| begg930 发表于 2015-11-26 02:22:22 | 显示全部楼层
关注一亩三分地微博:
Warald
bobzhang2004 发表于 2015-11-26 01:51
请问楼主,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
是快排的思想,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)
. more info on 1point3acres.com
嗯嗯,应该是average case O(n), 刚写了一下,感觉好容易出bug。。。 多谢楼主的分享啦,
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| begg930 发表于 2016-1-7 21:54:21 | 显示全部楼层
caffery24 发表于 2016-1-6 00:16
楼主这个题是不是其实是一个加强版的find kth largest number
. 鍥磋鎴戜滑@1point 3 acres
是是是是是是是是是是是是是是

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-27 02:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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