Ittiam Systems Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
1:Mark the element 'x' as key element and take it to one of the two corners of an array.
2:Arrange elements in such fashion that elements to its left are smaller than the key element and right are greater or vice-versa (requires atmost n comparisons).
3:Have 2 BST 1 for elements smaller than key element and other for elements greator than or equal to key element.
4:Have inorder traversal for ascending order.
5:And put elements into stack first by having inorder traversal and then pop out for descending order.
Sort the array using quick sort in descending order
Find the index of key element in the array
Reverse the array from key elements' index + 1 element to the last element to get the ascending order
O(NlogN) algo.
- Neeraj September 12, 2011-> Write your partition function with pivot as x( x may not be present in the array)
-> Partition function returns index k such that all elements in [0,k] are less than 'x' and all elements in range [k+1, N-1] are greater than 'x' .
->Now sort [0,k] range in ascending and [k+1, N-1] in descending order using Quick Sort or some other O(NlogN) algo.