I was asked this question in an coding interview I tried hashmap, heap tree, and queue but nothing worked. I want to understand what I missed, can someone tell me how to approach this problem.
DESCRIPTION It's the year 2050. Teleportation has been made possible since 2045. Now you have just bought a teleportation machine for yourself. However. operating the machine is not a child's play. Before you can teleport to some other places. you need to do some arrangements on the machine. There are N equipments in the machine which are needed to be switched on and there are M types of dependencies between various equipment. Now you need to figure out the order in which you should switch on the equipment so as to make the machine start.
Input • First-line will contain 2 numbers: N representing number of equipment in the machine. M representing number of equipment dependencies.
• Next M lines contain 2 integers A and B representing a dependency from A to B (That means A must be switched on to start B.
Output • On a single line, print the order(separated by space) in which the machines should be switched on to do teleportation. Constraints
• 1 <= N <= 500
• 1 <= M = N(N-1)/2
• 1 <= A <= 500
• 1 < B <= 500
Sample Test Case Solution Input:
6 6
1 2
1 3
2 5
3 4
5 6
4 6
Sample Output
1 3 4 2 5 6
Explanation
If you follow the pattern. you will observe that to switch on equipment 6. you would need to switch on 4 and 5. To switch on equipment 4 and 5. we need to switch on equipment 3 and 2 respectively. Finally to switch on equipment 3 and 2 we need to switch on equipment 1.
The problem can be rephrased to:
Input: an unweighted, directed acyclic graph G(V, E)
Output: a topological ordering of G.
The process needed is called Topological Sorting. This reference lists a few alternative algorithms.
One way is to use a depth-first search and mark nodes as visited as you encounter them. Do not visit those again. When backtracking from recursion, prepend the current node to the output list. This will ensure that all dependent nodes have already been add to that list, and this "ancestor" precedes them all.