## Interview Question for SDE-2s

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

``````public class SortThreeRadixInPlace {
public static void sortSpecial(String[] array) {
if(array == null || array.length <= 1) return;
for(int p2s = 0, p3s = 0, i = 0; i < array.length; i++) {
// [0, p2s) marks the range for prio. 1.
// [p2s, p3s) marks the range for prio. 2.
// [p3s, i) marks the range for prio 3.
int prio = getPrio(array[i]); // here one would call the function to get the prio
if(prio == 1) {
swap(array, i, p2s);
swap(array, i, p3s);
p2s++;
p3s++;
} else if(prio == 2) {
swap(array, i, p3s);
p3s++;
}
}
}``````

and the boilerplate to compile and drive

``````static public void main(String[] args) {
String[] array = new String[]{"101", "302", "203", "104", "305", "106", "207", "208", "109", "310", "211"};
sortSpecial(array);
System.out.println(Arrays.toString(array));
// output: [101, 104, 106, 109, 207, 208, 203, 211, 305, 310, 302]
}

static private int getPrio(String code) {
// e.g. first character contains the prio 1,2,3
int prio = code.charAt(0) - '0';
if(prio >= 1 && prio <= 3) return prio;
return 3;
}

static private <T> void swap(T[] array, int i, int j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Easier conceptual approach is to count each priority items and output

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.