求OA2 packaging automation

楼主，我正在准备美国amazon，也越到这个题，能分享一下么

我爱喝牛奶 发表于 2021-1-4 10:44
楼主，我正在准备美国amazon，也越到这个题，能分享一下么

跟朋友讨论了下 我们觉得最好的方法是用hashset

packaging这题,我的思路:
可以先sort 一下 asc order
因为第一个是1, 第二个最大是2, 所以最后一个(第n)个理论最大只能是n. 实际上只会小于等于n,因为还要看前一个数是多少.
sort 完之后,从左往右刷
arr = min(arr[i-1] + 1, arr[i])
刷一遍就得到arr[n] 了. sort占用了NlogN复杂度[/i]

apeatapple 发表于 2021-1-4 12:01
packaging这题,我的思路:
可以先sort 一下 asc order
因为第一个是1, 第二个最大是2, 所以最后一个(第n) ...

我觉得用hashset更好O(n)

轩轩要更勤快 发表于 2021-1-4 12:29
我觉得用hashset更好O(n)

可以分享下hashset的思路吗 谢谢啦

轩轩要更勤快 发表于 2021-1-2 23:45
对！你有答案吗 我觉得是用treemap greedy思路

楼主你是西海岸的还是东边的呀, 我是ubc的

轩轩要更勤快 发表于 2021-1-4 11:43
跟朋友讨论了下 我们觉得最好的方法是用hashset

我觉得像楼下说的，用dp也是线性时间，而且我在网上看到有用数学方法做的更快，不知道hashset是怎么做

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

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

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

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

我刚刚接了加拿大亚麻new grad offer，有群吗