Interview Question
Country: United States
procedure DFS(G, s, dest, g):
let marked[1..G.V] keep track of the visited vertices
call DFS_recursive(G, s, dest, marked, g)
end procedure
procedure DFS_recursive(G, u, dest, marked, pred, g):
marked[u] = True
if (u == dest) then:
return True
is_dest = False
for each v such that gcd(u,v) < g:
if marked[v] == False then:
is_dest = DFS_recursive(G, u, dest, marked, pred, g)
return is_dest
# for a pair (u,v) and for a value of g call:
is_path = call DFS(G, u, v, g)
Note:
1. For gcd(a,b) you can use Euclid's algorithm.
2. If the value of g is the same for any (u,v) call then you can use some sort of dynamic programming (populate G.E as you go) for future queries!
Hii i Found this question on glassdor. This question was asked in codenation.Can anyone tell how to solve this problem
- manaranjanfav January 17, 2019