For those who are trying out their own code,
if you are seeing “NameError: name ‘List’ is not defined”, just add “from typing import List” to the top of the script.
The input specified in the description is a Dict[List[int]], yet the formal parameters of the code have the typing set to List[List[int]]. There’s a disconnect there and wouldn’t be analogous for keys that aren’t 0-indexed.
why the graph if of type List[List[int]], I thought it is a dict instead of a 2d array
hi, what are the parameters to use for the javascript test case?
Problem: Find distance between two nodes.
Solution: Finds the distance between ROOT and a node.
The solution does not solve the stated problem.
You need a variable for both ‘firstNodeLevel’ and ‘secondNodeLevel’ and set the current level to these variables if the target value matches the current node value.
Then call return abs(secondNodeLevel - firstNodeLevel) to get the solution, or return -1 if either of the variables are -1 (variables are -1 if not contained in graph)
I’m confused, should graph be a dict instead of a list?
Nodes of the graph start with index 0, so we can use a list here. You can name each node and use dict instead, but there is no difference.
q = deque([[a, 0]])
visited = set()
while q:
node, level = q.popleft()
for n in graph[node]:
if n == b:
return level + 1
if n not in visited:
q.append([n, level + 1])
visited.add(n)
I am confused as to where the getNeighbors function is coming from.
getNeighbors(node) returns the neighbors of the node. In this problem, it simply returns the corresponding nodes in the adjacency list.
Yeah, you’re right. I think this python solution solves the stated problem (returning None when a node is not in the graph). Also assumes 0 indexed nodes, which seems like something we can’t get around given the way the input is supplied.
def shortest_path(graph: List[List[int]], a: int, b: int) -> int:
def get_neighbors(i):
return graph[i]
def bfs(node1, node2):
queue = deque([0])
level = 0
visited = set([0])
first_node_level = None
second_node_level = None
while queue:
n = len(queue)
for _ in range(n):
node = queue.popleft()
if node == node1:
first_node_level = level
elif node == node2:
second_node_level = level
if first_node_level is not None and second_node_level is not None:
return abs(first_node_level - second_node_level)
for neighbor in get_neighbors(level):
if neighbor in visited:
continue
queue.append(neighbor)
visited.add(neighbor)
level += 1
return bfs(a, b)
I’m confused, the BFS template in the solution here is entirely different from the BFS template available to us
It the same as the “BFS on graph” template except there’s a level variable?
C# solution
public static int ShortestPath(List<List> graph, int a, int b)
{
var levels = 0;
var queue = new Queue<int>();
queue.Enqueue(a);
var visited = new HashSet<int>();
visited.Add(a);
while (queue.Count > 0)
{
var n = queue.Count;
for (int i = 0; i < n; i++)
{
var node = queue.Dequeue();
if (node == b) return levels;
foreach (var neighbour in graph[node])
{
if (visited.Contains(neighbour)) continue;
queue.Enqueue(neighbour);
visited.Add(neighbour);
}
}
levels++;
}
return levels;
}
def shortest_path(graph: List[List[int]], a: int, b: int) → int:
if not graph: return 0
dq, visited, lv = deque([a]), set(), 0
while dq:
for _ in range(len(dq)):
cur = dq.popleft()
if cur in visited: continue
visited.add(cur)
if cur == b: return lv
dq += graph[cur]
lv += 1
return lv
Reset functionality on problem doesn’t work. getNeighbors method is not restored.
should prob add more test cases tbh since i passed without using a visited data structure
NameError: name ‘get_neighbors’ is not defined
How are we supposed to use this function, it doesnt work
I agree with the other comments that it would be really nice to have more test cases, ones that test some edge cases that people often miss.
Also for this, I think there should be a note about how you represent the adjacency matrix as a dict in the intro, but in the coding part of it, you’re provided with a 2-d list. Beginners might get tripped up here.