Directi Interview Question
Country: India
Interview Type: Phone Interview
I tried like as you mentioned, its failing for the input {1,1,2,2,2,0,1,2,0}, if I use while(mid<right), but working fine if I use while(mid<=right), can you please check once?
yes it should be equal to..Thanks for pointing that out.
I hope this works fine for all.
1. left = 0, mid = 0, right = n
2. while mid <= right
3. if arr[mid] == 0 swap arr[left] and arr[mid], then mid++; left++;
4. if arr[i] == 1 mid++;
5. if arr[i] == 2 swap arr[mid] and arr[right], then right--;
geeksforgeeks will have more details.
Hmmm, now it seems to be correct, but my implemented code still displays wrong result:
def DNFAlgo(a) :
right = len(a) - 1
if right < 1 : return
left = 0
mid = 0
while mid <= right :
if a[mid] == 0 :
a[left], a[mid] = a[mid], a[left]
mid = mid + 1
left = left + 1
if a[mid] == 1 :
mid = mid + 1
if a[mid] == 2 :
a[mid], a[right] = a[right], a[mid]
right = right - 1
for your array {1,1,2,2,2,0,1,2,0} it displays result:
{0,0,1,1,2,1,2,2,2}
You could try this:
arr = [0,2,2,0,2,1]
zeroFreq, oneFreq, twoFreq = 0, 0, 0
newList = []
for i in xrange(len(arr)):
if arr[i] == 0:
zeroFreq += 1
elif arr[i] == 1:
oneFreq += 1
else:
twoFreq += 1
for i in xrange(zeroFreq):
newList.append(0)
for i in xrange(oneFreq):
newList.append(1)
for i in xrange(twoFreq):
newList.append(2)
print newList
Solution loops through the array once keeping track of the minimum index for 0,1,2. If the number at the previous index if greater than the current index number, then we swap the current index number with the minimum index of the number at previous index.
static void sort(int[] array) {
if (array == null || array.length < 1)
return;
int[] lastIndex = new int[3];
lastIndex[0] = -1;
lastIndex[1] = -1;
lastIndex[2] = -1;
System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
for (int i = 0; i < array.length; i++) {
if (lastIndex[array[i]] == -1)
lastIndex[array[i]] = i;
if (i != 0) {
int current = array[i];
int prev = array[i - 1];
if ((prev - current) > 0) {
if ((prev - current) == 1 || lastIndex[1] == -1) {
swap(i, lastIndex[prev], array);
updateLastIndex(current, prev, i, lastIndex, array);
System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
} else {
// swap 1 and 0
swap(i, lastIndex[1], array);
updateLastIndex(0, 1, i, lastIndex, array);
System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
// swap 2 and 1
swap(i, lastIndex[prev], array);
updateLastIndex(current, prev, i, lastIndex, array);
System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
}
}
}
}
}
static void updateLastIndex(int current, int previous, int index, int[] lastIndex, int[] array) {
if (lastIndex[current] > lastIndex[previous])
lastIndex[current] = lastIndex[previous];
if (array[lastIndex[previous] + 1] == previous)
lastIndex[previous]++;
else
lastIndex[previous] = index;
}
static void swap(int i, int j, int[] array) {
array[j] ^= array[i];
array[i] ^= array[j];
array[j] ^= array[i];
}
May be you can use counting sort.
public static int[] getSortedArray ( int[] inputArr ) {
/*
* We already know that the unsorted Array has just
* 0s, 1s, 2s. We can leverage this information.
*/
if ( inputArr == null ) {
return null;
}
int[] intermediateArr = new int[3];
int i;
for ( i = 0 ; i < inputArr.length ; i++ ) {
intermediateArr[inputArr[i]]++;
}
int count = 0;
for ( i = 0 ; i < intermediateArr.length; i++ ) {
while ( intermediateArr[i] > 0 ) {
inputArr[count] = i;
count++;
intermediateArr[i]--;
}
}
return inputArr;
}
Use Dutch Flag Algo:
- artemis November 08, 20121. left = 0, mid = 0, right = n
2. while mid < right
3. if arr[mid] == 0 swap arr[left] and arr[mid], then mid++;
4. if arr[i] == 1 mid++;
5. if arr[i] == 2 swap arr[mid] and arr[right], then right--;
geeksforgeeks will have more details.