上周一FB纽约on site跪了，疑似新题

电面情况见这个帖子， 面完了当天就知道过了，然后约onsite。
onsite那天晚上没睡好，所以精神不太好。被问了一题rolling median （不是running，是rolling，就是最近的k个元素的median）。后来看了看好像标准做法是heap，我一时有点糊涂没想到这个，说的是弄两颗平衡二叉树，然后每次要删除一个数，增加一个数，删除的话查查它在左边还是右边的树，找到了删除，增加的话，先比较L.max 和 R.min 和这个数的大小，看看加到左边的树还是右边的树，两颗树size差距超过1了再rebalance 一下。这一步的复杂度是O（logn）然后再回答median。这个时候要分奇数还是偶数看，如果L.size > R.size, 那就是L.max, R.size > L.size 就是R.min, 否则是 (R.min + L.max) /2。整体的复杂度是O(logn)的，我感觉即使是heap好像也是logn，但是可能heap比较简洁一些？

还有一题是如果要写一个chrome extension，可以在linkedin 上显示可能的 facebook 账号，要怎么做。

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

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

求打赏，求打赏，为啥大家都爱设置188，想看帖 ಥ‿ಥ

minggo 发表于 2019-9-16 09:56
楼主，rolling median 这题能否讲详细些？从你的描述是用两个 heap，一个最大堆，一个最小堆，然后取顶部二 ...

我没有回答heap，主要是没想到怎样在heap里面删除一个任意的数

面试官有没有说chrome extension可以access哪些内容？要显示的是谁的facebook账号？是浏览者的还是html里面显示的profile的人的？

楼主，rolling median 这题能否讲详细些？从你的描述是用两个 heap，一个最大堆，一个最小堆，然后取顶部二者的平均值？

188是地主设的

charlieyan 发表于 2019/09/16 05:30:15
188是地主设的

原来是这样 ... 还差20多分 ...

请问第二题是system design吗，FB new grad也要面system design吗

bearxiong2017 发表于 2019/09/16 08:11:55
请问第二题是system design吗，FB new grad也要面system design吗

我不是new grad 啦

看样子是想让你说API需要access token?

everending 发表于 2019/09/16 08:38:59
看样子是想让你说API需要access token?

哎呀，没想到！其实用过的

minggo 发表于 2019/09/16 09:56:52
楼主，rolling median 这题能否讲详细些？从你的描述是用两个 heap，一个最大堆，一个最小堆，然后取顶部二者的平均值？

LZ好像说的是LC480