FB一轮电面超级热乎

Facebook 一轮电面

今天下午刚刚面好的，及时回馈一下地里的战友：

TimeLine： 我是八月底找的朋友内推，九月初HR联系我问我什么时候电面。然后9.20下午两点面的第一轮。

这是楼主第一次技术店面，所以一开始上来特别紧张。 面试官非常友好，是一个入职3年的白哥，一直在安慰我说没事的别害怕我人很好。

第一题：给你city人数让你返回概率。这道题目在地里出现的比较多但是lc上没有。我之前一直都只刷lc所以等于是第一次做这道题目。
（举例：纽约：100人。三藩：900人， 你应该设一个function，这样return纽约的概率是10%， sf是90%）
我就是找出概率

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

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

的heapify runtime在python里的确是O(n)

补充内容 (2019-9-30 23:02):
但是面试官如果就想你再写个更intuitive O(n)的算法你就顺着他提示写就好了。
祝大家找工作顺利！ 楼主上周每天一个拒信人都傻了，现在这个二面真的又重新打了鸡血

第一题是random pick with weight的马甲吧

heapify的时间复杂度就是O(n)吧，geeksforgeeks上面有详细推导
https://www.geeksforgeeks.org/ti...uilding-a-heap/amp/

heapify的时间复杂度python是ON，java是nlgn

请问第一题是知道概率之后，根据概率返回城市吗？就是如果90%的在NY， function call的时候就有90%的概率返回NY？

我可能没太读懂，但是第一题我理解就是lc528吧
以及heapify是O(n)的...如果heapify都差到O(nlogn)，那为何不直接sort呢。

请问下大家，第二题最优解时间复杂度能到多少？

感觉我被面试官带跑了啊😂😂😂他一直问我heapify真的是ON吗。我就以为我写错了就又写了一个。哎怪自己知识点没有掌握好

鸭ssseven 发表于 2019-9-21 13:30
请问下大家，第二题最优解时间复杂度能到多少？

quick select，平均复杂度O(N), 最坏复杂度O(N^2)，就是不稳定。heap是O(NlogK)。我也说不好最优是什么

大家还是要顺着面试官的思路走，然后多准备一些解法，特别是最优解一定要分析清楚。写完代码以后不要马上run test case，自己口头先说一遍看看通不通