Microsoft Interview Question Software Engineer in Tests


Country: United States
Interview Type: Phone Interview


Comment hidden because of low score. Click to expand.
15
of 21 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--]);
	}	
}

- Aalok on August 23, 2012 | Flag Reply
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.

- crystal.rishi2 on October 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sunny on December 06, 2012 | Flag
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--]);

- ruth542 on March 02, 2013 | Flag
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;
}

- srikantaggarwal on August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why voted -ve?

- srikantaggarwal on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Shivam Maharshi on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Man its O(n)

- srikantaggarwal on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- srikantaggarwal on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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. :)

- srikantaggarwal on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Shivam Maharshi on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well vote up thn.. :P

- srikantaggarwal on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- srikantaggarwal on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- basavaraja.b on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- babbupandey on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Srikant Aggarwal on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its working for every test case. :)

- Srikant Aggarwal on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Srikant Aggarwal on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bc on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Srikant Aggarwal on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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..

- Prashant R Kumar on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wrong logic...

- sanjeev on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Sanjeev.. Please explain.. why.. :P
Know about the code before commenting... Its mod Dutch Flag Algo... Thanks. @Neo.

- Srikant Aggarwal on August 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- srikantaggarwal on August 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

its perfectly fine..!!

- sgarg on August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aygul on November 15, 2012 | Flag
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;
}

- Shivam Maharshi on August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Shivam Maharshi on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sunny on December 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks for this, I was havig trouble understanding DNF

- ruth542 on March 02, 2013 | Flag
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++;
}
}
}

- Chengyun Zuo on August 22, 2012 | Flag Reply
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;
}

- pranaymahajan on August 24, 2012 | Flag Reply
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,

- hwer.han on August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]

- hwer.han on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good approach.

- maverick on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
youtube.com/watch?v=rZdV64uq5KM

- Anonymous on August 21, 2012 | Flag
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();
}
}

- Anonymous on August 21, 2012 | Flag Reply
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--;
            }
        }
    }

- nj on August 23, 2012 | Flag Reply
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;
        }

- Andy on August 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Bucket sort...

- Kiran on September 01, 2012 | Flag Reply
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++;
		}
    }	
}

- babbupandey on August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- UDawg on August 21, 2012 | Flag
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++;
  }
}

- Martin on August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- babbupandey on August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Shivam Maharshi on August 21, 2012 | Flag
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
			//increase j as long as another negative is not found
			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
			//decrease n as long as another positive is not found
			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]+",");
		}
	}

- musfiqur on August 21, 2012 | Flag Reply
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.

- Anonymous on August 21, 2012 | Flag Reply
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;

}

- Meena on August 21, 2012 | Flag Reply
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;
}

- Nishikant on August 21, 2012 | Flag Reply
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

- Anonymous on August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Shivam Maharshi on August 21, 2012 | Flag
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

- Malluce on August 21, 2012 | Flag Reply
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--;
      }
   }
}

- ankit manit on August 22, 2012 | Flag Reply
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

- neo on August 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Srikant Aggarwal on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More