## Google Interview Question

Software Engineers**Country:**India

we can have BFS way traversal and until we find the target node keep traversing:-

void util(int src, int tgt, boolean vis[], int dist)

{

Queue<Integer> q = new LinkedList<Integer>();

q.add(src);

while(!q.isEmpty())

{

int x = q.pop();

vis[x] = true ;

ArrayList<Integer> adj = getFriends(x);

for(Integer k : adj)

{

if(!vis[k])

{

q.push(k);

dis[k]+=1;

}

}

}

int getDistance(int src , int tgt)

{

int dist[] = new int[v] // number of nodes

boolean vis[] = new boolean[] ;

util(src, tgt, vis, dist)

return dist[tgt];

}

```
int checkFriend(int s, int t) {
queue<int> q;
q.push(s);
int level = 0;
vector<bool> visited(maxN, false);
visited[s] = true;
while (q.size()) {
int n = q.size();
for(int i = 0; i < n; i++) {
int u = q.top();
q.pop();
if (u == t) return level;
for(int v: a[u]) if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
level++;
{
}
```

```
def findlist(input):
dictn={}
for pair in input:
dictn[pair[0]]=dictn.get(pair[0], [])+[(pair[2],pair[1])]
queue=[(0, 1)]
ans=[1]
while queue:
tmstmp, person = queue.pop(0)
if dictn.get(person) is not None:
for neighbour in dictn[person]:
if neighbour[0]>=tmstmp:
queue.append((neighbour[0], neighbour[1]))
ans.append(neighbour[1])
return ans
def getFriend(user):
#returns a list of users first degree friends
def checkdegree(user1, user2):
if user1==user2:
return 0
queue=[(user1, 0)]
degree=-1
while(queue):
usr, degree = queue.pop(0)
friendslist=getFriend(usr)
for friend in friendslist:
if friend==user2:
return degree+1
if degree<2:
queue.append((friend, degree+1))
return -1
def getFriends(user):
first_degree = getFriend(user)
ans=[]
for friend in firstdegree:
sec_degree = getFriend(friend)
ans.extend(sec_degree)
for friend2 in sec_degree:
ans.extend(getFriend(friend2))
return and
```

Rudimentary. Just do DFS in any form with depth count ( max_depth ) and create visited set.

- NoOne May 28, 2021Do this for both user_1 and user_2.

Then simply do an intersection.

You are done.