Directi Interview Question
Developer Program EngineersSolution using stack.
take a stack S
for example array A = {3,7,4,9,10,2,1}
Now algo:
1) Push the element in the stack if that element is greater than the top of the stack
as soon as this condition fails
2) pop the top of the element and put in solution array. Repeat step 2 till step 1 doesnt hold true.
The solution array will be 7,10,9,4,3,2,1 which is the required answere.
time O(n) ans space O(n)
pankaj can u plz explain how is tht possible in O(n).....or the solution which u r thnkng of....
The question is not very clear :-( there can be multiple outputs based on what you do after swapping. Increment i or start from i again.
O(n) solution can start from behind
consider 1 , 4, 7, 2, 5
for 5 smallest element on right is 5 so decrement counter
for 2 smallest element is 5 but compare it with smallest 2 < 5 so make smallest=2
so far nothing changes
1,4,7,2,5
for 7, smallest is 2 so swap.
1,4,2,7,5 smallest is still 2.
for 4, smallest is 2 so swap
1,2,4,7,5
for 1 smallest is 2 but 2 < 1 so no change.
1,2,4,7,5
there can be some other solutions as well if question is better defined.
Move from last node to first node while constructing a bst
for each element first search it in the BST....add element to Bst..also note the last right movement(this will be the req element) and replace a[i] by that..
worst case would be o(n^2) but if we use augmented trees it wud be O(nlogn)
- sachin323 October 06, 2010