Interview Question
SDE-2sCountry: United States
public static void sortArray(String productCodeArray[]){
System.out.println(Arrays.toString(productCodeArray));
int mid=0;
int low=0;
int high = productCodeArray.length-1;
while(mid<=high){
int priorityCode = getPriority(productCodeArray[mid]);
String tmp = null;
switch(priorityCode){
case 1:
tmp = productCodeArray[mid];
productCodeArray[mid] = productCodeArray[low];
productCodeArray[low]=tmp;
mid++;
low++;
break;
case 2:
mid++;
break;
case 3:
tmp = productCodeArray[mid];
productCodeArray[mid] = productCodeArray[high];
productCodeArray[high]=tmp;
high--;
break;
}
}
System.out.println("After Sorting: "+Arrays.toString(productCodeArray));
}
Think about problem as an array of integer with 1,2 or 3 in it that needs
to be sorted in-place, not stable.
1) Use a standard, in-place compare-sort technique that will run
with O(n*lg(n)) time and O1(1) space complexity.
2) implement something like radix sort in place with O(n) time and O(1)
space complexity.
For fun 2) in java
and the boilerplate to compile and drive
- Chris May 17, 2017