Cadence Inc Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
1. Append first steps to the empty list
2. Check each item of the list if dependencies are done.
3. If all dependencies are done, remove it from the list and add children to the end of the list
4. If not all dependencies are finished yet stay where it is.
5. Repeat 2-4 until the list is empty.
this problem will be solved using DFS on DAG.
1. we can create directed acyclic graph of the jobs and their dependences. IF job 1 have dependency on job 2 then make 1->2. similarly for others.
2. then use dfs over each node of Graph. as soon as all dependencies of a node processed then process that node.
write comments if any issue.
- Ashish September 09, 2014