Graph Algorithms for Technical Interviews - Full Course
video description
Here's is my (more complex!) solution (in Python):
def island_count(grid):
graph, nodes = gridToGraph(grid)
count = 0
visited = set()
for i in nodes:
if (i not in visited):
if (bfs(graph, nodes, i, visited) == True):
count += 1
return count
def gridToGraph(grid):
nx = len(grid[0])
ny = len(grid)
size = nx - ny
nodes = --
graph = --
for m in range(size):
i = m % nx
j = int(m / nx) % (nx - ny)
nodes[m] = grid[j][i]
left = None
right = None
up = None
down = None
if (i > 0):
left = [m - 1, grid[j][i - 1]]
if (i < nx - 1):
right = [m + 1, grid[j][i + 1]]
if (j > 0):
up = [m - nx, grid[j - 1][i]]
if (j < ny - 1):
down = [m + nx, grid[j + 1][i]]
if (m not in graph.keys()):
graph[m] = []
if (left != None):
graph[m].append(m - 1)
if (right != None):
graph[m].append(m + 1)
if (up != None):
graph[m].append(m - nx)
if (down != None):
graph[m].append(m + nx)
return graph, nodes
def bfs(graph, nodes, n, visited):
if (n not in visited): visited.add(n)
if (nodes[n] == 'W'): return False
q = [n]
while (len(q) > 0):
i = q.pop()
for e in graph[i]:
if (e not in visited and nodes[e] == 'L'):
visited.add(e)
q.append(e)
return True
Date: 2022-03-14
Related videos
Comments and reviews: 9
ChiefSittingStill
Excellent overall but one minor quibble: I hit a problem with Island Count in C++. If like me you're not particularly au fait with mathematical notation, you may go astray here too.
The C++ code on the website for the explore helper function uses what I believe it be a representation of the mathematical 'less than or equal to' symbol. It's not valid C++ (to my knowledge) and I can't even recreate it on my keyboard! I (incorrectly) took it to mean the C++ 'less than' symbol; this isn't correct, but it's not a glaringly obvious mistake - if you put that in and use Alvin's test cases, that error only manifests itself in the results of test_01 (I got 3 islands returned, not 4 as expected).
To make it clear for anyone else who makes the same mistake I did, I went with these as the first lines of code in my explore function (which is basically otherwise identical to Alvin's):
const unsigned int ZERO-0-;
bool rowInbounds = (ZERO
reply
Excellent overall but one minor quibble: I hit a problem with Island Count in C++. If like me you're not particularly au fait with mathematical notation, you may go astray here too.
The C++ code on the website for the explore helper function uses what I believe it be a representation of the mathematical 'less than or equal to' symbol. It's not valid C++ (to my knowledge) and I can't even recreate it on my keyboard! I (incorrectly) took it to mean the C++ 'less than' symbol; this isn't correct, but it's not a glaringly obvious mistake - if you put that in and use Alvin's test cases, that error only manifests itself in the results of test_01 (I got 3 islands returned, not 4 as expected).
To make it clear for anyone else who makes the same mistake I did, I went with these as the first lines of code in my explore function (which is basically otherwise identical to Alvin's):
const unsigned int ZERO-0-;
bool rowInbounds = (ZERO
reply
Alvin
Hey Programmers! Thanks for checking out the course and I hope you find it useful as you prepare for those tech interviews. If you enjoyed this content, be sure to check out Structy for more data structure and algorithm tutorials from me. Links in the description!
There I cover all of the common interview topics and you can code along and run test cases directly on the platform. You'll also be able to find video walkthroughs for every problem in JavaScript and Python, (more language support coming soon!).
Cheers!
-Alvin
reply
Hey Programmers! Thanks for checking out the course and I hope you find it useful as you prepare for those tech interviews. If you enjoyed this content, be sure to check out Structy for more data structure and algorithm tutorials from me. Links in the description!
There I cover all of the common interview topics and you can code along and run test cases directly on the platform. You'll also be able to find video walkthroughs for every problem in JavaScript and Python, (more language support coming soon!).
Cheers!
-Alvin
reply
Timothy
Hey Thanks -Alvin the Programmer, I have a question about the visited nodes -48:22, It appears you return to node K after marking it visited, and in the code -59:00 there doesn't appear to be a removed from visited call. I'm curious, how you are able to return to an already visited node such as -48:22? I'm thinking visited is a copy and each recursive call gets its unique state at the time of the call...
reply
Hey Thanks -Alvin the Programmer, I have a question about the visited nodes -48:22, It appears you return to node K after marking it visited, and in the code -59:00 there doesn't appear to be a removed from visited call. I'm curious, how you are able to return to an already visited node such as -48:22? I'm thinking visited is a copy and each recursive call gets its unique state at the time of the call...
reply
Monotoba
just one quick clarification. At about 34 minutes in you say that n-squared is the number of edges in a graph. I think you mean that n-squared is the maximum number of edges in a graph. Your own diagram only shows 6 edges for a 3 node graph proving that n-squared is not always the number of edges in a graph. Also, the maximum number of edges will depend on the type of graph.
reply
just one quick clarification. At about 34 minutes in you say that n-squared is the number of edges in a graph. I think you mean that n-squared is the maximum number of edges in a graph. Your own diagram only shows 6 edges for a 3 node graph proving that n-squared is not always the number of edges in a graph. Also, the maximum number of edges will depend on the type of graph.
reply
Oscar
Hey Alvin, I've observed in the minimum island count problem (2:10:00) is that you initialize minSize = infinity. I believe the worst case here is that the entire grid is an island, therefore you could've simply initialize minSize = len(grid) - len(grid[0]) (in Python code). Other than that, great recursive solution!
reply
Hey Alvin, I've observed in the minimum island count problem (2:10:00) is that you initialize minSize = infinity. I believe the worst case here is that the entire grid is an island, therefore you could've simply initialize minSize = len(grid) - len(grid[0]) (in Python code). Other than that, great recursive solution!
reply
Mazhar
At 47:50 . Lets say we wanted to find 'm'. Since you marked 'K' as visited, and are now at 'l'. The icon shouldn't go back to 'K' (as it is visited), so does the program just ends there? Without finding a path to 'm', even though there is a path?
reply
At 47:50 . Lets say we wanted to find 'm'. Since you marked 'K' as visited, and are now at 'l'. The icon shouldn't go back to 'K' (as it is visited), so does the program just ends there? Without finding a path to 'm', even though there is a path?
reply
Harry
Great video! At 1:00:00 isn't there a slight optimisation where you add the src to visited, as it will add it twice as it goes back up the stack so could wrap in a conditional to only add to visited if it doesn't already exist in visited?
reply
Great video! At 1:00:00 isn't there a slight optimisation where you add the src to visited, as it will add it twice as it goes back up the stack so could wrap in a conditional to only add to visited if it doesn't already exist in visited?
reply
John
For island count (1:58:20), you actually don't need a visited set to keep track of the tiles you have already visited. Simply set the land tile to water -W- when you visit it; you already have the logic there to skip over water tiles.
reply
For island count (1:58:20), you actually don't need a visited set to keep track of the tiles you have already visited. Simply set the land tile to water -W- when you visit it; you already have the logic there to skip over water tiles.
reply
Maksatbek
20:40 Looks like you need a queue to implement DFS, because stack is taking as current last node that entered stack:
[b, c] => current becomes -c- but you need -b-, queue in this case fits this implementation
reply
20:40 Looks like you need a queue to implement DFS, because stack is taking as current last node that entered stack:
[b, c] => current becomes -c- but you need -b-, queue in this case fits this implementation
reply
Add a review, comment
Other channel videos
