Google Interview Question SDE1s
Country: United States
Interview Type: In-Person
Python solution:
def helper(adj, visited, start, end):
if start == end:
return True
if len(adj[start])==0:
return False
visited[start] = True
return all([helper(adj, visited, child, end) for child in adj[start] if not visited[child]])
def allPathsConnect(adj, start, end):
v = {node:False for node in adj}
return helper(adj, v, start, end)
I'd do something like this,
class Node {
int num;
HashSet<Node> next = new HashSet<>();
}
boolean allPathsConnect(Node curr, HashSet<Node> visited, Node end) {
if (curr == end) return true;
if (visited.contains(curr)) return true;
else if (curr.next.isEmpty()) return false;
else {
visited.add(curr);
for (Node i : curr.next) {
if (!allPathsConnect(i, visited, end)) return false;
}
return true;
}
}
Python solution!
def helper(adj, visited, start, end):
if start == end:
return True
if len(adj[start])==0:
return False
visited[start] = True
return all([helper(adj, visited, child, end) for child in adj[start] if not visited[child]])
def allPathsConnect(adj, start, end):
v = {node:False for node in adj}
return helper(adj, v, start, end)
This would be a DFS where you check two things 1) you are not going to a node you already visited and 2) if the final node is not the ending node return false.
Use a hashset to keep track of nodes already visited, then when you are on a node go to it's children that you haven't visited yet. If that node doesn't have any children that you haven't visited then return false.
It is a DFS. If reached means if it is end node, then return true. As soon as the program reaches null means end of path, return false.
Brute force:
For each path starting from the start point, we do DFS to see if it can reach the end point. If all of the paths can reach end point, then we are good. Otherwise, return false;
Optimization:
Because we did a lot of redundant work during the DFS phase, we can memorize the successful paths for the previous DFS. And the next DFS is based on all of the previous DFS results, if we reach to a point which is a node in the successful path, then we are done.
can you revisit vertices in a path?
lets say start was 1, end was 4. Is this a valid path :
1 - 2 - 3 - 5 - 6 - 2 - 4
This is how I would do it... some sort of DFS with a little dynamic programming.
So, if for a current vertex that is visited all the path for all adjacent vertices goes T, then all the paths from the current vertex go to T also. If this is done recursively... it should give you the right answer. Basically, if conn[S] == True then NECESSARILY CONNECTED.
connected(v, T)
visited[v] = True
flag = False
for u in adj(v) do
if (u == T) OR // this is the ending vertex, so True
(visited[u] == True AND conn[u] == True) then // this is visited and also the paths from it goes to T
flag = True
if visited[u] == False then
flag = connected(u, T)
// no need to check further...
if flag == False then
break;
conn[v] = flag
return flag
MAIN:
flag = connected(S, T)
if flag == False then
NOT NECESSARILY CONNECTED
else
NECESSARILY CONNECTED
This is how I would do it... some sort of DFS with a little dynamic programming.
So, if for a current vertex that is visited all the path for all adjacent vertices goes T, then all the paths from the current vertex go to T also. If this is done recursively... it should give you the right answer. Basically, if conn[S] == True then NECESSARILY CONNECTED.
connected(v, T)
visited[v] = True
flag = False
for u in adj(v) do
if (u == T) OR // this is the ending vertex, so True
(visited[u] == True AND conn[u] == True) then // this is visited and also the paths from it goes to T
flag = True
if visited[u] == False then
flag = connected(u, T)
// no need to check further...
if flag == False then
break;
conn[v] = flag
return flag
MAIN:
flag = connected(S, T)
if flag == False then
NOT NECESSARILY CONNECTED
else
NECESSARILY CONNECTED
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
Assuming that if cycles are detected than the graph would not be considered Necesssarily connected, firstly using DFS find out if any cycle is present, if yes then directly return false.
We need to find all the nodes which are reachable from Source node before we reach desstination node. These are the nodes present in all the paths between sorce and destination node. For this graph to be necessarily connected none of these should be a sink node. All paths paasing through them should sink at destination node. So for all these nodes check if any node is a Sink node, i.e. has no out going edges then the graph is not 'necessarily connected'. If no such node found then graph is 'necessarily connected'
Complexity will be: O(n^2) , n: no. of vertices in the graph
Your statement: "Assuming that if cycles are detected then the graph would not be considered Necessarily connected..." - so, you say if a graph that contains a cycle along a path from S->T then S->T are not necessarily connected? If that is true, then yes, the DFS solution is incomplete, but it can be adapted extremely easy and avoid O(n^2).
to me it's BFS..
begin with "start node" and review all adjcent node and again and again.. if any of those does not go to "end node", then return false. otherwise, true. there are many youtube out there explaining this. ex) find shortest path.. or all connected?
Google's nature is search company. at least people will need to know all search algorithm (including data structure) very well along with Big O.
frankly speaking, if this was really the interview question in on-site, i would say it was easy one. (don't feel bad but i'm just saying and telling you experience from my friends). because some that i know said.. their interview question was "do code some sort of game".
Consider the graph with the destination node deleted (remove all edges going in and out of the destination, too). This graph represents the paths that can be formed before hitting the destination node (paths that are eligible for failure). 1) In this graph, is there a path from the source to a zero-outdegree vertex? If so, this is a failing path. 2) Is there a path from the source to a cycle? If so, this is a failing path.
If neither case happens, there are no failing paths and the source and destination are necessarily connected.
The case of a cycle from the source can be checked with DFS easily enough. The case of a path to a zero-outdegree edge can be part of the same DFS, or can be done separately with BFS (but why if you're already doing DFS?)
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
{{I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.}}
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
{{
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
}}
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For example, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (
node1->node2->node5
where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (
node1->node2->node5
where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. (
node1->node2->node5
where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. ( node1, node2, node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
I don't know any of the solutions above works.
My understanding of the question is, not just all direct paths from Start node. For exmaple, if the graph is like this,
node1(start) -> node 2 -> node3 -< node4(end)
-> node5
it is not necessarily connected even though there is a path from node1(start) to node4(end) when "all paths" are not connected. ( node1->node2->node5 where it is terminated)
If we just use DFS or BFS, it will find a path to end(node4) and return true.
I don't think google's interview question is so easy to run dfs against direct edges from start node only.
Simple piece of cake solution;
Keep doing DFS, keep a set to check the cycle, and keep a path array to note, that path has been explored or not so that you don't visit them again
public class SourceToDestinationWithCycleNecessaryConnected {
public static void main(String args[]) {
int vertices = 9;
IGraph directedGraph = new DirectedGraph(vertices);
directedGraph.addEdge(2, 3);
directedGraph.addEdge(2, 4);
directedGraph.addEdge(3, 4);
directedGraph.addEdge(3, 6);
directedGraph.addEdge(3, 5);
directedGraph.addEdge(4, 5);
directedGraph.addEdge(4, 2); // Cycle
directedGraph.addEdge(4, 6);
directedGraph.addEdge(5, 4); // Cycle
directedGraph.addEdge(5, 7);
directedGraph.addEdge(7, 8);
System.out.println(isNecessaryConnected(directedGraph, vertices, 2, 8));
IGraph directedGraph2 = new DirectedGraph(vertices);
directedGraph2.addEdge(2, 3);
directedGraph2.addEdge(2, 1);
directedGraph2.addEdge(2, 4);
directedGraph2.addEdge(3, 4);
directedGraph2.addEdge(3, 6);
directedGraph2.addEdge(3, 5);
directedGraph2.addEdge(4, 5);
directedGraph2.addEdge(4, 2); // Cycle
directedGraph2.addEdge(4, 6);
directedGraph2.addEdge(5, 4); // Cycle
directedGraph2.addEdge(5, 7);
directedGraph2.addEdge(7, 8);
System.out.println(isNecessaryConnected(directedGraph2, vertices, 2, 8));
}
private static boolean isNecessaryConnected(IGraph directedGraph, int vertices, int source, int destination) {
if (source > vertices || destination > vertices || source < 0 || destination < 0)
return false;
Set<Integer> visited = new HashSet<>();
boolean path[] = new boolean[vertices];
Arrays.fill(path, false);
visited.add(source);
dfs(directedGraph, visited, path, source, destination, source);
for (int node : directedGraph.getAdjList()[source]) {
if (path[node] == false)
return false;
}
return true;
}
private static boolean dfs(IGraph directedGraph, Set<Integer> visted, boolean[] path, int source, int destination, int current) {
//if this path already been computed
if (path[current])
return true;
for (int node : directedGraph.getAdjList()[current]) {
if (!visted.contains(node)) {
//add this node so that we won't visit again (to avoid cycle)
visted.add(node);
if (node == destination)
path[node] = true;
if (dfs(directedGraph, visted, path, source, destination, node)) {
path[current] = true;
return true;
}
visted.remove(node);
}
}
return false;
}
}
My python solution:
# edges[j] - is a list of children for node j.
def inverse_graph(vertices, edges):
new_edges = [list() for i in range(0, len(vertices))]
j = 0
for children in edges:
for child in children:
new_edges[child].append(j)
j += 1
return new_edges
def end_reachable_from_children(vertices, edges):
if len(edges) == 0:
return False
nodes = [vertices[-1]]
local_nodes = []
reverse_edges = inverse_graph(vertices, edges)
existed_path_from_end = [False for i in edges]
while len(nodes) != 0:
for node in nodes:
if not existed_path_from_end[node]:
local_nodes.extend(reverse_edges[node])
existed_path_from_end[node] = True
nodes = local_nodes
local_nodes = []
t = True
for child in edges[0]:
t = existed_path_from_end[child] and t
return t
vertices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
edges = [[1, 2, 3], [4], [1], [5], [3, 7], [2, 8, 10], [8], [6, 9], [7, 10], [], []]
reachable = end_reachable_from_children(vertices, edges)
print(reachable)
You need to find a path from start that does not end in the end node. You can brute force all paths for from start. You can optimize if you store for a given node if it has a path to end so you do not redo the same work over and over. Recursive solution should be straight forward.
- Chris January 02, 2019