views:

106

answers:

4

Hi, I am trying to find the solution for a problem where i have something like

  1. A > B
  2. B > C
  3. B > D
  4. C > D

And I should get the answer as A > B > C > D.

Conditions for this problem

  1. The output will involve all the elements.
  2. The problem will not have any bogus inputs. for example, (A>B) (C>D) is a bogus input, since we cannot determine the output.
  3. The inputs can be of any size but never bogus and there will always be a solution to the problem.

I need to find a solution for this optimally using Java Collections. Any tips/hints are welcome.

Thanks in advance!

+7  A: 

It's called a Topological Sort. http://en.wikipedia.org/wiki/Topological_sorting

Given that, you should be able to complete your homework on your own.

S.Lott
Great response to a homework question! Very specific, yet leaving much to be figured-out to the student!
mjv
Offhand, I seem to recall that top. sort will return a result even if there are several possible answers. I think the Qn wants to ensure the answer is unique (i.e., fail if it is not).
Charles Stewart
Thank you very much for the heads up! I will take on from here
Bragboy
@Charles Stewart: "ensure the answer is unique"? Where did you read that?
S.Lott
@S.Lott: it is not clearly asserted as a requirement, but talk of "bogus problems", which are said to be problems without unique solns, suggested that to me.
Charles Stewart
+1  A: 

I'm betting you recently covered graphs in this class...
How do you think a graph could be applied here ?
Can you think of a structure which one would build on the basis of the problem inputs (A>B>, A>D, C>A etc.)? Maybe some kind of directed graph...

Once the problem is expressed in such a graph, the solution would involve navigating this graph...

mjv
A: 

You start putting them in a List. The list will be sorted, so for the nth pair (a, b), you look up a, using a binary search. If it exists already skip, if not you insert in at proper point. Since a > b, you do that again with b in the remaining part of the List. Hope this help.

fastcodejava
A: 

You can do this with a Map of the inputs and a recursive method that adds it's answer to a returned List (or just prints each node as it descends the tree.) If you are returning the answer then pre-pending to the returned list will prevent the answer from being reversed D->C->B->A when complete (or you can just .reverse() the list at the end.) Don't forget to test for a break condition when recursing. (hint: key not found)

Chris Nava