Cadence Inc Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (sorted order)
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.
Simple. Do topological sorting.
- Killedsteel March 02, 2014http: / /en.wikipedia.org/wiki/Topological_sorting