May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

FB 实习一面

[复制链接] |试试Instant~ |关注本帖
哈哈贼 发表于 2015-12-13 04:50:29 | 显示全部楼层 |阅读模式

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

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

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

x
11月面的,当时找学长退的,很快就收到消息了。然后recruiter安排的面试。
面试是一个三哥,楼主面试在这以后面试无数场,但这场尤其记忆犹新,这个三哥态度最差,各种push.
题目是leetcode Binary TreeVertical Order Traversal . 当时面的时候还没有这道题。楼主上来有点懵,再加上三哥的原因,有点紧张。
做的时候没有用hash(后面和同学讨论了一下hash是最优的).
楼主先算了tree的宽度,然后建了一个宽度这么长的vector,然后用BFS.
最后那个三哥让我算求树宽度那个函数的复杂度我说O(logn),他说worstcaseO(N),然后问问问题就88了。

三天之后收到据信。 。。。

评分

4

查看全部评分

nemoleoliu 发表于 2015-12-13 05:10:15 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
对于facebook请不要只考虑最优解 他会刻意让你用某种解法做 只为验证你会不会这样做 比如recursive iterative 互转
回复 支持 2 反对 0

使用道具 举报

gabrielzhuyun 发表于 2015-12-14 03:31:18 | 显示全部楼层
关注一亩三分地微博:
Warald
感谢楼主分享。请问楼主为啥必须要用hash是最优的呢?我觉得你的做法很好啊。复杂度保证在O(n)。
如果用unordered_map, 似乎无法做到让key(column number)是排好序的,如果用map,那么自带的排序功能会有O(w log w)的复杂度(w是宽度,worst case 可以成为n),不是加大了复杂度么?
回复 支持 反对

使用道具 举报

 楼主| 哈哈贼 发表于 2015-12-14 03:37:41 | 显示全部楼层
gabrielzhuyun 发表于 2015-12-14 03:31
感谢楼主分享。请问楼主为啥必须要用hash是最优的呢?我觉得你的做法很好啊。复杂度保证在O(n)。
如果用un ...

有可能是楼主的复杂度答错了。。。。hash写起来比较简单吧。。。不过那个三个总体来说就是凶巴巴的感觉很差
回复 支持 反对

使用道具 举报

gabrielzhuyun 发表于 2015-12-14 03:47:25 | 显示全部楼层
哈哈贼 发表于 2015-12-14 03:37
有可能是楼主的复杂度答错了。。。。hash写起来比较简单吧。。。不过那个三个总体来说就是凶巴巴的感觉很 ...

楼主复杂度答错了是挺可惜的,被面试官抓到把柄了。。。
回复 支持 反对

使用道具 举报

zjh08177 发表于 2016-1-12 15:54:37 | 显示全部楼层
先算宽度最优吧,hash的话复杂度是O(nlgn)?因为(ordered)map插入的复杂度是o(lgn)?
回复 支持 反对

使用道具 举报

 楼主| 哈哈贼 发表于 2016-1-12 19:10:52 | 显示全部楼层
zjh08177 发表于 2016-1-12 02:54
先算宽度最优吧,hash的话复杂度是O(nlgn)?因为(ordered)map插入的复杂度是o(lgn)?

hash是o(1)  呀
回复 支持 反对

使用道具 举报

zjh08177 发表于 2016-1-13 02:34:38 | 显示全部楼层
.鏈枃鍘熷垱鑷1point3acres璁哄潧
unordered map是1. map是logn吧?应该需要内部维护一个bst
回复 支持 反对

使用道具 举报

 楼主| 哈哈贼 发表于 2016-1-13 02:43:20 | 显示全部楼层
不需要吧。。key都是连续的,只要根据unordered_map.size就能知道有几个entry然后根据key映射一下index就好了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-27 23:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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