## Juspay Interview Question

Software Developers**Country:**India

I am not sure how can we do it in O(Log(n)), but with O(n) it should be easy.

1) Keep a map where you store the cells which can be reached by C1.

2) Traverse through the path of C1, keep on storing the path in the map. {c1: 1, c1->exit: i, c1->exit->exit: 1 ....}

3) Do the same traversal for c2, at any time if you find the exit path exist in the above map then that is the meeting point of 2 cells.

In Javascript:

```
var path = {},
meetingPoint = null;
while(c1.exit) {
var cell = c1.exit;
path[cell] = 1;
}
while(c2.exit) {
if (path[c2.exit] === 1) {
meetingPoint = c2.exit;
}
}
return meetingPoint;
```

var path = {},

meetingPoint = null;

while(c1.exit) {

var cell = c1.exit;

path[cell] = 1;

}

while(c2.exit) {

if (path[c2.exit] === 1) {

meetingPoint = c2.exit;

}

}

return meetingPoint;

# Anwer to this question in Python:

```
def meet(edges,c):
startCell = c[0]
c1_cells=[]
cell = startCell
while cell > -1 and cell not in c1_cells:
c1_cells.append(cell)
cell = edges[cell]
startCell = c[1]
c2_cells=[]
cell = startCell
while cell > -1 and cell not in c2_cells:
c2_cells.append(cell)
cell = edges[cell]
min_dist = 99999
ans = -1
for j in c1_cells:
if j in c2_cells:
dist = max(c1_cells.index(j) , c2_cells.index(j))
if dist < min_dist:
min_dist = dist
ans = j
return ans
size = int(input())
edges = list(map(int,input().strip().split()))
c = list(map(int,(input().split())))
print(meet(edges,c))
```

I think this code will fail when you stuck in an infinite cycle.

- maniacLooper December 18, 2020Let the path 1-> 2-> 3-> 4-> 1

Then, you will be stuck in your first while loop.

i may suggest a code in python:

def find_meet(edges_list, a,b,n):

visited = [0]*n

d = {}

visited[a] = 1

if visited[b] == 1:

return a

visited[b] = 1

t = edges_list[a]

while t!= -1 and visited[t] == 0:

visited[t] = 1

t = edges_list[t]

t = edges_list[b]

# print(visited)

while t!= -1 and visited[t] == 0:

visited[t] = 1

t = edges_list[t]

# print(visited)

if t == -1:

return -1

return t

t = int(input())

for _ in range(t):

n = int(input())

edges_list = list(map(int,input().split()))

a,b = map(int,input().split())

# print([i for i in range(n)])

# print(edges_list)

print(find_meet(edges_list, a, b, n))

################# SIddhesh dosi #######################