A array : 1 3 0 2 4 9
input: dest-node: A0
output: all the source nodes: (A1, A3, A4)

Each element in this array means the steps it can take. Each element can go left or right. So A[1] and A[4] can reach A[0]. A[1] can reach A[4], A[4] can reach A[0], so A[1] can reach A[0].

Output the index of element which can reach A[0].

Question

A array : 1 3 0 2 4 9   
input: dest-node: A0  
output: all the source nodes: (A1, A3, A4)

Each element in this array means the steps it can take. Each element can go left or right. So A[1] and A[4] can reach A[0]. A[1] can reach A[4], A[4] can reach A[0], so A[1] can reach A[0].

Output the index of element which can reach A[0].

Anonymous · Accepted Answer

consider it is a graph and then dfs or bfs

O(N^2) time complexity, any better algorithm? · Answer

run dfs/bfs from destination node, O(N^2) time complexity, O(N) space. any better algorithm?

Anonymous · Answer

reverse the arcs, run bfs/dfs. atmost 2N arcs, linear time.

Google

Google interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches