Two Sigma GHC onsite

abby3

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 abby3 于 2019-10-8 06:24 编辑

给一个GHC的

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

N), 求更好的解法。

最后求大米看面经，给我加大米，不会减你的大米的。祝大家面试顺利！

pxpxpxpx

可以把shuffle换成 random一个index再remove
lz怎么已经知道挂了？

Glaces

arraylist remove是O(n) 不能取head要取tail吧

abby3 · 2019-10-10 02:05:31

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

abby3 · 2019-10-10 02:10:15

Glaces 发表于 2019-10-9 00:50
arraylist remove是O(n) 不能取head要取tail吧

取TAIL也是O(N), 不过总时间是o(n)+o(n)+o(n) = o(n)

pxpxpxpx · 2019-10-10 02:21:32

abby3 发表于 2019/10/10 02:05:31

random index 是O(N)时间更久吧。他们给我写信了，就说挂了。

难道不是O(1)吗？

abby3 · 2019-10-10 02:34:38

piggy1228 发表于 2019-10-10 02:21
难道不是O(1)吗？

random an index是O(1),但你还是GET这个ELEMENT，就是O(N），还有不能重复的问题，如是DELETE了会更麻烦的。

pxpxpxpx · 2019-10-10 03:11:36

abby3 发表于 2019/10/10 02:34:38
random an index是O(1),但你还是GET这个ELEMENT，就是O(N），还有不能重复的问题，如是DELETE了会更麻烦的。

我对java不了解可以把index的数字和last element互换然后pop last吗？

Metaverse · 2022-10-20 12:32:02

random取index，比如【0，n】里取一个，取出的值和最后一个元素互换，下次从【0，n-1】里取就行