脸书 电面 感觉挂了...

这题在359道题的那个大题库里。

楼主去的养老厂是哪呀 微软么

感谢分享，这题不用remove么？
如果只push， 那不就是加进list, random一个index 出来 就好了。

xiaozhuxiaozhu 发表于 2021-9-21 22:28
感谢分享，这题不用remove么？
如果只push， 那不就是加进list, random一个index 出来 就好了。

popRandom()相当于remove()，而且要求API复杂度都得是Averagely O(1)

匿名用户 发表于 2021-09-21 16:52:20
哪一题啊？不是 Random Pick with Weight/Index

下面有人找出来题号了…

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

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

匿名者 发表于 2021-9-21 16:00
楼主宽心，FB最近很缺人，bar时高时低，挂了可能也不会发拒信，然后不知道哪天把你捞起来VO
好几个朋友都 ...

这位朋友承你吉言！

不过现在是不是情况又变了，fb ng还有坑么