ebay Summer Intern OA

Ebay Intern OA大约海投出去十天左右收到的

70分钟4道题
第一题 给一个数组，判断每个数字是不是average of its neighbours, 2*arr[i] == arr[i-1] + arr[i+1]
第二题 给一个数组，peak数字arr[i] 定义为arr[i]>arr[i-1], arr[i]>arr[i+1](是边界的话大于旁边那个数字就满足是peak number), 依次从数组中删除minimum peak number, 直到数组为空, 比如[8,4,6,5]->peak为8,6,5,先删除5, 数组变成[8,4,6], 再删除6 ...
第三题 给一个matrix, 实现clockwise  90度旋转，沿main diagnal翻折, second main diagnal翻折三个功能
第四题 给一个数组，元素在[10^-9,10^9]范围内表示一个地址，[1,-5,3,2] 表示随着时间增加，依次在1, -5, 3, 2位置修建一座房子，要求返回各个时刻最长的住房区长度，比如一开始只有1位置有房子，最大住房区长度是1, 最后-5,1,2,3有房子，最大住房区长度是3(1,2,3有房子), 这个例子返回[1,1,1,3]

第四题test case都过了，submit里有两个超时了。。
求加米看看其他帖子

zengfh2006 发表于 2021-10-1 15:34
第四题用union find做应该不会超时吧？lz咋做的

我弄了个hashmap, key是房子的位置, value是pair<int,int>记录它连续的一片的最左边位置和最右边位置，每次新建一个房子i，查看hashmap[i+1]和[i-1]更新这个hashmap。我写了个循环更新, 感觉不够有效率，这个更新应该只要更新最左和最右就足够了。

lich96zz 发表于 2021-10-1 18:55
我弄了个hashmap, key是房子的位置, value是pair记录它连续的一片的最左边位置和最右边位置，每次新建一 ...

. 1point3acres.com Union Find + 路径压缩的话比你这个效率应该高很多，你这个最差会到O(N)的

第四题 Unionfind 的思路是不是说，每次新建造一个房子，就查看它左右两边是否已经有房子，如果有，就把他们union 起来，当前的最大住房区长度就是parent数组中相同元素出现的最大次数。
求大佬指点！

想借楼主的贴子问一下。我是某天半夜投的ebay的intern，结果90分钟后，还是大半夜呢，就收到拒信了。这是什么情况啊？我被系统拒了？

感谢楼主分享，看来都是一些常规题

想问下lz投的岗位是美国的吗 我貌似没在官网上找到相应的岗位

想问下楼主第二题怎么做的，写个findMinPeak的helper function然后不停call这个helper function吗？

感谢楼主分享

第四题用union find做应该不会超时吧？lz咋做的

Piiii 发表于 2021-9-30 23:20
想问下lz投的岗位是美国的吗 我貌似没在官网上找到相应的岗位

是的 差不多半个月前在linkedin上投的

xqfq 发表于 2021-10-1 01:07
想问下楼主第二题怎么做的，写个findMinPeak的helper function然后不停call这个helper function吗？

对的 问题的scale不大，brute force就可以通过了

lich96zz 发表于 2021-10-01 16:47:45
对的 问题的scale不大，brute force就可以通过了

好的好的谢谢