## Microsoft Interview Question for Software Engineer in Tests

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
16
of 22 vote

This problem can be solved by modified Dutch National Flag problem.
Instead of '0' we have -ve numbers
Instead of '1' we have 0's(zero).
and for 2 we have +ve Numbers.
------------------------------------------
So modified algo will be

``````void swap(int *a, int *b)
{
int c;
c = *a;
*a = *b;
*b = c;
}
void sortNumbers(int *arr, int len)
{
int low=0,mid=0,high=len-1;
while(mid <= high)
{
if(arr[mid]<0)
swap(&arr[low++],&arr[mid++]);
else if(arr[mid]==0)
mid++;
else
swap(&arr[mid], &arr[high--]);
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The question does not clearly mention whether all the negatives are the same or whether all the positives are the same. If they are diff say we have -2, -5, -1,etc. and 4,8,7,etc then we cannot use the DNF algo as it is.

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

Why not? If you run the code above with {-4, -5, 0, 3, 7, 0, -2, -5, 7, 0} it should still rearrange them properly. The order might not be preserved though.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

in the last else statement

``````else
swap(&arr[mid], &arr[high--]);``````

shouldnt it be

``````else
swap(&arr[mid++], &arr[high--]);``````

Comment hidden because of low score. Click to expand.
6
of 22 vote

In single parse:

``````#include <stdio.h>
#include <stdlib.h>

int main()
{
int *arr, n, i, j, k;
scanf("%d", &n);
arr = (int *)malloc(sizeof(int)*n);

for(i = 0; i < n; i++)
scanf("%d", &arr[i]);

i = -1;
k = n;

for(j = 0; j < k; j++)
{
if(arr[j] > 0)
{
int temp;
k--;
temp = arr[j];
arr[j] = arr[k];
arr[k] = temp;
j--;
}
else if(arr[j] < 0)
{
int temp;
i++;
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}

printf("\n");
for(i = 0; i < n; i++)
printf(" %d ", arr[i]);

return 0;
}``````

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

Why voted -ve?

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

Dude ignore that, May be some one didn't got that approach. But anyways I see that you're doing this in order O(n^2). This can be done in O(n) order, may be that's why some one didn't like it.

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

Man its O(n)

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

It seems due to indentation people are getting confused.. As I take the array from user.. I am using 2 for loops but they are not nested. :)
I only parse the array once... indicated by second for loop.

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

swapping to keep the elements below zero in first half.. and elements greater than zero in third half.. the elements equal to zero comes in between. :)

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

Ohh....but it is making this code looks complex.But then again you are returning the same array. Its gud.

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

Well vote up thn.. :P

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

Why no vote for my code.. I think its the best solution possible.. Please let me know if ne issue?

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

Hi,
Would you please let me know if the below sequence of input works for your logic???
1,2,5,7,-1,-2,-5,0,0,0
If not, I have still more sequences to share with you.
If possible, explain the logic behind your code.

Thanks.

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

This will work for the given input, I think you are getting confused by the fact that he is using j-- in the loop, that is only to counter the j++ in the for loop.

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

Whenever you come across 0 you are just skipping that instead of putting it in some place. It is not working in making sure 0s are in the middle - which is what supposed to make this challenging. I can do it in two passes though, first bring only negative to one side and then take only remainign array and bring 0s to one side.

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

Please verify the solution before reducing votes. It works absolutely fine. :)

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

Its working for every test case. :)

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

As explained earlier.. making the -ve shift to front nd positive shift to back is same as keeping zeros in middle. Please read comments. :)

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

what if you swap with positive number?
1st element is positive, last element is positive.
{1,-1,0,2}

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

Please run the code to verify urself...
2 -1 0 1
0 -1 2 1
-1 0 2 1

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

Read his code correctly what he is doing is allright..He is just swapping all the positive number towards the end all negative number towrads the begining..In that sense he is swapping even positive with positive, that can be avoided.

I try to make it more logical..Consider the case when there are only positive and negative numbers and no zero..In that case we use two pointer from two ends and swap positive with negative..Here what we have to do is, swap positive with negative as well as zero..Swap negative with positive but swap with zero too..

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

wrong logic...

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

Know about the code before commenting... Its mod Dutch Flag Algo... Thanks. @Neo.

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

F**k all.... B******s.

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

its perfectly fine..!!

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

Not works with an array with a '0' in the first cell.

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

/*
* This has a runtime of O(n).
* Places all the negative no on the left side.
* All the positive no on the right side.
* And all the zeroes in the middle.
*/
public int[] arrangeArray(int[] arr) {
int[] res = new int[arr.length];
int left = 0;
int right = arr.length - 1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
res[left] = arr[i];
left++;
} else if (arr[i] > 0) {
res[right] = arr[i];
right--;
}
}
return res;
}

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

You don't have to do 2 passes. In first pass place the negatives on the left, the positive on the right, and the remaining must be zeroes. As when you initialize an array the value gets initialised with zero so you don't even need to set anything now. Just 1 pass required.

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

Although it's using an extra array, it's easier to understand than the Dutch National Flag algorithm so I like this version more.

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

thanks for this, I was havig trouble understanding DNF

Comment hidden because of low score. Click to expand.
1
of 3 vote

public static void divide_neg_0_pos(int [] test){
int neg_hold=-1;
int pos_hold=test.length;
int current=0;
while(current!=pos_hold){
if(test[current]>0){
exChange(test,current,--pos_hold);
continue;
}
if(test[current]<0){
if(current==neg_hold){
current++;
continue;
}
exChange(test,current,++neg_hold);

}
if(test[current]==0){
current++;
}
}
}

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

Solution 1:

``````void swap(int* a, int i, int j)
{
if (i >= j)
return;

int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

void print(int * a, int len)
{
for (int i = 0; i < len; ++i)
printf("%3d  ", a[i]);
}

int main()
{
int arr[] = {-12, -11, 12, 0, 11, -10, 10, 9, 8, -8, 7, 0, 0 , -9, -7};
int start = 0;
int mid = 0;
int len = sizeof(arr) / sizeof(arr[0]);
int end = len - 1;

print(arr, len);
printf("\n");

while (mid <= end)
{
if (arr[mid] < 0)
swap(arr, start++, mid++);
else if (arr[mid] == 0)
mid++;
else
swap(arr, mid, end--);

}

print(arr, len);
printf("\n");
return 0;
}``````

Solution 2:

``````void swap(int* a, int i, int j)
{
if (i >= j)
return;

int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

void print(int * a, int len)
{
for (int i = 0; i < len; ++i)
printf("%3d  ", a[i]);
}

int main()
{
int arr[] = {-12, -11, 12, 0, 11, -10, 10, 9, 8, -8, 7, 0, 0 , -9, -7};
int start = 0;
int len = sizeof(arr) / sizeof(arr[0]);
int end = len - 1;

print(arr, len);
printf("\n");

while (start < end)
{
while (arr[start] < 0)
++start;

while (arr[end] >= 0)
--end;

swap(arr, start, end);
}

print(arr, len);
printf("\n");
while (arr[start] >= 0)
--start;

++start;
end = len - 1;

while (start < end)
{
while (!arr[start])
++start;

while (arr[end] > 0)
--end;

swap(arr, start, end);
}
print(arr, len);
return 0;
}``````

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

Here is my one pass algorithm:
let ptr_left points to the left end of the array a[] and ptr_right points to the right end
let nzero_left is the counts of zero from left sides; nzero_right for right side

nzero_left=0; nzero_right=0;
while (ptr_left<=ptr_right)
{{

if (a[ptr_left]==positive and
a[ptr_right]==negative)
swap a[ptr_left] and a[ptr_right]

if a[ptr_left] is negative
{
if nzero_left>0:
shift 0 toward the center of array by letting
a[ptr_left-nzero_left]= a[ptr_left]; a[ptr_left]=0;
ptr_left++;
}
else if a[ptr_left] is zero
{
increase nzero_left by 1
ptr_left++;
}

similarly,

if a[ptr_right] is positive
{
if nzero_right>0:
shift 0 toward the center of array by letting
a[ptr_right-nzero_right]= a[ptr_right]; a[ptr_right]=0;
ptr_right--;
}
else if a[ptr_right] is zero
{
increase nzero_right by 1
ptr_right--;
}

}}

eventually, ptr_left and ptr_right meet somewhere in middle,

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

here is the python code

``````a=[1,2,-1,0,2,0,0,3,-1,4,-2,0,3,4,0,0,2,-2,-3,0]
ptr_left=0
ptr_right=len(a)-1;
nzero_left=0
nzero_right=0

while ptr_left<=ptr_right:
if a[ptr_left]>0 and a[ptr_right]<0:
t=a[ptr_left]
a[ptr_left]=a[ptr_right]
a[ptr_right]=t

if a[ptr_left]<0:
if nzero_left>0:
a[ptr_left-nzero_left]=a[ptr_left]
a[ptr_left]=0
ptr_left+=1
elif a[ptr_left]==0:
nzero_left+=1
ptr_left+=1

if a[ptr_right]>0:
if nzero_right>0:
a[ptr_right+nzero_right]=a[ptr_right]
a[ptr_right]=0
ptr_right-=1
elif a[ptr_right]==0:
nzero_right+=1
ptr_right-=1

print ptr_left, ptr_right, nzero_left, nzero_right
print a``````

here is the output
0 18 0 1
[1, 2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 2, -2, -3, 0]
1 17 0 1
[-3, 2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 2, -2, 0, 1]
2 16 0 1
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 2, 0, 2, 1]
3 15 0 1
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 0, 2, 2, 1]
4 14 1 2
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 0, 2, 2, 1]
4 13 1 3
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 0, 2, 2, 1]
4 12 1 3
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 0, 0, 0, 4, 2, 2, 1]
4 11 1 3
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 0, 0, 0, 3, 4, 2, 2, 1]
4 10 1 4
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 0, 0, 0, 3, 4, 2, 2, 1]
5 9 1 4
[-3, -2, -1, -2, 0, 0, 0, 3, -1, 4, 0, 0, 0, 0, 2, 3, 4, 2, 2, 1]
6 8 2 4
[-3, -2, -1, -2, 0, 0, 0, 3, -1, 0, 0, 0, 0, 4, 2, 3, 4, 2, 2, 1]
7 8 3 4
[-3, -2, -1, -2, 0, 0, 0, 3, -1, 0, 0, 0, 0, 4, 2, 3, 4, 2, 2, 1]
8 7 3 4
[-3, -2, -1, -2, -1, 0, 0, 0, 0, 0, 0, 0, 3, 4, 2, 3, 4, 2, 2, 1]

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

good approach.

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

we can just use partition algorithm of quick sort to partition this array, just use 0 as the pivot element and hence all negative numbers will come to its left and positive numbers will come to its right
you can understand partition algorithm at

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

If we could use another array for result, shivam maharshi's code above seems to be doing good. In case we are not allowed to use extra array, following code works fine :

public class testing {

public static void main(String[] args) {
int a[]={-5,6,-9,0,-2,0,4,-3};
sortArray(a);
}

static void sortArray(int[] a)
{
int negativeTracker=0, positiveTracker=a.length-1;

while(negativeTracker<=positiveTracker) {
if(a[negativeTracker] < 0)
negativeTracker++;
else {
if(a[positiveTracker] >= 0)
positiveTracker--;
else {
swap(a, negativeTracker, positiveTracker);
negativeTracker++;
positiveTracker--;
}
}
}

int zeroTracker = 0;
if(positiveTracker < a.length-2) {
zeroTracker = positiveTracker+1;
positiveTracker = a.length-1;

while(zeroTracker<positiveTracker) {
if(a[zeroTracker] == 0)
zeroTracker++;
else {
if(a[positiveTracker] > 0)
positiveTracker--;
else {
swap(a, zeroTracker, positiveTracker);
zeroTracker++;
positiveTracker--;
}
}
}
}

printArray(a);
}

static void swap(int a[], int from, int to)
{
int temp=a[from];
a[from]=a[to];
a[to]=temp;
}

static void printArray(int[] y) {
for(int a:y) {
System.out.print(a + " : ");
}
System.out.println();
}
}

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

``````public static void quickPartition(int array[])
{
int nPtr=0, pPtr=array.length-1;
for(int i=0; i<pPtr; i++)
{
if(array[i]<0)
{
biSwap(array, nPtr, i);
nPtr++;
}
else if(array[i]>0)
{
biSwap(array, pPtr, i);
i--;
pPtr--;
}
}
}``````

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

``````public void DutchFlag(int[] numbers)
{
int low = 0;
int current = 0;
int high = numbers.Length - 1;

while (current <= high)
{
if (numbers[current] > 0)
{
swap(numbers, current, high);
high--;
}
else if (numbers[current] < 0)
{
swap(numbers, current, low);
low++;
current++;
}
else
{
current++;
}
}

}

public void swap(int[] array, int first, int second)
{
int temp;
temp = array[first];
array[first] = array[second];
array[second] = temp;
}``````

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

Use Bucket sort...

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

``````#include<stdio.h>
int main()
{
int arr[20],i,n,j,temp;
printf("enter value of n");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
for(i=0;i<n;i++)
printf("%d\t",arr[i]);
return 0;
}``````

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

``````int main(void)
{
int a[N] = { 0, 1, -0, 1, 0, -1, -1, 1, 1, -1};
int i, lo = 0, mid = 0, hi = N-1, tmp;

while (mid <= hi) {
if (a[mid] == 1) {
tmp = a[mid];
a[mid] = a[hi];
a[hi] = tmp;
--hi;
}
else if (a[mid] == -1) {
tmp = a[lo];
a[lo] = a[mid];
a[mid] = tmp;
++lo; ++mid;
}
else
++mid;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I gave the following answer (didn't get through, help me figure out if I did something wrong)

``````void group(int[] arr) {
int begin = 0, end = arr.length;
while(begin<end) {
/* group all positive together at the end*/
if(arr[begin]>0) {
int temp = arr[begin];
arr[begin] = arr[end];
arr[end] = temp;
end--;
} else {
begin++;
}
}
/* At the end of previous loop, end will contain the first index of negative number */
end--; //This will contain the end-index of sub-array where +ve and zeros are mixed
begin = 0;
while(begin<end) {
/* group all zero together at the end*/
if(arr[begin]==0) {
int temp = arr[begin];
arr[begin] = arr[end];
arr[end] = temp;
end--;
} else {
begin++;
}
}
}``````

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

change the
end = arr.length
to
end = arr.length - 1

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sorting is nlog(n), but there's a linear solution. Not sure if this is optimal, but here's a two pass algorithm that first swaps positive/zero numbers from left to right with negative numbers, and then a similar pass for zeros:

``````void partition(vector<int>& input) {
int next_to_swap = 0;
int ix = 1;
int last_negative = -1;
while (ix < input.size() && next_to_swap < input.size()) {
if (input[next_to_swap] < 0) { next_to_swap++; continue; }
if (input[ix] < 0) {
std::swap(input[ix], input[next_to_swap]);
last_negative = next_to_swap;
}
ix++;
}
next_to_swap = last_negative+1;
ix = next_to_swap+1;
while (ix < input.size() && next_to_swap < input.size()) {
if (input[next_to_swap] == 0) { next_to_swap++; continue; }
if (input[ix] == 0) std::swap(input[ix], input[next_to_swap]);
ix++;
}
}``````

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

I followed the exact 2-pass approach, I dunno what happened and why wasn't I called for the next round.

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

You don't have to do 2 passes. In first pass place the negatives on the left, the positive on the right, and the remaining must be zeroes. As when you initialize an array the value gets initialised with zero so you don't even need to set anything now. Just 1 pass required.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is the a possible solution for this:

``````void Lineararrange(int X[]){
this.X=X;
int i=0,j=0;
int m=X.length-1,n;
while(i<X.length){
//Increase i as long as found negative
while(X[i]<0 && i<X.length)i++;
//Set j=i+1
j=i+1;//X[j] is either 0 or positive
while(j<X.length && X[j]>=0){j++;}
//if j=length finish
if(j>=X.length){
break;
}
//else swap with X[i],increase i
else{
int temp=X[i];
X[i]=X[j];
X[j]=temp;
}
}
//Now we have all negative to the left of i
while(m>0){
//Decrease m as long as found positive
while(X[m]>0 && m>0)m--;
//Set n=m-1
n=m-1;//X[n] is either 0 or negative
while(n>=0 && X[n]<=0 ){n--;}
if(n<=0){
break;
}

//if n=0 finish

//else swap with X[m],decrease m
else{
int temp=X[m];
X[m]=X[n];
X[n]=temp;
}
}
//Now we have all positive to the right of m
output();
}
public void output(){
for(int i=0;i<X.length;i++){
System.out.print(X[i]+",");
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

take zero as pivot element. nd traverse once.compare all elements with zero. anythin less than zero will come to the left and anythin greater than zero will come to the right of zero.. so basically partition around zero.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>
#define SIZE 9
void arrange(int[]);
void swap(int[],int,int);
int main()
{
int array1[SIZE]={-3,1,2,3,0,0,-2,-3,0};
arrange(array1);
int i=0;
for(;i<SIZE;i++)
{
printf("%d\t",array1[i]);
}
getchar();
return 0;
}
void arrange(int array1[])
{
int i = 0;
int first = 0,last = SIZE-1;
while(array1[i] <0)
{
i++;
}
while(i<=last)
{
if(array1[i]==0)
{
i++;
}
else
{
if(array1[i]>0)
{
swap(array1,i,last);
last--;
}
else
{
swap(array1,i,first);
first++;
}
}
}
}
void swap(int array1[ ],int first,int second)
{

int temp = array1[first];
array1[first]=array1[second];
array1[second]=temp;

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

int _tmain(int argc, _TCHAR* argv[])
{
int arr[9] = { 0,0,-1,-1,2,2,0,-2,2};
int startIndex =0;
int EndIndex = 8;
int tmp;
int i =0;
while ( startIndex < EndIndex )
{
if (arr[startIndex] < 0)
{
tmp = arr[i];
arr[i++] = arr[startIndex];
arr[startIndex] = tmp;
}
if (arr[startIndex] > 0 )
{
tmp = arr[startIndex];
arr[startIndex] = arr[EndIndex];
arr[EndIndex--] = tmp;
}
if (arr[startIndex] == 0)
{
startIndex++;
}
}
return 0;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

What about first having 3 variables that will count the no of positive, negative & 0 values once u had that in the second pass u just have to set values in the second pass

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

but you don't need 2 passes. it can be done in just one pass.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

well, since it doesn't say we cannot have an extra array. I will just create an extra array with the same size and initialize to 0.
Then I will scan through the given array, if it's less than 0, then put it at the front (say, a counter that starts at 0). If it's greater than 0, then put it at the end (have a counter that starts at n-1).
It should be done after the first pass since it's initialized to 0's already, so the middle ones are all 0's.

``````public class NegPosArray {
public static int[] partitionArray(int[] array) {
int[] result = new int[array.length];
int leftCount = 0;
int rightCount = array.length - 1;
for (int i = 0; i < array.length; i++) {
if (array[i] < 0) {
result[leftCount] = array[i];
leftCount++;
} else if (array[i] > 0) {
result[rightCount] = array[i];
rightCount--;
}
}
return result;
}

public static void main(String args[]) {
int[] arr = { 1, 2, -4, 0, 0, 2, 3, 7, -6, -13, 5, 8, 0, 2, -5, 3, -2,
5, -16, 0, -23, -25, -6, 1, 0, 0 };
int[] res = partitionArray(arr);

for (int i = 0; i < res.length; i++) {
System.out.print(res[i] + " ");
}
}
}``````

The result is

``````-4 -6 -13 -5 -2 -16 -23 -25 -6 0 0 0 0 0 0 1 5 3 2 8 5
7 3 2 2 1``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````void arrange(int *a,int n)
{
int negative_right_end=0;
int positive_left_end=n-1;
for(int i=0; (i<n || i>positive_left_end);)
{
if(a[i]==0)
i++;
else if(a[i]==-1)
{
swap(a[i],a[negative_right_end]);
negative_right_end++;
}
else if(a[i]==1)
{
swap(a[i],a[positive_left_end]);
positive_left_end--;
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

It is similar to Dutch Nation Flag problem:

Just imagine negatives numbers as 0, zeroes as 1 and positive numbers as 2. Then the problem is to sort the array containing only 0, 1, 2.

Dutch nation flag problem code:

``````Lo := 1; Mid := 1; Hi := N;
while Mid <= Hi do
Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
case a[Mid] in
0: swap a[Lo] and a[Mid]; Lo++; Mid++
1: Mid++
2: swap a[Mid] and a[Hi]; Hi--``````

So for the above problem:

switch cases will be if arr[mid] <0 arr[mid] ==0 and arr[mid]>0

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

The answer is incorrect as it doesnt reparse the taile element swapped.

Comment hidden because of low score. Click to expand.

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.