Adobe Interview Question
Country: United States
what if there is no relationship established between any two of them. say a1>a2,a2>a3,a4>a3 . There would be no cycle but you cannot sort them as you dont know the relation between a4 and a1 or a2. You need to make sure that the graph is complete graph first and then check for a cycle. If not reject it straight away
Sort in ascending order of the first elements using quick sort. Then try to find the location of the second element in the sorted list using binary search on the right hand side of its greater number.
You may also sort the second part and then do one time merge. In any of these methods the running time will be O(n log n), because you have n/2 items that you don't know their order.
If we have something like a1 > a2, a2 > a3, a3 > a1, we know that there is no ascneding order. So we can create a graph based on the comparisons. Create nodes for each element. and then if element x > element y, direct the graph from node y to x. Run some sort of graph algorithm like DFS with cycle detection. If we detect a cycle, we know that we can not order in ascending order.
- SK July 09, 2015