传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2091|回复: 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 | 显示全部楼层
对于facebook请不要只考虑最优解 他会刻意让你用某种解法做 只为验证你会不会这样做 比如recursive iterative 互转
回复 支持 2 反对 0

使用道具 举报

gabrielzhuyun 发表于 2015-12-14 03:31:18 | 显示全部楼层
感谢楼主分享。请问楼主为啥必须要用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.鏈枃鍘熷垱鑷1point3acres璁哄潧
感谢楼主分享。请问楼主为啥必须要用hash是最优的呢?我觉得你的做法很好啊。复杂度保证在O(n)。
如果用un ...

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

使用道具 举报

gabrielzhuyun 发表于 2015-12-14 03:47:25 | 显示全部楼层
哈哈贼 发表于 2015-12-14 03:37
.鏈枃鍘熷垱鑷1point3acres璁哄潧有可能是楼主的复杂度答错了。。。。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 | 显示全部楼层

unordered map是1. map是logn吧?应该需要内部维护一个bst
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 18:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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