Abhishek Shrivastava
BAN USER- 1of 1 vote
AnswersYou are given a BST, and min, max elements. Your task is to trim this BST so that it contains the elements between the min and the max elements.
For example, given the mix and max elements [5, 13] and the tree below, you would return the output below.8 3 10 1 6 14 4 7 13
output should be :--->
- Abhishek Shrivastava in United States8 6 10 7 13
| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm
Yeah Agree...!!!!
1. I was also trying to modify merg sort to reduce the complexity to O(nlogn).
2. Another approcah if the temp storage is allowed then we can create two different arrays for odd and even positions and use merge sorting; then finally we can create a final sorted (as expected .. odd/even) array.
It will also execute using O(nlogn)+O(n) = O(nlogn)
We can modify the existing sorting algorithm to do so. I have changes the insertion sort.
Worst case Complexity : O(n^2)
Sample code is in Java.
package handson;
public class InsertionSort{
public static void main(String a[]){
int i;
int array[] = {12,9,4,99,120,1,3,10};
System.out.println(" Selection Sort\n\n");
System.out.println("Values Before the sort:");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
insertion_srtEven(array, array.length);
insertion_srtOdd(array, array.length);
System.out.print("Values after the sort:\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
}
public static void insertion_srtOdd(int array[], int n){
for (int i = 2; i < n ; ){
int j = i;
int B = array[i];
while ((j > 0) && (array[j-2] < B)){
array[j] = array[j-2];
j=j-2;
}
array[j] = B;
i=i+2;
}
}
public static void insertion_srtEven(int array[], int n){
for (int i = 3; i < n ; ){
int j = i;
int B = array[i];
while ((j > 1) && (array[j-2] > B)){
array[j] = array[j-2];
j=j-2;
}
array[j] = B;
i=i+2;
}
}
}
Good decision :-)
- Abhishek Shrivastava February 17, 2013