## Interview Question

Country: United States

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

Hii i Found this question on glassdor. This question was asked in codenation.Can anyone tell how to solve this problem

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

What is g?

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

What is g?

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

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

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

It's Union find problem. construct connected components by doing this
:for all i if gcd(i,j)>g (both i,j belong to same component) where j is a multiple of i.Then you can check for any(u,v) if they can be reached(same component) or not.

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.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.