LET'S TALK TECHNICAL

This blog is intended to help people prepare for the job interviews and improve their analytical skills. We have posted difficult datastructures and algorithm questions and puzzles. Interview experiences section is for the people to post their interview experiences.Views expressed here are of their personal and the blog author doesn't take any responsibility for the same.

-

Followers

Jobs

Tuesday, October 18, 2011

Given a dependency list of the components, how do you find the correct build order in MakeFile

This problem can be mapped to the Topological sorting of vertices in a graph  assuming each component as the vertice in the graph and edge as the dependency indicator.For more details see the link below.
http://en.wikipedia.org/wiki/Topological_sorting
Unix have tsort program for doing the same.
For a DAG(directed acyclic graph) tsort produces a listing of the vertices so that for all edges 'a->b', 'a' comes before 'b' in the listing. This is used in MakeFile for identifying the build order of the components in a way to fulfill dependencies. This will not work when the graph have cycles. (Cyclic dependencies are not taken care).
 http://en.wikipedia.org/wiki/Tsort_%28Unix%29

1 comment:

  1. I didn't understand properly.Can you please give a concrete example to throw more light to it.

    ReplyDelete

Popular Posts