狗家VO面经

上个月底面的狗家L4，贡献一下面经：

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

游客，您好！
本帖隐藏的内容需要积分高于 50 才可浏览
您当前积分为 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

Linked list 找cicle可以用hare and tortoise

第四轮 顺便求一下第二问的input是什么type呀 为啥有两个C呀

1. 
   
2. class AddRoad:
   
3.     def union(self, a,b,parent):
   
4.         parent[self.find(a,parent)] = self.find(b,parent)
   
5.     def find(self, a, parent):
   
6.         if parent[a] != a:
   
7.             parent[a] = self.find(parent[a],parent)
   
8.         return parent[a]
   
9.     def __init__(self, matrix):
   
10.         n,m=len(matrix),len(matrix[0])
    
11.         visited = set()
    
12.         def dfs(x,y,ids):
    
13.             self.union((x,y),ids,self.parent)
    
14.             visited.add((x,y))
    
15.             for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
    
16.                 nx,ny=x+dx,y+dy
    
17.                 if 0<=nx<n and 0<=ny<m and matrix[nx][ny] == 1 and (nx,ny) not in visited:
    
18.                     dfs(nx,ny,ids)
    
19. 
    
20.         self.matrix = matrix
    
21.         # use -2, -1 to represent root for 2 island
    
22.         ids = -2
    
23.         self.parent = {-1:-1,-2:-2}
    
24.         for i in range(n):
    
25.             for j in range(m):
    
26.                 self.parent[(i,j)] = (i,j)
    
27.         for i in range(n):
    
28.             for j in range(m):
    
29.                 if matrix[i][j]:
    
30.                     dfs(i,j,ids)
    
31.                     ids += 1
    
32.         self.island1 = -1
    
33.         self.island2 = -2
    
34.    
    
35.     def addRoad(self, x, y):
    
36.         if self.matrix[x][y] == 1:
    
37.             return False
    
38.         self.matrix[x][y] = 1
    
39.         for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
    
40.             nx,ny=x+dx,y+dy
    
41.             if 0<=nx<n and 0<=ny<m and self.matrix[nx][ny] == 1:
    
42.                 self.union((nx,ny),(x,y))
    
43.         return self.find(self.island1, self.parent) == self.find(self.island2, self.parent)

复制代码

第一轮

1. 
   
2. class Node:
   
3.     def __init__(self,value,secretValue,next=None):
   
4.         self.value = value
   
5.         self.secretValue = secretValue
   
6.         self.next = next
   
7. def nextSecretValue(head):
   
8.     node = head
   
9.     while node:
   
10.         if node.next:
    
11.             node.secretValue = hash(node.value + node.next.secretValue)
    
12.         else:
    
13.             node.secretValue = hash(node.value)
    
14.     return head
    
15. def circle(head):
    
16.     slow,fast = head,head
    
17.     while fast and fast.next:
    
18.         if fast == slow:
    
19.             return True
    
20.         fast = fast.next.next
    
21.         slow = slow.next
    
22.     return False

复制代码

第三题

1. 
   
2. def minimum_distance(matrix,start,end):
   
3.     n,m=len(matrix),len(matrix[0])
   
4.     q = deque()
   
5.     visited = set()
   
6.     for i in range(n):
   
7.         for j in range(m):
   
8.             if matrix[i][j] == 1:
   
9.                 q.append((i,j))
   
10.                 visited.add((i,j))
    
11.                 matrix[i][j] = -1
    
12.     graph = [[0] * m for _ in range(n)]
    
13.     step = 0
    
14.     while q:
    
15.         for _ in range(len(q)):
    
16.             x,y = q.popleft()
    
17.             graph[x][y] = step
    
18.             for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
    
19.                 nx,ny=x+dx,y+dy
    
20.                 if 0<=nx<n and 0<=ny<m and (nx,ny) not in visited:
    
21.                     q.append((nx,ny))
    
22.                     visited.add((nx,ny))
    
23.         step += 1
    
24.     x,y=start
    
25.     heap = [(-graph[x][y],x,y)]
    
26.     distance = {(x,y):graph[x][y]}
    
27.     while heap:
    
28.         dis,x,y = heappop(heap)
    
29.         if (x,y) == end:
    
30.             return -dis
    
31.         dis *= -1
    
32.         for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
    
33.             nx,ny=x+dx,y+dy
    
34.             if 0<=nx<n and 0<=ny<m and matrix[nx][ny] != -1:
    
35.                 new_dis = min(graph[nx][ny], dis)
    
36.                 if (nx,ny) not in distance or distance[(nx,ny)] < new_dis:
    
37.                     heappush(heap, (-new_dis, nx,ny))
    
38.                     distance[(nx,ny)] = new_dis
    
39.     return -1

复制代码

hjldtc 发表于 2021-5-9 03:55
第一轮
[mw_shl_code=python,true]
class Node:

计算当前节点的时候 node.next.secretValue 还没有被计算过吧
题主提到了递归 应该是递归到tail然后bottom-up更新的哇

--第四轮是不是两个set更方便一点？ 每次添加一个点 看这个点的neighbor能不能是不是既有第一个岛的也有第二个岛的--
忽略我吧 union find规范一点

kashimoto 发表于 2021-05-08 14:23:58
计算当前节点的时候 node.next.secretValue 还没有被计算过吧
题主提到了递归 应该是递归到tail然后bottom-up更新的哇

好像有道理 从后往前更新 要递归

都好难。。。请问第三题的TC多少？所有点的bfs感觉复杂度很高啊

sas鹰uke 发表于 2021-5-9 11:40
都好难。。。请问第三题的TC多少？所有点的bfs感觉复杂度很高啊

可以从所有等于1的点开始bfs update 所有0 到1的最近距离，bfs的TC就是 row * col。