twitter 新鲜店面

报一个新鲜的店面， 是一个印度的小哥， 全程非常友好， 互动很多。聊得很开心。
有数字1， 2， 3， 40，3， 2 。。。。 一个一个的进来
设计一个class能够实现下面的function
1） add(0)
2） getMean（）
3） getMedian（）

第一轮， 先是问一下想用什么data structure来弄那个median的， 我们 go t

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

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

ep track of frequency.

之后就是问小哥的问题, team怎么样, project怎么样, 时间超时了一些, 小哥直接说HR 会联系onsite的安排了。

请问OA过了多久联系你的 校招还是社招 new grad？

suda_adus 发表于 2020-3-14 06:08
请问OA过了多久联系你的 校招还是社招 new grad？

是社招， 朋友内推的， 整个过程很快， 内推20分钟HR 就联系了， 然后就是HR面， Hiring Manager面，之后大概一天就约了店面。

suda_adus 发表于 2020-3-14 06:08
请问OA过了多久联系你的 校招还是社招 new grad？

然后没有做OA， 也没有给我发过

谢分享。一个问题，这都是一轮店面45m内做的？一共几道题呀？

顺便求求lz能否分享下188 里面的内容，积分不够看不了。。。

notelonmusk 发表于 2020/03/15 00:27:27
谢分享。一个问题，这都是一轮店面45m内做的？一共几道题呀？

顺便求求lz能否分享下188 里面的内容，积分不够看...

嗯嗯，都是一轮店面里做的。面试总共1个小时。聊天15分钟。做题45分钟。之后又聊超时了。一共就是一道题，但是三个功能，getmedian 先是让你想可能的data structure。然后实现三个功能和我最后写的那个frequency array的那个方法

然后我188里的内容跟po出来的都一样。不知道为啥有的隐藏了，可能手抖点的？

多谢已加米！
问一下那个frequency array，应该是一个cumulative frequency吗？动态更新的话需要一个BIT?

convexopt 发表于 2020-3-15 04:17
多谢已加米！
问一下那个frequency array，应该是一个cumulative frequency吗？动态更新的话需要一个BIT?

谢谢! 对的， 是一个cumulative frequency，index表示进来的数字是几， 找median的时候就是从头数总共进来的数的一半， 数到了的那个数就是median了。

就是array[i]++， 不太明白动态更新需要一个BIT是什么意思？ array的大小是initiate的时候就定的。 一个int takes two byte。

srigter 发表于 2020-3-15 06:49
谢谢! 对的， 是一个cumulative frequency，index表示进来的数字是几， 找median的时候就是从头数总共进 ...

比如范围是[0,4], add 0,0,1,1,1,4,4, frequency是 [2,3,0,0,2], cumulative frequency是[0,2,5,5,5,7], count/2=3，那可以二分搜索出中位数是1。但是维护这个cumulative frequency array的成本是O(k) (范围是[0,k))。BIT指的是binary indexed tree，可以logk更新，查中位数还是需要二分，成本是(logk)^2