CareerCup

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

#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;
}

#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;
}
}
}
}

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?

#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]);

}

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

#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;
}

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("");
	}
}

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.

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

#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();
}

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

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

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.

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

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)

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

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

#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]);
}

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

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

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

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] + ", ");
	}

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] + ", ");
	}

// 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++;
        }
    }
}

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.

#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;
}
~
~

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

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

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

	}
}

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

{{Code is wrong, No order maintained}}

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)

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