GOOGLE'S #1 INTERVIEW QUESTION (MARCH 2022) | SHORTEST PATH IN GRID WITH OBSTACLE ELIMINATION
HTML-код
- Опубликовано: 11 сен 2024
- In this video we are solving Google's #1 interview question (at the time of recording in March 2022). Despite being a hard level question, it is actually quite simple and follows a very familiar BFS through a matrix/grid pattern that we see in so many other Leetcode problems.
thank you man, what a talent! really best explanations on youtube
Feels like just doing simple BFS 0..K times might be a bit more efficient (esp. if K could be pretty big, we can do binary search instead of just incrementing K) due to abrupt BFS termination in cases where there is no path for current K.
Great explanation, thanks!
great explanation! thanks!!
Really clear explanation, love the variable names too
Great explanation, thank you for sharing!
Thanks for the video explanation.
Amazing explanation!
Appreciated
Thanks
Would be highly appreciated if you can do Problem 317. Shortest Distance from All Buildings
Just made the video. Will be uploaded next week. It's really fucking hard. Explaining it is so hard haha
@@crackfaang Thanks tons for the great efforts and brilliant explanations!
Really awesome !! thanks for the explanation!! this really helps me a lot, big big appreciate!!!
subscribe :D!!!
Hi, I tried another way myself but doesn't seem to work. My dp doesn't seem to work properly. What am I doing wrong here?
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
if k >= m + n - 2:
return m + n - 2
dp = {}
dir = [(1, 0), (0, 1), (-1, 0), (0, -1)]
visit = set()
def dfs(x0, y0, k0):
if k0 < 0:
return float('inf')
if x0 == m-1 and y0 == n-1:
return 0
if (x0, y0, k0) in dp:
return dp[(x0, y0, k0)]
visit.add((x0, y0))
res = float('inf')
for xd, yd in dir:
x1, y1 = x0 + xd, y0 + yd
if x1 in range(m) and y1 in range(n) and (x1, y1) not in visit:
newRes = (dfs(x1, y1, k0-1) if grid[x1][y1] == 1
else dfs(x1, y1, k0))
res = min(res, newRes + 1)
visit.remove((x0, y0))
dp[(x0, y0, k0)] = res
return res
res = dfs(0, 0, k)
return res if res != float('inf') else -1
I tried removing dp, which makes it 'correct' but still can't pass previous test cases due to time complexity issue
This channel is great!
Its slowly gaining momentum.
Ig you should promote the channel on linkedin?
Also if you could make a video on how we could improve leetcode contest ratings, it would be helpful!
Haha I can’t promote it on LinkedIn because I don’t want to give away my name and identity (probably get fired).
Also I have never done a leetcode contest as I think they’re a complete waste of time. Perhaps if you solve these questions as a hobby but for me I always focused on the company I wanted and didn’t bother with anything else. Stay focused on the goal
@@crackfaang Do you work at Google?
@@varunshrivastava2706 I can neither confirm nor deny 😉
@@crackfaang I guess I got my answer 😂😂
where am I going wrong?
var shortestPath = function(grid, k) {
const queue = [ [0, 0, 0] ];
const visited = new Set([ 0 + ',' + 0 ]);
const rows = grid.length, cols = grid[0].length;
while (queue.length > 0) {
const [ row, col, distance ] = queue.shift();
if (row === rows - 1 && col === cols - 1) return distance;
const deltas = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let delta of deltas) {
const [deltaRow, deltaCol] = delta;
const neighborRow = row + deltaRow;
const neighborCol = col + deltaCol;
const neighborPos = neighborRow + ',' + neighborCol;
const rowInbounds = 0
From first glance, you dont seem to have stored K in your queue.
Also, visited and queue seem to have their values flipped.