狗家电面

发一个狗家电面面经，攒人品回馈地里
1. 给一个org chart, 每个人都有他的下属，下属可以为空，也可以是多个人，最后给定一个人，返回他下面所有的直接和间接下属的总数，我用hashmap和divide and conque 递归来计

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

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

记录原来的顺序，然后小组内排序，总之感觉整的挺麻烦的。我这算法的时间复杂度应该是O(nlogn) 空间是O(n)

求加米，祝大家面试好运！

第二题不能用union find吗？
对于每个数x 看x+k,x-k 是否在数组里 如果有就union 到一组即可

Tdvxufnek 发表于 2021-02-06 23:23:47
第二题也可以这样做

首先把乱序数组里面的每个 number x, 变成  的 range

二分搜索可以略过 如果维护一个区间和数字的映射 合并区间的时候数字就归并了 多o(n)space
互相加分哈

第二题也可以这样做

首先把乱序数组里面的每个 number x, 变成 [x - k, x + k] 的 range
for example k = 2, arr = [2, 9, 10]
[2, 9, 10] => [[0, 4], [7, 11], [8, 12]]
然后排序做一次区间合并 O(nlogn) + O(n)
最后扫一遍乱序数组的每个值，用区间合并后的结果来二分判断每个数加入哪个区间 O(nlogn)

时间复杂度和空间复杂度和楼主的做法都是一样的，只不过没有了记录原数组的位置小组排序那一步，可能是面试官想要的解法吧

缺米感谢

第二题用bucket应该可以

非常感谢！

第二题能不能用dfs ?     如果两个数差小于 k 就可以连接， 然后找所有connected component

rubyfrea 发表于 2021-02-06 22:30:41
第二题能不能用dfs ?     如果两个数差小于 k 就可以连接， 然后找所有connected component

这样做建图的时间复杂度就是O(n^2)，还要多做一步小组内的原数组顺序还原，您说的这个做法没有比楼主的算法更优

workworkhard 发表于 2021-2-8 15:37
第二题不能用union find吗？
对于每个数x 看x+k,x-k 是否在数组里 如果有就union 到一组即可

当时我也想到了union find，但是比如x=3 k=3 x+k = 6 x-k = 0, 假设6,0都不在数组里 但是 5,4都在 如何有效快速判别哪些可以union哪些不行，当时也没想出来，如果两两都比较的话 时间复杂度就是o(n^2)了，还请大神指点。

好多面经看不了好惨 求楼主分享个题号