Facebook 电面面经

昨天电面 打电话来的是个美国人 一上来他就心情不好 collabedit他也用不了 换了好几个才终于成功

期间他特别高冷 几乎我每句话都是以被他打断而结束 including 最后一句“Thank you for answering my questio

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

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

说实话我第一次见这么高冷的面试官 吓尿了 感觉必挂 觉得超级可惜  半年都无缘FB了

就当攒了个人品吧。。。

鱼吃鱼翅 发表于 2015-1-22 04:52
BST那个题，能不能用inorder traversal，用i记录扫到的值的个数，当i等于5的时候直接返回这个值就可以了， ...

BST那个题：我就是这样做的

给一个数组比如： ｛1，2，3，5，5，3，2，5｝
请返回最大数的下标。
如果最大数出现了好几次，就随机返回一个，随机是指，每个最大数的下标被选中的概率是一样的

hesha0987 发表于 2015-1-22 03:04
面试官相当高冷 他没有任何提示 也没说最优是怎样
楼主用的是inorder traversal 递归实现 所以如果已知 ...

当然不是o(1)  假象是一个单边树   只有左孩子 你必须遍历到最左边 已经走过n个节点了
复杂度要看树

yezi86 发表于 2015-1-22 02:35
BST的那道题时间就是O(N) / O(k) 吧。空间怎么优化，必须要栈啊，那就O(h)了。求指点！

面试官相当高冷 他没有任何提示 也没说最优是怎样
楼主用的是inorder traversal 递归实现 所以如果已知了K是5的话 时间空间应该是O（1）吧

fb冷冻期是半年吗？ 另外bless楼主

BST的那道题时间就是O(N) / O(k) 吧。空间怎么优化，必须要栈啊，那就O(h)了。求指点！

第一题的随机是什么意思呢？不能有额外空间那只能扫数组了吧

teedoo 发表于 2015-1-22 02:22
fb冷冻期是半年吗？ 另外bless楼主

楼主只是猜测。。一般大公司都是半年吧。。

第三题，可以BST每个Node存左子树有多少个节点，然后二分

hesha0987 发表于 2015-1-22 03:05
楼主只是猜测。。一般大公司都是半年吧。。

不是一年吗？

BST那道，我能想到 1)deleteMin 5 次 2） inorder traverse成数组，然后select kth smallest

zengm321 发表于 2015-1-22 03:25
不是一年吗？

那可能就是一年吧 反正楼主没啥念想了