脸书 电面 感觉挂了...

上来基本一句寒暄都没有，直接做题
让实现一个RandomContainer
                 push(), popRandom

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

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

...同时收到了狗的OA...真的有点想withdraw不想去卷了..好想进养老厂躺一段时间再跳槽算了

楼主宽心，FB最近很缺人，bar时高时低，挂了可能也不会发拒信，然后不知道哪天把你捞起来VO
好几个朋友都电面没做出来也VO了，blind上也有说VO面得很烂最后拿到顶包的

一个链表存数据
一个list存各节点顺序，push就放到最后
poprandom就随机取一个数，先在链表里面删除，然后再list里面把该位置和最后一个swap，然后pop，
两个都是average O(1)
原题

这题确实是题库吧
不过我总感觉依赖于碰到原题不是个办法啊 还是理解了好 也不用演了

虽然但是…我感觉这个题是题库里的

今天失学了吗 发表于 2021-9-21 16:48
虽然但是…我感觉这个题是题库里的

哪一题啊？不是 Random Pick with Weight/Index

谢谢分享。楼主能描述的再具体点吗？popRandom()这个函数有什么具体要求吗？是同概率还是weighted的pop？

匿名者 发表于 2021-9-21 16:54
谢谢分享。楼主能描述的再具体点吗？popRandom()这个函数有什么具体要求吗？是同概率还是weighted的pop？

等概率的

三吧林. Insert Delete GetRandom O(1)

匿名者 发表于 2021-9-21 19:55
等概率的

那应该是这题的变种： https://leetcode.com/problems/insert-delete-getrandom-o1/
想让popRandom()是O(1)的话，跟list的最后一位swap下再pop，同时用hashmap辅助记录下对应的value:idx应该就可以了把。不知道我理解的对不对。

peter_jun 发表于 2021-9-21 15:58
三吧林. Insert Delete GetRandom O(1)

积分不够，看不到你隐藏了啥，根据描述猜的

peter_jun 发表于 2021-9-21 16:58
三吧林. Insert Delete GetRandom O(1)

我竟然没刷到过这题..那就是自己菜没办法了