Amazon Interview Question
Software Engineer / DevelopersDraw a directed graph and do depth first traversal until all elements are visited...A->B means A depends on B
I mean for dfs u would make use of a for or while loop, the question says that we shouldn't use loops..
dfs wont work always
for eg.
take task A,B,C and D
let B and C depends on A and D depends on D(construct the graf)
using dfs D can be completed directly through A,B and D...therefor leaving task C behing
topological sort is best to use
@krithick.krishnagiri No loops in the question means that there are no cyclic dependencies between the tasks. It does not that a loop cannot be used in the answer
A,B,C,D,E
A-->B,D
C-->D
E-->A
a) From the input remove all the tasks which have list of dependencies(A, C, E)
b) Now you have {B, D}, since there is no loop in the tasks we can remove the task that is depended on more than one tasks that is D
c) Now you have {B} then onwards it should be trivial
I guess topological sorting would work here..
- Jit April 10, 2011