ebay Summer Intern OA

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记录它连续的一片的最左边位置和最右边位置，每次新建一 ...

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

第四题的题目是什么意思 我好像没看懂

请问第三题matrix是square吗？

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

无名棋脚 发表于 2021-9-30 22:47
想借楼主的贴子问一下。我是某天半夜投的ebay的intern，结果90分钟后，还是大半夜呢，就收到拒信了。这是什 ...

emm，+1，今天刚投就被拒了，请问你后来有后续嘛

vva98 发表于 2021-10-6 14:25
emm，+1，今天刚投就被拒了，请问你后来有后续嘛

后来，就在今天，又给我发了一次拒信，不知道搞什么鬼