一亩三分地论坛

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

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

facebook装逼失败之旅

[复制链接] |试试Instant~ |关注本帖
372284362 发表于 2015-10-21 14:51:48 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other在职跳槽

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

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

x
        我是on campus的面试,不过感觉应该等效于电面吧!
        在面试前的周日,fb在round table pizza组织要参加面试的这些人和各自的面试官吃饭聊天。大概四五十人,二十盘披萨吧。。。
       说说今天的面试吧!面试官因为在周日已经自我介绍过了,所以第一步主要是我来介绍自己。先坦诚地表明自己是转专业狗,基础不好,但是我很努力地学了各种CS课,也对CS充满爱。他问我比较喜欢什么职位,我说我的话可能更适合后端,不过还没想好具体的职位。这也是为什么我这么早找实习,希望早点拿到offer,这样可以尽快为夏天的实习有计划地补充新知识。他看我简历上有之前参加sdhack的项目,让我简单介绍了一下,之后开始做题了。
        第一道是leetcode原题没变化,first bad version。
You are a product manager and currentlyleading a team to develop a new product. Unfortunately, the latest version ofyour product fails the quality check. Since each version is developed based onthe previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n]and you want to find out the first bad one, which causes all the following onesto be bad.
You are given an API boolisBadVersion(version) which will return whether version is bad. Implement afunction to find the first bad version. You should minimize the number of callsto the API.
       二分搜索没啥好说的。我也不能先说用顺序搜索,然后等他follow up之后再说二分搜索对吧!要么估计说完顺序搜索,我跟fb就直接拜拜了。。。
        期间确认了做取平均数加法时会不会overflow,他说有可能。于是写了个肯定不会overflow的版本。别的实在想不出还有啥能展现的了。然后测了几个corner case,就过了。
       第二题开始了我的傻逼瞎比比之旅。其实也属于leetcode原题,sort colors,有了点小改编。
Given an array with n objects colored red,white or blue, sort them so that objects of the same color are adjacent, withthe colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2to represent the color red, white, and blue respectively.
A rather straight forward solution is atwo-pass algorithm using counting sort.
First, iterate the array counting number of0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's andfollowed by 2's.
Could you come up with an one-pass algorithmusing only constant space?
       他的变化时这样的,假如给你一个数组[9, 7, 2, 10, 6, 3, 4, 1],让你把这个数组按某种顺序排序,所有前三分之一小的数字先出现,然后是中间三分之一的和前三分之一大的数。三类数字内部的顺序不关心。同时他提供了一个API,调用这个叫做getCategory(x)的API,可以返回x属于这个数组的哪部分(L、M、H)。
       我的傻逼之处在于,我以为他让我实现这个API。以下是我瞎比比的所有内容:
       “嗯,这个的话可以直接用排序,时间复杂度是O(nlogn),我来想想有没有什么时间复杂度是O(n)的方法吧。”
       “我们可以尝试建一个平衡树,往里面一直插东西,虽然每次插入是O(logn),但是就像堆的初始化均摊之后是O(n)的,所以这个时间可能是O(n)?”这特么在说什么啊!建堆的时候首先最低一层不用讨论,这样本身需要操作的结点个数就是n/2了,我这需要插入n个元素啊!而且最重要的是建堆是下沉操作啊!越深的结点,可能下沉的最大深度约少!平衡树插入的时候,越深的结点插入的深度就越深!显然时间复杂度均摊之后也不是O(n)啊!脑子里全是周日的pizza吧。。。
       “呀!这个平衡树好像太复杂了,我再想想别的方法。哦!我们来维护四个堆吧!一个大根堆维护L,一个小根堆和一个大根堆维护M,一个小根堆维护H。”然后面试官提醒了我下看看算法复杂度,我列个式子均摊一下还是O(nlogn)。估计面试官到现在为止会觉得我是个听说个一些数据结构功能,然而并不会用的孩子吧= =
        “我来提醒你一下吧!首先我们可以扫一遍这个数组,这样就能知道每个元素标记为L还是M还是H了。同时,你也知道了各类元素的个数对吧?”
       “诶!等一下!你怎么标记的呀!啊!啊!啊!你给的这个是API,我可以直接调用的!卧槽!我以为你让我实现呢!”
       看了下表,还有7分钟,没时间写计数排序之后再follow up一个in place算法了,直接跟他说了个三指针的算法,也没时间代码实现了,只能讲讲思路,然后结合个例子具体跑一下了。最后他问了下需要扫描这个数组几轮,回答第一次完整的扫描需要过n个元素,三指针每个最坏遍历2n/3个元素,相当于一共遍历了三遍。
       最后他问我有没有什么问题问他就撤了,走之前再次为自己的傻逼行为表达了歉意。。。
       教训是毕竟转专业狗,不要太自信了,出完题之后好好过脑子再说话。如果还有下一个面试的话,不要瞎比比。。。



补充内容 (2015-10-27 04:24):
小米说由于交流不畅周五补一轮电面!不论是升中学还是升大学,刚到了新环境时总会发现自己英语水平还算不错,就没了继续学习的动力,离开那个环境时也总会发现被别人赶超落下了很多,FG两家面试终于吃到苦头了。。。

补充内容 (2015-11-5 14:46):
补面了个read4 II,感觉写得挺好,应该也是没bug,然而还是崩了。。。可能还是沟通问题,或者代码风格吧。。。

评分

6

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
clfhaha1234 发表于 2015-10-21 14:59:56 | 显示全部楼层
我怎么感觉一共遍历了2遍呢?头尾指针和在一起一遍,中间那个指针再一遍。. visit 1point3acres.com for more.

补充内容 (2015-10-21 15:01):
或者说就一遍,中间那个指针碰到右指针就算结束了吧
回复 支持 反对

使用道具 举报

 楼主| 372284362 发表于 2015-10-21 15:07:05 | 显示全部楼层
clfhaha1234 发表于 2015-10-21 14:59
我怎么感觉一共遍历了2遍呢?头尾指针和在一起一遍,中间那个指针再一遍。.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2015-10-21 15:01):

我做的是三个指针,分别指向所代表类型的元素里,第一个不在自己位置的元素,方向都是从头向尾扫。

三遍分别是第一遍长度为n的遍历把数字变成L、M、H,三遍长度为2n/3的遍历移动三个指针,总的等效于三遍了。. From 1point 3acres bbs

你是没算第一遍对于每个元素调用API把数字变成L、M、H那次?
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-21 15:39:47 | 显示全部楼层
第二题不就是SORT COLOR?.鏈枃鍘熷垱鑷1point3acres璁哄潧
直接调用API就好看属于哪一部分= =?
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-21 15:40:14 | 显示全部楼层
对的:
补充内容 (2015-10-21 15:01):
“或者说就一遍,中间那个指针碰到右指针就算结束了吧”
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-21 15:41:08 | 显示全部楼层
“期间确认了做取平均数加法时会不会overflow,他说有可能。于是写了个肯定不会overflow的版本。别的实在想不出还有啥能展现的了。然后测了几个corner case,就过了”
. from: 1point3acres.com/bbs
2分的时候一定要写: mid = low + (high-low)/2的。。。
回复 支持 反对

使用道具 举报

Jaden 发表于 2015-10-21 15:51:27 | 显示全部楼层
请问楼主对面试总体来说还有什么建议吗?过两天也要面试了,好紧张。还有求问如果保证left+right不会overflow,就可以直接写mid=(left+right)/2吧
回复 支持 反对

使用道具 举报

 楼主| 372284362 发表于 2015-10-21 15:55:39 | 显示全部楼层
Jaden 发表于 2015-10-21 15:51
请问楼主对面试总体来说还有什么建议吗?过两天也要面试了,好紧张。还有求问如果保证left+right不会overfl ...

= =我也没面过几次。。。也谈不上什么意见建议。。。我觉得就是说话之前先想想吧,估计跟他说一声“让我想会儿”,然后半分钟不说话也没什么。。。我就是一直不停地有什么说什么,基本没过下脑子,看看自己想的到底可行不可行。。。
回复 支持 反对

使用道具 举报

mmliu 发表于 2015-10-21 16:33:05 | 显示全部楼层
Jaden 发表于 2015-10-21 15:51
请问楼主对面试总体来说还有什么建议吗?过两天也要面试了,好紧张。还有求问如果保证left+right不会overfl ...
. From 1point 3acres bbs
left + (right - left)/2

补充内容 (2015-10-21 16:33):. From 1point 3acres bbs
哦,确定不会overflow的话,就层主那样就OK了。
回复 支持 反对

使用道具 举报

chuxiaoyou 发表于 2015-10-21 17:17:17 | 显示全部楼层
XQG如此谦虚,我还是先帮你升级,待我明日被干
回复 支持 反对

使用道具 举报

 楼主| 372284362 发表于 2015-10-27 04:25:06 | 显示全部楼层
小米说由于交流不畅周五补一轮电面!不论是升中学还是升大学,刚到了新环境时总会发现自己英语水平还算不错,就没了继续学习的动力,离开那个环境时也总会发现被别人赶超落下了很多,FG两家面试终于吃到苦头了。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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