狗家电面

yiliaobailiao 发表于 2021-2-9 23:31
能问一下第一题的输入格式吗？为啥要用分治法呢？

这题的输入格式如下(我就用python来表示了哈)：
{'Bob': ['Peter','Mary'],'Mary':['Jim'], 'Peter':[],'Jim':[]}
其中key是老板，value是直属员工的list
需要返回指定人所有直系和间接员工的总数，我当时是写递归分治，每个人return他每个下属的下属个数的总和，有点像返回一个树节点下面所有的子节点的个数。如果有其他思路很欢迎大神分享，我们可以学习一下。

第二题有着非常明显的谷歌风格，比较考察candidate的算法基本功，我觉得是个好题，默默记录下来哈哈

huali0415 发表于 2021-2-10 00:59
1，把数字全部装进buckets（hashmap即可）
2，从每个bucket出发进行dfs，每次去找左、右相邻的两个bucke ...

明白了。每个bucket的size应该是k，数字对k取模之后放入对应的bucket，然后更新每个bucket的最大值和最小值。这样，相邻的buckets就可以根据最大值和最小值的差来判断是不是能够合并。这样的话，其实跟楼主的思路差不多了，只不过是另外一种sort，不需要关注每个bucket里面的情况。空间还是要多用一些。也还是需要记录原来数据的位置。

请问楼主投的timeline是怎么样的？谢谢

排序还是最简单直接的办法，想要比排序还快的话 边扫描边merge也不是不行， 但是merge的时候要找相邻的buckets, 而且要判断新加入的这个number会不会扩展bucket的界限，不一定是merge一次完事儿了，代码会比较复杂，可读性也会降低。（当然大牛可以无视这些）

排序的话只需要从最小的数字一个个看下去，只要在 current number + k 的范围内，就放在同一个bucket，不在的话就开始往一个新的bucket里放。

1. 
   
2. def find_group(numbers: List[int], k: int):
   
3.     sorted_numbers = sorted(numbers)
   
4.     groups = []
   
5.     ind = 0
   
6.     while ind < len(sorted_numbers):
   
7.         right = ind
   
8.         while right < len(sorted_numbers) and sorted_numbers[right] <= sorted_numbers[ind]+k:
   
9.             right += 1
   
10.         groups.append(sorted_numbers[ind: right])
    
11.         ind = right
    
12.     return groups
    

复制代码

Tdvxufnek 发表于 2021-2-9 18:33
海牙，大意了，不应该把value直接变成区间的，应该先拿数字扫，最后再变成区间，感谢提醒！

这部分还是不是太懂，能否举例展开说说"应该先拿数字扫，最后再变成区间。。。"非常感谢哈

changfu24 发表于 2021-2-10 05:47
请问楼主投的timeline是怎么样的？谢谢

timeline 就是每两个月投3个狗家的职位 投了1年了 基本已经放弃了 压根没指望狗家回复 结果recruiter就找上门了，这只是电面，后面的interview还没约好，感觉最近recruiter特别忙，我和他约的聊下一轮面试的meeting都约到三月份去了，之前他说他没空，感觉他们家重来不愁candidates, 唉，天地不仁，以万物为刍狗。。。

shanewww 发表于 2021-2-10 05:55
排序还是最简单直接的办法，想要比排序还快的话 边扫描边merge也不是不行， 但是merge的时候要找相邻的buck ...

但是此题还要求最后返回的list里每个group里面数字的原始相对顺序不变，排序的话就打乱了，我当时是强行开tuple记录(order,value)，先按value 排序，小组内按order排序。记得当时和面试官聊得时候她对我的算法想了很长时间，最后弄明白是可以work的，感觉她的optimal solution不是这个，而且她原本还打算出另外一题，结果我这题整的太复杂就来不及了。很想知道是否有更简单的写法。

huali0415 发表于 2021-2-10 00:59
1，把数字全部装进buckets（hashmap即可）
2，从每个bucket出发进行dfs，每次去找左、右相邻的两个bucke ...

如果找左右两个bucket，是否得对bucket进行排序，或者用priority quene呢，这样的话又变成nlogn的了

yiliaobailiao 发表于 2021-2-9 22:32
这个题目的要求是“差值小于k”，并不是“等于k”。所以只查询+k, -k两个值是不够的。

明白了！感谢大神 是我理解错题意了