Snap 电面

聊了一会儿简历，然后做题

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

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

觉得有用帮忙加个米吧，大家找工顺利！

感觉蛮不错的一道题。用简单的一个链表，或一个array，应该只会被认为是暴力解。我想想

有想法了。三个数据结构可以达到效果：一个hashmap，一个array，再加一个count

三个操作都是O(1)负责度。

当remove是，array会出一个hole。这个时候把最后一个元素移回去。（有点heap调整或quicksort交换的味道）

dennyzhang007 发表于 2019-10-8 02:15
有想法了。三个数据结构可以达到效果：一个hashmap，一个array，再加一个count

三个操作都是O(1)负责度。

99%同意。 应该用 list 而不是 array。

请问楼主面的哪个office?

dennyzhang007 发表于 2019-10-8 15:15
有想法了。三个数据结构可以达到效果：一个hashmap，一个array，再加一个count

三个操作都是O(1)负责度。

array需要resize怎么办？

longvision 发表于 2019-11-3 12:57
array需要resize怎么办？

380. Insert Delete GetRandom O(1)

嗯，如上面朋友说的。应该是list(链表), 而不是array

dennyzhang007 发表于 2019-11-3 13:34
380. Insert Delete GetRandom O(1)

嗯，如上面朋友说的。应该是list(链表), 而不是array

链表怎么get random呢？

longvision 发表于 2019-11-3 00:41
链表怎么get random呢？

利口题号都给你了，自己花点时间吧。

longvision 发表于 2019-11-2 23:41
链表怎么get random呢？

reservoir sampling