Infosys Interview Question for Site Reliability Engineers


Team: I
Country: United States




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

#include<stdio.h>

int main()
{

int low=0,high,temp;
int array[]={98,-87,75,85,75,-74,-63,-746,987,82,-836,-6453,-745,-947,98};
high= ( sizeof(array)/sizeof(array[low]));
while(low < high)
{
if(array[low] > 0)
{
if(array[high] > 0)
{
high++;
}
}
else if(array[low] < 0)
{
if( array[high] > 0)
{
temp=array[high];
array[high]=array[low];
array[low]=temp;
}
else
{
low--;
}
}
low++;
high--;
}
return 0;
}

- Avi July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Order is not maintained by your code.

- sujita July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
# define SIZE 10
void arrange(int[]);

int main()
{
int array[SIZE] = {3,1,2,2,-2,-3,-2,6,2,3};
arrange(array);
int i;
for(i=0;i<SIZE;i++)
{
printf("\n%d",array[i]);
}
return 0;
}

void arrange(int array[])
{
if(SIZE > 0)
{
int first_n = 0,second_n = 0,pos = 0,i=0,j;
while(array[i]>=0 && i<SIZE)
{
i++;
}
pos = i;
while(i<SIZE)
{
while(array[i]<0 && i<SIZE)
{
i++;
}
if(i<SIZE)
{
first_n = array[pos];
array[pos] = array[i];
for(j=pos+1;j<i;j++)
{
second_n = array[j];
array[j] = first_n;
first_n = second_n;
}
array[i]=first_n;
i++;
pos = pos + 1;
}
}
}
}

- Meena July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are using more than one iteration.

- Neel July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is just an example,generic case is what we are looking for.

- sujita July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] array = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
out put needed :
{3,2,2,3,2,2,3,0,2,-1,-2,-6,-8}

We should only think about this case or we need to implement something more generic?

- TS July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm asking this because if we could focus on only handling this specific case and we're allowed to use at least one more array, I think we could somehow use "bucket sort" like approach.

- TS July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h> //for memcpy


main()
{
int array[] = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
int arraysize= sizeof(array)/sizeof(int);
int i;
int num_of_minus=0;
for(i=0;i<arraysize-num_of_minus-1;i++) // repeat before the begining of minus number array 
{
  if(array[i]<0)
  {
     // Move current minus number at the end of array
     int temp=array[i];
     memcpy(array+i,array+i+1,sizeof(int)*(arraysize-i-1) );
     array[arraysize-1]=temp;
     
     i--; //Current number is overwritten, so check it again.
     num_of_minus++;
  }
}
printf("{");
for(i=0;i<arraysize-1;i++)
{
printf("%d,",array[i]);
}
printf("%d}\n",array[arraysize-1]);

}

- knuhepbg July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is this memcpy() finction in your code ? how to write it in Java ? also is the order maintained ?

- sujita July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it can be replaced with this:

if(array[i]<0)
  {
// Move current minus number at the end of array
     int temp=array[i];
     for(j=i;j<arraysize-1;j++)
         array[j]=array[j+1];
     array[arraysize-1]=temp;

     i--; //Current number is overwritten, so check it again.
     num_of_minus++;
  }

- knuhepbg July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

can be solve in o(n) and using one temp array
int temp[n],i,j,k,l;
i=0;j=n-1;
k=0;
l=n-1;
for(i=0;i<n;i++,j--)
{
if(a[i]>0)
{
temp[k]=a[i];
k++;
}
if(a[j]<0)
{
temp[l]=a[j];
l--;
}
}
// correct me if i am wrong

- rashmi sapmath July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it is equal to two iterations

- Siva Krishna July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>


int main()
{
int array[] = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
int arraysize= sizeof(array)/sizeof(int);
int i,k;
k=0;
int num_of_minus=0;
printf("{");
for(i=0;i<arraysize*2;i++)
{
if(i<arraysize && array[i]>=0)
{
printf("%d,",array[i]);
k++;
}
else if (i>arraysize && array[i-arraysize]<0)
{
if (k==arraysize-1)
printf("%d",array[i-arraysize]);
else
{
printf("%d,",array[i-arraysize]);
k++;
}
}
}
printf("}\n");
system("PAUSE");
return 0;
}

- Junsang Kim July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you have just printed the elements,your array still has some other order.

- sujita July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

public class CCup1 {

	public static void main(String[] args) {
		int[] array = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
		printArray(array);
		array = sortArray(array);
		printArray(array);
	}
	
	private static int[] sortArray(int[] array) {
		int location =0;
		for (int i = 0; i < array.length; i++) {
			if(array[i]>=0) {
				if(i!=location) {
					for (int j = i; j > location; j--) {
						int temp = array[j];
						array[j] = array[j-1];
						array[j-1]= temp;
					}
				}
				location++;
			}
			
		}
		return array;
	}

	private static void printArray(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i]+" ");
		}
		System.out.println("");
	}
}

- Pankaj July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isn't it O(n^2) with 2 for loops ? is it possible in O(n)

...............

- sujita July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, missed the single iteration part. But as its an Array and there is surely sorting involved, sorting can never happen with O(n). At the best it can be O(nlog(n))

- Pankaj July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ok so you are shifting the elements using 2 pointers.

- sujita July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void main()
{
int a[] = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2} , temp[13] = { 0 };
int len =0 ,count = 0, start = 0 ,index =0;
len = sizeof(a) / sizeof(a[0]);

for(int i=0; i<len; i++)
{
if(count != len )
{
if(a[count] > 0)
{
temp[i] = a[count];
if(a[(count-1)] < 0)
{
a[count-1] = a[count];
}

}
if(a[count] < 0)
{
a[start] = a[count];
start++;
if(count != len-1)
i--;
}
count++;
}
else
{
if(a[index] < 0)
{
temp[i] = a[index];
index++;
}
}
}

// printing the value
for(int i =0; i<len; i++)
printf("\n%d" , temp[i]);
}

This is the final code dude , with all the requirement.

- kk July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you do it without using temporary array ? as it will increase space complexity.

- sujita July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah sure I will try it.

- kk July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@sujama is this experienced interview question?
if yes , how many years?

- kk July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

3+ years Java.

- sujita July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Sujama

- kk July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
main()
{
int a[]={1,0,-1,-2,5,-10,11,-11,-5,-4};
int k=0,i=0,l=10;
while(i<l)
{
if(a[i]<0)
k++;
if(a[i]>=0&&k>0)
for(int j=i;j>i-k;j--)
{
int temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
i++;
}

for(i=0;i<l;i++)
printf("%d ",a[i]);
getch();
}

- Anonymous July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is in single iteration
bt o(n) is not maintained

- Anonymous July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

None of the above solutions are valid....need to find out one....can anyone pls share O(n) solution

- Sri July 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let me go back home from office , u will find optimal solution..

- kk July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah! noone soln is correct soln!

- sujita July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can do it using two pointer. As soon u get -ve number track that position and swap it with the pointer value which will be definately further tracking the positive value after this -ve number swap them and increment the pointer untill it gets another negative number.

- kk July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can make one at office :P . I guess with your 2 pointer solution the order will be changed ... :|

- sujita July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In office i just make only note of questions which i will do at home. i know it wd'nt take much tym , though idont prefer. lots of work is pending . with two pointer order will only change for last two value that u have to take care of.

- kk July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about this one, guys? It is O(n), but it has 2 iterations. Of course if the request was 1 iteration we need to find something better

import java.util.Arrays;

/**
 *
 * @author ggiscan
 */
public class ShiftNegativesToEnd {

    static void shiftNegativesToEnd(int[] arr) {
        int[] collector = new int[arr.length];
        int cnt_negative = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                collector[cnt_negative++] = arr[i];
            } else {
                arr[i - cnt_negative] = arr[i];
            }
        }
        System.arraycopy(collector, 0, arr, arr.length - cnt_negative, cnt_negative);
    }

    public static void main(String[] args) {
        int[] testArr = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
        int[] expArr = {3,2,2,3,2,2,3,0,2,-1,-2,-6,-8};
        shiftNegativesToEnd(testArr);
        assert(Arrays.equals(testArr, expArr));
    }
}

- GSG July 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void main()
{
int a[] = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
int len =0;
int *ptr1 , *ptr2;
int flag = 0 ;
ptr1 = ptr2 = a;
len = sizeof(a) / sizeof(a[0]);

for(int i=0; i<len; i++)
{
if(a[i] < 0 && flag == 0)
{
ptr1 = a+i;
flag = 1;
}

if(a[i] >= 0 && flag == 1)
{
a[i] = a[i] ^ *ptr1;
*ptr1 = a[i] ^ *ptr1;
a[i] = a[i] ^ *ptr1;
ptr1++;

*ptr1 = a[i] ^ *ptr1;
a[i] = a[i] ^ *ptr1;
*ptr1 = a[i] ^ *ptr1;

ptr2 = ptr1;
if(*++ptr2 != a[i])
{
*ptr2 = a[i] ^ *ptr2;
a[i] = a[i] ^ *ptr2;
*ptr2 = a[i] ^ *ptr2;
}
}

}

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

}

@sujama Check it.

- kk July 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This won't work in java..

- sujita July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes it wo'nt work ! i know only c language. you can convert it into java. it's having o(n) complexity.

- kk July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hmm,I have no clue how to convert it in java..may be if you can explain the logic a bit..then I might try it out.Thanks

- sujita July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have taken first pointer. i m checking first minus value if i get any minus value (-1) i will point my first pointer to that value. after this minus value if i get any positive value i will swap this pointer value with my positive value. like -1 and 2 will be swapped and pointer will now point to -2...
so ur array wd be now like this..
3 2 -2 -1 2 3 2 -6 2 3 -8 0 2
at the same tym u have to maintain minus order also so swap -2 and -1 to
3 2 -1 -2 2 3 2 -6 2 3 -8 0 2......
your pointer wd be in -1 position ur loop index wd be now in 2 positive value swap them
3 2 2 -2 -1 3 2 -6 2 3 -8 0 2
swap again -1 and -2 also to maintain order..
3 2 2 -1 -2 3 2 -6 2 3 -8 0 2
3 2 2 3 -2 -1 2 -6 2 3 -8 0 2
3 2 2 3 -1 -2 2 -6 2 3 -8 0 2
3 2 2 3 2 -2 -1 -6 2 3 -8 0 2
3 2 2 3 2 -1 -2 -6 2 3 -8 0 2
3 2 2 3 2 2 -2 -6 -1 3 -8 0 2
3 2 2 3 2 2 -1 -6 -2 3 -8 0 2
here you have to take care of -6 and -2 also then swap them to maintain order thas y one more condition
3 2 2 3 2 2 -1 -2 -6 3 -8 0 2
pointer wd be in -1 and index i has been reached in 3 now
3 2 2 3 2 2 3 -2 -6 -1 -8 0 2
3 2 2 3 2 2 3 -1 -6 -2 -8 0 2
3 2 2 3 2 2 3 -1 -2 -6 -8 0 2

........keep doing it till the i == length..

- kk July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

check for a[] = {3,-1,-2,2,2,-3,2,-6,2,-3,-8,0,2}
o/p is not correct .

- Shobhit July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes i agree to maintain the order of minus values i need some different logic...

- kk July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c#

MoveNext(new int[] { 3, -1, -2, 2, 2, 3, 2, -6, 2, 3, -8, 0, 2 });

        private void MoveNext(int[] values, int i = 0)
        {
            if (i >= values.Length)
            {
                return;
            }
            else if (values[i] < 0 && Arrange(values, i) == false)
            {
                return;
            }
            else
            {
                MoveNext(values, i + 1);
            }
        }
        private bool Arrange(int[] values, int pos, int next = 1)
        {
            if ((pos + next) >= values.Length)
            {
                return false;
            }
            else if (values[pos + next] >= 0)
            {
                int temp = values[pos];
                values[pos] = values[pos + next];
                for (int i = next; i > 1; i--)
                {
                    values[pos + i] = values[pos + i - 1];
                }
                values[pos + 1] = temp;
                return true;
            }
            else
            {
                return Arrange(values, pos, next + 1);
            }
        }

- Anonymous July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Going through all the codes I guess this is not possible in O(n) time..the best solution I got here is using 2 loops,inner loop for shifting the elements.
anyways Q is still open hope someone gets some logic to find it in O(n)

- sujita July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

#include <stdio.h>

void printarray(int array[],int arraysize,int nCursor)
{
	int i;
	for(i=0;i<arraysize;i++)
		printf("%3d ",array[i]);
	printf("\n");
	if(nCursor>=0)
	{
		for(i=0;i<nCursor;i++)
		   printf("    ",array[i]);

		printf("  *\n");
	}
}
main()
{
	
	int array[] = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
	int arraysize= sizeof(array)/sizeof(int);
	int i;
	for(i=1;i<arraysize;i++)
	{
		printarray(array,arraysize,i);

     	if(array[i-1]>=0 && array[i]>=0) 
     		continue;
     	
     	if(array[i-1] < 0  && array[i]>=0) //-2 , 2
     	{
     		int temp = array[i];
     		array[i]=array[i-1];
     		array[i-1]=temp;
     		i-=2; //Move the cursor back
     	}

	}
	printarray(array,arraysize,-1);
}

- knuhepbg July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

3  -1  -2   2   2   3   2  -6   2   3  -8   0   2 
      *
  3  -1  -2   2   2   3   2  -6   2   3  -8   0   2 
          *
  3  -1  -2   2   2   3   2  -6   2   3  -8   0   2 
              *
  3  -1   2  -2   2   3   2  -6   2   3  -8   0   2 
          *
  3   2  -1  -2   2   3   2  -6   2   3  -8   0   2 
      *
  3   2  -1  -2   2   3   2  -6   2   3  -8   0   2 
          *
  3   2  -1  -2   2   3   2  -6   2   3  -8   0   2 
              *
  3   2  -1  -2   2   3   2  -6   2   3  -8   0   2 
                  *
  3   2  -1   2  -2   3   2  -6   2   3  -8   0   2 
              *
  3   2   2  -1  -2   3   2  -6   2   3  -8   0   2 
          *
  3   2   2  -1  -2   3   2  -6   2   3  -8   0   2 
              *
  3   2   2  -1  -2   3   2  -6   2   3  -8   0   2 
                  *
  3   2   2  -1  -2   3   2  -6   2   3  -8   0   2 
                      *
  3   2   2  -1   3  -2   2  -6   2   3  -8   0   2 
                  *
  3   2   2   3  -1  -2   2  -6   2   3  -8   0   2 
              *
  3   2   2   3  -1  -2   2  -6   2   3  -8   0   2 
                  *
  3   2   2   3  -1  -2   2  -6   2   3  -8   0   2 
                      *
  3   2   2   3  -1  -2   2  -6   2   3  -8   0   2 
                          *
  3   2   2   3  -1   2  -2  -6   2   3  -8   0   2 
                      *
  3   2   2   3   2  -1  -2  -6   2   3  -8   0   2 
                  *
  3   2   2   3   2  -1  -2  -6   2   3  -8   0   2 
                      *
  3   2   2   3   2  -1  -2  -6   2   3  -8   0   2 
                          *
  3   2   2   3   2  -1  -2  -6   2   3  -8   0   2 
                              *
  3   2   2   3   2  -1  -2  -6   2   3  -8   0   2 
                                  *
  3   2   2   3   2  -1  -2   2  -6   3  -8   0   2 
                              *
  3   2   2   3   2  -1   2  -2  -6   3  -8   0   2 
                          *
  3   2   2   3   2   2  -1  -2  -6   3  -8   0   2 
                      *
  3   2   2   3   2   2  -1  -2  -6   3  -8   0   2 
                          *
  3   2   2   3   2   2  -1  -2  -6   3  -8   0   2 
                              *
  3   2   2   3   2   2  -1  -2  -6   3  -8   0   2 
                                  *
  3   2   2   3   2   2  -1  -2  -6   3  -8   0   2 
                                      *
  3   2   2   3   2   2  -1  -2   3  -6  -8   0   2 
                                  *
  3   2   2   3   2   2  -1   3  -2  -6  -8   0   2 
                              *
  3   2   2   3   2   2   3  -1  -2  -6  -8   0   2 
                          *
  3   2   2   3   2   2   3  -1  -2  -6  -8   0   2 
                              *
  3   2   2   3   2   2   3  -1  -2  -6  -8   0   2 
                                  *
  3   2   2   3   2   2   3  -1  -2  -6  -8   0   2 
                                      *
  3   2   2   3   2   2   3  -1  -2  -6  -8   0   2 
                                          *
  3   2   2   3   2   2   3  -1  -2  -6  -8   0   2 
                                              *
  3   2   2   3   2   2   3  -1  -2  -6   0  -8   2 
                                          *
  3   2   2   3   2   2   3  -1  -2   0  -6  -8   2 
                                      *
  3   2   2   3   2   2   3  -1   0  -2  -6  -8   2 
                                  *
  3   2   2   3   2   2   3   0  -1  -2  -6  -8   2 
                              *
  3   2   2   3   2   2   3   0  -1  -2  -6  -8   2 
                                  *
  3   2   2   3   2   2   3   0  -1  -2  -6  -8   2 
                                      *
  3   2   2   3   2   2   3   0  -1  -2  -6  -8   2 
                                          *
  3   2   2   3   2   2   3   0  -1  -2  -6  -8   2 
                                              *
  3   2   2   3   2   2   3   0  -1  -2  -6  -8   2 
                                                  *
  3   2   2   3   2   2   3   0  -1  -2  -6   2  -8 
                                              *
  3   2   2   3   2   2   3   0  -1  -2   2  -6  -8 
                                          *
  3   2   2   3   2   2   3   0  -1   2  -2  -6  -8 
                                      *
  3   2   2   3   2   2   3   0   2  -1  -2  -6  -8 
                                  *
  3   2   2   3   2   2   3   0   2  -1  -2  -6  -8 
                                      *
  3   2   2   3   2   2   3   0   2  -1  -2  -6  -8 
                                          *
  3   2   2   3   2   2   3   0   2  -1  -2  -6  -8 
                                              *
  3   2   2   3   2   2   3   0   2  -1  -2  -6  -8 
                                                  *
  3   2   2   3   2   2   3   0   2  -1  -2  -6  -8

- knuhepbg July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Move back cursor by 2? How can you keep this constant? It will work for this example only.

- Noob July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i-=2 and i++ in for(). so it equals -- for next iteration.

- knuhepbg July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tested with this: {-3,1,2,-2,-2,-3,-2,6,-2,-3,8,0,-2}; and the result was:
1 2 6 8 0 -3 -2 -2 -3 -2 -2 -3 -2

- knuhepbg July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

code looks fine,but is it a single iteration ? coz you are reducing i's value..and your iterations are increasing due to that..

- sujita July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't know what "single iteration" exactly means, but I don't believe there would be no other way which generates less iterations than this if we don't use memcpy...

- knuhepbg July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To me single iteration you are accessing the array elements only one time by traversing the original array only once.

- Psycho July 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;


public class ArrayOrder
{
public static void main(String args[])
{
	int[] array = new int[]{3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
	int negativeIndex = -1;
	LinkedList<Integer> list = new LinkedList<Integer>();
	for(int i=0;i<array.length;i++)
	{
		if(array[i] >=0)
		{
			if(negativeIndex != -1 && negativeIndex < i)
			{
			  list.add(negativeIndex, array[i]);
			  negativeIndex++;
			}
			else
			{
				list.add(array[i]);
			}
		}
		else
		{
			list.add(array[i]);
			if(negativeIndex == -1)
			{
			  negativeIndex = i;
			}
		}
	}
	for(Integer value :  list.toArray(new Integer[0]))
	{
		System.out.println(value.intValue());
	}
}
}

- Raghava July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above code maintains O(n) complexity. And linked list is the best option when dealing with array insertion and deletion in random places.

- Raghava July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hmmm..

- sujita July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you have increased space complexity dude.... this logic is already implemented above.

- kk July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
main()
{
int a[13]= {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
int c[13];
int b,i,j;

for(i=1;i<13;i++)
{
for(j=0;j<13-i;j++)
{
if(a[j]<0)
{
if(a[j+1]>=0)
{
b=a[j+1];
a[j+1]=a[j];
a[j]=b;
}

}
}
}
for(j=0;j<13;j++)
printf("%2d ",a[j]);
}

- yogesh kumar sharma July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void shiftNegative(int arr[]){
		boolean negativefound = false;
		int negativeIndex = -1;
		for(int i=0;i<arr.length; i++){
			
			if(arr[i] > -1){
				if(negativefound){
					for(int j=i; j>negativeIndex; j--){
						swap(arr,j,j-1);
					}
					negativeIndex++;
				}
			}else{
				if(!negativefound){
					negativefound = true;
					negativeIndex = i;
				}
			}
		}
	}

private static void swap(int arr[], int src, int dest){
		int temp = arr[src];
		arr[src] = arr[dest];
		arr[dest] = temp;
	}

- Pradeep July 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[]={3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
int SIZE=sizeof(a);
int b[SIZE];
for(int i=0;i<SIZE;i++)
{
if(a[i]<0)
{a[i]=*b;
b=b+1;}
else
{
printf(" ",+a[i])
}
}//for loop end
for(int i=0;i<SIZE;i++)
printf(" ",+b[i]);


Space complexity will be little bit more then O(n)
Time complexity=O(n)
output:322322302-1-2-6-8

- abh007 July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about recursion?

class mySequence{
static int neg=0;
static int pos=0;
public static void main(String args[])
{

int a[]={3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
mySequence ms = new mySequence();
ms.sequence(a,0,0,0,0,a.length);
for (int i=0;i<a.length;i++)
System.out.print(a[i]+"");
}

void sequence(int a[], int p, int ind, int i,int n,int len2){
if(i<len2){
n = a[i];
if(a[i]>=0){
ind = 1;
p++;
pos = p;

}
else{
ind = -1;
neg++;
}
i++;
sequence(a,p,ind,i,n,len2);


System.out.println(n +" "+ ind+" "+p+" "+neg);
if(ind==1){
a[p-1]=n;
//p--;
}
else{
a[pos+neg-1]=n;
neg--;
System.out.println(" "+neg);
}
}

}

}

O(n) time

- Imon August 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n)

public static void ChangeArray(int[] a) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		int[] returnArray = new int[a.length];

		int j = 0;
		for (int i = 0; i < a.length; i++) {
			if (a[i] < 0)
				list.add(a[i]);
			else {
				returnArray[j] = a[i];
				j++;
			}
		}
		System.out.println(list);
		for (int i = j; i < returnArray.length; i++) {
			int a1 = list.removeFirst();
			System.out.println(a1);
			returnArray[i] = a1;

		}

		for (int i = 0; i < returnArray.length; i++)
			System.out.print(returnArray[i] + ", ");
	}

- dandy August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void ChangeArray(int[] a) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		int[] returnArray = new int[a.length];

		int j = 0;
		for (int i = 0; i < a.length; i++) {
			if (a[i] < 0)
				list.add(a[i]);
			else {
				returnArray[j] = a[i];
				j++;
			}
		}
		System.out.println(list);
		for (int i = j; i < returnArray.length; i++) {
			int a1 = list.removeFirst();
			System.out.println(a1);
			returnArray[i] = a1;

		}

		for (int i = 0; i < returnArray.length; i++)
			System.out.print(returnArray[i] + ", ");
	}

- dandy August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// in-place, O(n2) for the second step.
void f(int* arr)
{
    // step 1: switch positive with negative
    int 1stNeg, headNeg;
    //1stNeg: the 1st negative in original arr.
    //headNeg: the 1st negative in current arr.
    
    1stNeg = headNeg = -1;
    
    for(int i=0;i<strlen(arr);++i)
    {
    	if(arr[i]<0)
    	{
    	    if(1stNeg<-1)
    	    {
    	        1stNeg = i;
    	    }
    	    
    	    if(headNeg < -1)
    	    {
    	        headNeg = i;
    	    }    	    
    	}
    	else
    	{
    	    if(headNeg>-1)
    	    {
    	         swap(arr[headNeg], arr[i]);
    	    }
    	    
    	    if(headNeg == 1stNeg)
    	    {
    	         1stNeg = i;
    	    }
    	    
    	    headNeg++;
    	}
    }
    
    
    //step 2: shift the out of order negative numbers to make them in order. 
    //O(n2) time complexity.
    if(headNeg != 1stNeg)
    {
        for(int i=1stNeg; i<strlen(arr); ++i)
        {
             for(int j=1stNeg; j>headNeg; j--)
             {
                 swap(arr[j], arr[j-1]);
             }
             
             headNeg++;
        }
    }
}

- jiangok2006 August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I m doing. It looks it will take two iterations to find the answer. Single iteration seems impossible. I mean traversing each element only once.

- Psycho August 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

void printarray(int array[],int arraysize,int nCursor)
{
int i;
for(i=0;i<arraysize;i++)
printf("%3d ",array[i]);
printf("\n");

}

main()
{

int array[] = {-1,3,-2,2,2,3,2,-6,2,3,-8,-7,2};
int arraysize= sizeof(array)/sizeof(int);
int i = 0 ;
int nxt_pstv_inx = 0 ;
int ngtv_arry_inx = 0;
int ngtv_array[10]={0,};

printarray(array,arraysize,i);
for(i=0 ; i < arraysize ; i++)
{
if(array[i] >= 0 )
{
array[nxt_pstv_inx]=array[i];
nxt_pstv_inx++;
}
else
{
//push_to_fifo(arr[i])
ngtv_array[ngtv_arry_inx]=array[i];
ngtv_arry_inx++;
}
}
memcpy(array+nxt_pstv_inx,ngtv_array,ngtv_arry_inx*sizeof(int));


printarray(array,arraysize,i);
printf("ngtv_arry_inx is %d\n",ngtv_arry_inx);
return 0;
}
~
~

- Manjunatha C Achar February 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) traverse the array
2) if element are positive number update its position(index) to global variable for next positive number. i.e., stored "position(index) + 1" is next seqential occuring positive number.
3) if element are negative number push the element(FIFO). currently using negative seperate array
4) finally memcpy negative array and and original array.

#include <stdio.h>

void printarray(int array[],int arraysize,int nCursor)
{
        int i;
        for(i=0;i<arraysize;i++)
                printf("%3d ",array[i]);
        printf("\n");

}

main()
{

        int array[] = {-1,3,-2,2,2,3,2,-6,2,3,-8,-7,2};
        int arraysize= sizeof(array)/sizeof(int);
        int i = 0 ;
        int nxt_pstv_inx  = 0 ;
        int ngtv_arry_inx = 0;
        int ngtv_array[10]={0,};

        printarray(array,arraysize,i);
        for(i=0 ; i < arraysize ; i++)
        {
                if(array[i] >= 0 )
                {
                        array[nxt_pstv_inx]=array[i];
                        nxt_pstv_inx++;
                }
                else
                {
                        //push_to_fifo(arr[i])
                        ngtv_array[ngtv_arry_inx]=array[i];
                        ngtv_arry_inx++;
                }
        }
        memcpy(array+nxt_pstv_inx,ngtv_array,ngtv_arry_inx*sizeof(int));


        printarray(array,arraysize,i);
        printf("ngtv_arry_inx is %d\n",ngtv_arry_inx);
        return 0;
}

- Anonymous February 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python:

{{
lst = [3,-1,-2,2,2,3,2,-6,2,3,-8,0,2]
pos = []
neg = []
for i in lst:
if i >= 0:
pos.append(i)
else:
neg.append(i)

output = pos + neg
}}

- yummyravioli June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is not possible to do it in O(n) and without any extra spaces

- juliusjun March 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AllNegativeAtEnd {

	public static void main(String[] args) {

		int[] arr = new int[] { 3, -1, -2, 2, 2, 3, 2, -6, 2, 3, -8, 0, 2 };

		int i = 0;
		int j = arr.length;

		while (i < arr.length && i < j) {

			if (arr[i] < 0) {

				int tmp = arr[i];

				int k = i;

				while (k < arr.length - 1) {
					arr[k] = arr[k + 1];
					k++;
				}
				arr[k] = tmp;
				j--;
				if (arr[i] < 0) {
					continue;
				}

			}
			i++;
		}

		for (int a : arr)
			System.out.println(a);

	}
}

- cpeeyush December 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

main()
{
int a[] = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
int i=0,j=12, temp=0;
for(i=12;i>0;i--)
{
if(a[i]<0)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
j--;
}
}
for(i=0;i<13;i++)
{
printf("%d ",a[i]);
}
}

- Anonymous July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will not maintain order

- Anonymous July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

{{Code is wrong, No order maintained}}

- niranjan.singh July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think they meant O(n).... You can do first pass of array to store all positives and -ves in two tem arrays and now do a second pass to copy these into original first +ves and than -ves
Time O(n)
Space O(n)

- loveCoding July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can't take 2 temp arrays here.

- sujita July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if two temp arrays are not taken it wont b possible in single pass.

- codinglearner July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

1) Iterate over array from the end.
2) Maintain two pointers
a) positivePtr - points to the latest positive element in array
b) negativePtr - points to the latest negative element in array
3) Make sure that positivePtr >negativePtr so that when you swap elements negative value go to the right and positive to the left side
4) After the swap decrements both pointers

Time O(n), space O(1)
Code:

public static void main(String[] args) {

	int[] arr = { 3, -1, -2, 2, 2, 3, 2, -6, 2, 3, -8, 0, 2 };

	int positivePtr = arr.length - 1;
	int negativePtr = arr.length - 1;

	System.out.println(Arrays.toString(arr));
	while (positivePtr >= 0 && negativePtr >= 0) {
	    if (arr[positivePtr] < 0) {
		positivePtr--;
	    } else {
		if (negativePtr >= positivePtr || arr[negativePtr] >= 0) {
		    negativePtr--;
		} else {
		    int tmp = arr[positivePtr];
		    arr[positivePtr] = arr[negativePtr];
		    arr[negativePtr] = tmp;
		    negativePtr--;
		    positivePtr--;
		}
	    }
	}
	System.out.println(Arrays.toString(arr));
    }

- thelineofcode December 10, 2013 | Flag Reply


Add a Comment
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.

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