狗家非常新鲜的现场表演（求大米）

狗家现场表演。 没有发现 利口上的原题。

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

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

补充内容 (2020-8-27 12:13):
第一轮，有一个 例子写错， 更新如下。
`( * 3 ( + 4 1 2 ) )` => 21

ZionHuang 发表于 2020-9-19 01:13
请问这个面经思路是啥呢 感觉要先建个坐标系 然后把这些圆圈全部给填到网格中 再用bfs扫一遍 看能不能走 ...

利用dfs或者union find做

1. def connect(p1, p2):
   
2.     return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 <= (p1[2] + p2[2]) ** 2
   
3. 
   
4. def lobound(p):
   
5.     return p[1] - p[2]
   
6. 
   
7. def hibound(p):
   
8.     return p[1] + p[2]
   
9. 
   
10. # O(n * n)
    
11. def can_pass(pillars, lo, hi):
    
12.     from collections import defaultdict
    
13.     graph = defaultdict(set)
    
14.     for i in range(len(pillars)):
    
15.         if lobound(pillars[i]) <= lo and hibound(pillars[i]) >= hi:
    
16.             return False
    
17.         for j in range(i + 1, len(pillars)):
    
18.             if connect(pillars[i], pillars[j]):
    
19.                 graph[i].add(j)
    
20.                 graph[j].add(i)
    
21. 
    
22.     visit = set()
    
23. 
    
24. 
    
25.     def dfs(idx):
    
26.         stk = [(idx, lobound(pillars[idx]), hibound(pillars[idx]))]
    
27.         while stk:
    
28.             i, lb, hb = stk.pop()
    
29.             if i in visit:
    
30.                 continue
    
31.             visit.add(i)
    
32.             if lb <= lo and hb >= hi:
    
33.                 return False
    
34.             for nei in graph[i]:
    
35.                 if nei in visit:
    
36.                     continue
    
37.                 stk.append((nei, min(lb, lobound(pillars[nei])), max(hb, hibound(pillars[nei]))))
    
38.         return True
    
39. 
    
40.     return all(dfs(i) for i in range(len(pillars)) if i not in visit)
    

复制代码

[/i][/i][/i][/i][/i]

感觉第二题像并查集。相交的圆合并成一组。对每个组，维护它能延伸到的左边界，右边界。如果某组的[左边界，右边界] 能包括马路，说明能block路

caramonmajere 发表于 2020-8-28 01:07
请问第四题算system design还是coding？

coding 字数字数

1.  和琪散流很像
2. 一道去年的面筋题
3. 幺二四简化版？4. 没太看懂什么意思..是说相当于一个数组，对于每个位置，找前面比自己小的数的数量？

旧未来 发表于 2020-8-27 07:46
1.  和琪散流很像
2. 一道去年的面筋题
3. 幺二四简化版？

1.  和琪散流很像 -》 不是很像，因为数字可以是很多的，不一定是2，还要判断是不是valid的
2. 一道去年的面筋题
3. 幺二四 =》》 不像的，看我给的例子。

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

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

感觉第一轮要验valid， 就变得超难了
还有第四轮， bst 不见得balance有可能O(N)

ninjax 发表于 2020-8-27 11:50
感觉第一轮要验valid， 就变得超难了
还有第四轮， bst 不见得balance有可能O(N)

我是楼主，第四题，面试官要求的是in general是 log N的时间复杂度。然后最后讨论到大家同意用bst

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

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

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

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

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

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

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

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