The Standard Library comes with a lot of algorithms for processing lists
of things, but one thing it does not have is any form of topological sort, which takes a graph as input and produces a list as output.
This weekend I will be flying to PA for a job interview. Before I go, I would like to make sure I get dressed properly. So I made a list of requirements to make sure nothing goes wrong:
item → prerequisite(s)
pants → briefs, shirt
shoes → pants, socks
tie → shirt
jacket → shirt, tie
watch → (none)
That is, I need to have my shirt on before I put on my tie.
But this is only somewhat helpful. What I'd really like is an actual list telling me what order to put clothes on.
A topological sort
is designed precisely for this kind of thing.
However, there is a hiccup. A topological sort is specified as accepting a graph whose edges (u
) indicate that u
comes before v
I need to transform my input from a requirements graph to a dependencies graph: one where every edge (u
) represents things that can occur only after u
has been accomplished.
1 • Write a program that accepts a requirements list
2 • Transform the requirements graph into a dependency graph.
3 • Topologically sort it.
4 • Print the ordered instructions.
A topological sort only gives you one possible order out of many. I would rather not be told to dress in a really odd order, such as:
watch, shirt, socks, tie, jacket, briefs, pants, shoes
Also, as this is a CS interview, we should recognize that the ordering that comes out of a topological sort both depends on the input and
reveals a lot about the underlying data structures and algorithms used. Since this is a security hole, we should fix it by producing a different
but valid ordering every time the topological sort is used.
In fact, about three different orderings would be nice, because I could then choose which one I like best and use it.
5 • Produce a different valid ordering every time the topological sort is applied.
List a item (any single word) and its prerequisite items, if any.
Repeat for each new line.
Press Enter twice to finish.
> pants briefs shirt
> shoes pants socks
> tie shirt
> jacket shirt tie
Three possible orderings:
shirt, socks, tie, jacket, watch, briefs, pants, shoes
watch, socks, briefs, shirt, pants, shoes, tie, jacket
socks, briefs, shirt, watch, pants, tie, jacket, shoes
If that works nicely, I may use it to tell me how to make my PBJ lunch properly.
As this is a challenge, you may of course choose any underlying data structure you wish. I highly recommend an adjacency DAG using a couple of standard containers. You can read more about topological sorting at Wikipedia if you wish. https://en.wikipedia.org/wiki/Topological_sorting
I will be posting my solution about Wednesday next week. (And we’ll see if I get the job.)