FB 实习一面

11月面的,当时找学长退的，很快就收到消息了。然后recruiter安排的面试。

面试是一个三哥，楼主面试在这以后面试无数场，但这场尤其记忆犹新，这个三哥态度最差，各种push.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

对于facebook请不要只考虑最优解 他会刻意让你用某种解法做 只为验证你会不会这样做 比如recursive iterative 互转

感谢楼主分享。请问楼主为啥必须要用hash是最优的呢？我觉得你的做法很好啊。复杂度保证在O(n)。
如果用unordered_map, 似乎无法做到让key（column number）是排好序的，如果用map，那么自带的排序功能会有O(w log w)的复杂度（w是宽度，worst case 可以成为n），不是加大了复杂度么？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

楼主复杂度答错了是挺可惜的，被面试官抓到把柄了。。。

先算宽度最优吧，hash的话复杂度是O（nlgn）？因为（ordered）map插入的复杂度是o（lgn）？

zjh08177 发表于 2016-1-12 02:54
先算宽度最优吧，hash的话复杂度是O（nlgn）？因为（ordered）map插入的复杂度是o（lgn）？

hash是o(1)  呀

哈哈贼 发表于 2016-1-12 19:10
hash是o(1)  呀

unordered map是1. map是logn吧？应该需要内部维护一个bst

不需要吧。。key都是连续的，只要根据unordered_map.size就能知道有几个entry然后根据key映射一下index就好了。