Saw this question on Careercup.com:
Given heights of n persons standing in a line and a list of numbers corresponding to each person (p) that gives the number of persons who are taller than p and standing in front of p. For example,
Heights: 5 3 2 6 1 4
InFronts:0 1 2 0 3 2
Means that the actual actual order is: 5 3 2 1 6 4
The question gets the two lists of Heights and InFronts, and should generate the order standing in line.
My solution:
It could be solved by first sorting the list in descending order. Obviously, to sort, we need to define an object Person (with two attributes of Height and InFront) and then sort Persons based on their height. Then, I would use two stacks, a main stack and a temp one, to build up the order.
Starting from the tallest, put it in the main stack. If the next person had an InFront value of greater than the person on top of the stack, that means the new person should be added before the person on top. Therefore, we need to pop persons from the main stack, insert the new person, and then return the persons popped out in the first step (back to the main stack from temp one). I would use a temp stack to keep the order of the popped out persons. But how many should be popped out? Since the list is sorted, we need to pop exactly the number of persons in front of the new person, i.e. corresponding InFront.
I think this solution works. But the worst case order would be O(n^2) -- when putting a person in place needs popping out all previous ones.
Is there any other solutions? possibly in O(n)?