亚麻 SDE1 OA

新鲜的亚麻OA，麻烦各位加点米。115分钟，2道题。第二题没做出来。感觉有点可惜，也希望各位能指教一下

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

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

2. 给一个int array, 长度是1 <= length <= 10**5, 然后数字大小是 -10**9 <= x <= 10**9。求前k大的subsequence sum。比如：[-1, 2, 3, 4]，前3大就是[2+3+4, 4+3, 4+2] = [9, 7, 6]。 0 < k <= min(2**length, 2000)

我先sort了这个array。用了一个heap保存当前最大的k个combination sum，然后没一个值判断和之前每一个combination的sum是不是能加入，以及这个值本身是不是能加入heap。最后5个test cases timeout了。实在想不到别的什么办法。麻烦指教。

在Stackoverflow找到有人问：https://stackoverflow.com/questi ... -top-k-sum-elements

出结果了吗亲

匿名者 发表于 2022-5-19 11:22
出结果了吗亲

刚收到VO的邀请。还不知道是什么时间

请问楼主，能再解释一下 “我把所有router的开始和结尾放在一个heap” 是具体怎么做的吗？感谢！

匿名者 发表于 2022-6-12 21:41
请问楼主，能再解释一下 “我把所有router的开始和结尾放在一个heap” 是具体怎么做的吗？感谢！

类似meeting room吧。比如router在3，范围是2，那么我的heap就要放俩值，(1, START), (6, END)。因为1是3-2，然后START表示是开始点。6是3+2+1，END表示是结束点。就这样