Google 电面第二轮

可能是第一轮发挥的不好，又安排了一轮电面

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

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

状态比上一次感觉好多了，希望能有onsite～

8871052 发表于 2018-11-8 23:56
lz 能解释一下 什么数据结构 GetRandom？

Leetcode上面的一道题，380

lz 能解释一下 什么数据结构 GetRandom？

楼主，第一题最后是不是要用heap对频率排序呀？有O(n)的方法吗

vividlau 发表于 2018-11-12 03:30
楼主，第一题最后是不是要用heap对频率排序呀？有O(n)的方法吗

两个办法：
1. 先建立hashtable，key是number，value是number的freqency。 然后维护一个长度为3的最小堆，过一遍所有的hashtable里的item。这个方法，时间复杂度O（n），空间复杂度O（n）
2. sort这个数组，然后再iterate sorted number，维护一个长度为3的最小堆，这个方法时间复杂度是O（nlogn），空间复杂度（O（1））

Trade-off：
1. 最简单的情况下，是时间复杂度和空间复杂度的trade-off。但是这是建立在排序是不稳定排序的基础上（比如堆排序）。系统自带的TimSort，最差空间复杂度是O（n）
2. 如果number很长，超过系统自带内存，该问题只能用外排序和hashtable解决
3. 综上两点，我觉得方法1 比 方法2要好。

补充内容 (2018-11-12 03:42):
方法1 的 O（n），实际上时间是，n+ n * (log3) ， 第一个n是填hashtable 第二个nlog3是维护heap

amcw7777 发表于 2018-11-12 03:40
两个办法：
1. 先建立hashtable，key是number，value是number的freqency。 然后维护一个长度为3的最小堆 ...

对对，heap的长度为3，感谢楼主！