Expedia Intern OA

今天考了Expedia SDE Intern的OA，第一题卡住了想问问大家有没有会做的（楼主太菜了
第一题：给你一个array和一个k，k代表可以做几个operations。每一个o

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

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

nsactions，从左往右读，不能出现total小于0的情况，要求怎么transaction最长。

请问楼主 expedia 是 sde 的 intern 嘛?

Guitang 发表于 2022-9-20 22:40
请问楼主 expedia 是 sde 的 intern 嘛?

是的～zszszs

请问选择题是什么语言写的啊

第一题就是找最大的k个数加起来就行了，因为你想象如果想取那k个最大的数，就每次从两边开始取，取最左边的就保留右边，取最右边的就保留左边，最后一定能取到所有。当时做的时候也卡了下，但跑了几个例子就发现这个思路了。

请问oa给了多久以内做掉呀

请问一下那个strength test是什么题呀？谢谢！

AirsonLeo 发表于 2022-9-24 13:31
第一题就是找最大的k个数加起来就行了，因为你想象如果想取那k个最大的数，就每次从两边开始取，取最左边的 ...

请问第一题，为什么不用考虑第二大的数字和第三大的数字在第一大的数字的两边呢？discard 没到k次是允许的吗？比如他那个例子
[ 4, 6, -10, -1, 10, -20] k = 4
先选10， 和左边，因为6在左边，arr变成[ 4, 6, -10, -1]
然后选6，和左边[ 4,]
然后按照排序大小该选4 了，
但选完4 之后，这个数列就没有了，虽然说partition discard 可以是empty，但是k没有达到4 次，这还能算OK吗

匿名用户 发表于 2022-10-13 15:27
请问第一题，为什么不用考虑第二大的数字和第三大的数字在第一大的数字的两边呢？discard 没到k次是允许 ...

不是优先选最大的数，而是优先选k个最大的数中最靠近两边的。比如按照你的例子，第二第三大的数在最大的两边，那么就先选第三大的，再取左边（或先选第二大的，再取右边）。例如[4, 6, -10, -1, 10, --20]，已知最大的4个是4， 6， -1， 10， 那么就按顺序选10，去左，选-1，去左，选4，去右，最后选6。

其实这个思路不是传统greedy那样，你在不知道结果的情况下，每次都有更好的选择；而是你已经知道答案了，知道最大的k个数是什么，然后根据这k个数的结果（位置）反推寻找的过程。