## Google Interview Question for SDE1s

• 4

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

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.

Comment hidden because of low score. Click to expand.
2
of 2 vote

Python solution:

``````def helper(adj, visited, start, end):
if start == end:
return True
return False
visited[start] = True
return all([helper(adj, visited, child, end) for child in adj[start] if not visited[child]])

v = {node:False for node in adj}

Comment hidden because of low score. Click to expand.
1
of 1 vote

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 {
for (Node i : curr.next) {
if (!allPathsConnect(i, visited, end)) return false;
}
return true;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe you're asked about direct graph, so in this case you can build dominator tree and check whether all nodes dominate end node.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python solution!

``````def helper(adj, visited, start, end):
if start == end:
return True
return False
visited[start] = True
return all([helper(adj, visited, child, end) for child in adj[start] if not visited[child]])

v = {node:False for node in adj}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Actually, I made a mistake here as I assumed it was a tree. Since it is a graph, the error condition is that if all the neighbors of "a" current node are visited and the current node is not the end node, then return false. Meaning that there is a path that does not lead to end node.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0

This was onsite!

Comment hidden because of low score. Click to expand.
0
of 0 vote

The only certain answer to this question is BFS.

From the start node, you have to scan all path and as we traverse down till we either reach the end node or flag it false for when you have checked all nodes.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Can you revisit vertices in a path? Lets say start is 1 and end is 4.
Is this a valid path?
1 - 2 - 3 - 5 - 6 - 2 - 4

Comment hidden because of low score. Click to expand.
0
of 0 vote

compute the max flow with start node and end node, if it is equal to number of edges coming out of source then report 'true' else 'false'.

Comment hidden because of low score. Click to expand.
0
of 0 vote

find maxflow between start node and end node, if its equal to number of edges coming out of start node then report true else false.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
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``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

was there any info given on how the graph is stored or it was left upto you to decide however you want to store the graph?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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".

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?)

Comment hidden because of low score. Click to expand.
0
of 0 vote

test

Comment hidden because of low score. Click to expand.
0
of 0 vote

testesteestestste

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{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.}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

123

Comment hidden because of low score. Click to expand.
0
of 0 vote

1231231312312

Comment hidden because of low score. Click to expand.
0
of 0 vote

12312321312
1231323

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

System.out.println(isNecessaryConnected(directedGraph, vertices, 2, 8));

IGraph directedGraph2 = new DirectedGraph(vertices);

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);

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)

if (node == destination)
path[node] = true;

if (dfs(directedGraph, visted, path, source, destination, node)) {
path[current] = true;
return true;
}

visted.remove(node);
}
}

return false;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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:
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], , , , [3, 7], [2, 8, 10], , [6, 9], [7, 10], [], []]

reachable = end_reachable_from_children(vertices, edges)
print(reachable)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.