Google新鲜virtual onsite面经

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

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

umusa2012 发表于 2020-07-03 10:25:10
第四题 应该不是求最短路径， 而是求最小梯子长度， 最短路径上的最小梯子长度不一定是 global optimal
比如

的确，我居然两次都看错了问题……

第四题是LintCode 258 https://www.lintcode.com/problem/map-jump/description
用二分法来试答案，对于每个答案（最大梯子长度），用BFS检查能不能从起点走到终点。

zzgzzm 发表于 2020-7-4 08:44
的确，我居然两次都看错了问题……

感觉你说的dijistra是可行的， 我试着写了一下不知道对不对

1. def minLadder(board):
   
2.     m, n = len(board), len(board[0])
   
3.     visited = set()
   
4.     target = (m-1, n-1)
   
5.     heap = [[0, (0,0)]]
   
6. 
   
7.     h_ladder = 0
   
8.     while target not in visited:
   
9.         print(heap)
   
10.         h, (i,j) = heapq.heappop(heap)
    
11.         if (i, j) in visited:
    
12.             continue
    
13.         visited.add((i,j))
    
14.         h_ladder = max(h_ladder, h)
    
15. 
    
16.         for ni, nj in [[i-1, j],[i+1, j], [i, j-1], [i, j+1]]:
    
17.             if 0 <= ni < m and 0 <= nj < n:
    
18.                 heapq.heappush(heap, [abs(board[i][j] - board[ni][nj]), (ni,nj)])
    
19.             
    
20.     return h_ladder
    

复制代码

alpaca1234 发表于 2020-7-19 03:58
感觉你说的dijistra是可行的， 我试着写了一下不知道对不对

[mw_shl_code=python,true]def minLadder( ...

感觉可以

坨坨 发表于 2020-6-4 21:18
为啥要用priority queue， 直接按照时间对votes排序不行么？

只需要记录领先的人，然后每个时间点比较一下，就行了