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

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.

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

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

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

Python solution:

- Angus January 01, 2019