CareerCup

This problem is well known as no solution, save your time to work on other questions.

You can use a Binary Search Tree with '0' as the root element. they get sorted automatically and use a pre order traversal to get the elements in the order. We go through the array only once, and move each element in an array to the tree. We traverse through the tree to print the elements. I am not sure if this is the solution, but i guess this can be a solution.

Are you sure both O(n), no extra space are required conditions?

No pre order traversal you will not get the same order !Think of a test case like this

1,7,-5,9,-3,15 -12,

in this case according to pre order traversal you will get -12 instead of -5

how do you even rearrange elements in an array without ANY extra space

Could it be done in constant extra space, independent of 'n'?

Unless this is a linked list, I don't see a way of doing it in O(n) time and O(1) space

I agree with GekkoGordan . There is O(nlogn) solution without space but no O(n) solution.

1. Keep 2 indexes n1,n2
2. if n1 is -ve then fwd n1 till u find next -ve no.
3. swap values at n1 and n1-1 till u reach n2-1 position.
4. In 2nd step take start with +ve no. if u see first no. as +ve

#include<stdio.h>

void swap(int *a, int *b)
{
int temp;
printf("\nSwapping %d and %d",*a,*b);
temp = *a;
*a = *b;
*b = temp;
}

int main()
{
int a[10] = {-5,2,3,-4,-6,7,8,9,-1,0};
int n1=-1,n2=-1,k=-1;
int p1=-1,p2=-1,l=-1;
int i = 0;
int pos = 0;
int count = 0;
printf("Given array: ");

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

printf("\n");

i=0;

if(a[0] > 0)
{
p1 = 0;
pos = 1;
}
else
n1 = 0;


if(!pos)
{
do
{
while(i<10 && a[++i] > 0);

if(a[i] < 0)
{
n2 = i;

while(n2 > n1+1)
{
swap(&a[n2], &a[n2-1]);
count++;
n2--;
}
n1++;
}
}while(i<10);
}
else
{
do
{
while(i<10 && a[++i] > 0);

if(a[i] < 0)
{
n2 = i;

while(n2 > n1+1)
{
swap(&a[n2], &a[n2-1]);
n2--;
}
n1++;
}
}while(i<10);
}

printf("\n");

printf("Output: ");

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

printf("\nTotal swaps: %d",count);

return 1;
}

How about this?
1.Represent them as linked lists.
2.In the first pass, keep scanning for negative numbers.
3.When you hit the first negative number, compare it with the next number. If it's a positive number, swap both.
4.Continue step 3 until you have pushed the first negative number to the next occurring negative number in the list.
5.When you do this in the first pass, you will end up with all negative numbers accumulated in "pockets" but not necessarily together.
6.In the 2nd pass,scan for the first negative number. Redirect the previous number to point to the next positive number appearing after the negative number pocket. Similarly, the end of the positive numbers pockets should be made to point to the beginning of the same negative number pocket.
7.Repeat step 6 until end of list.

Essentially, you are creating chunks of positives and negatives and then rearranging the chunks to collect the positives on one side and negatives on the other.

I agree with you Vinod. Having a linkedlist gives us an advantage on swapping a series of number w/o too much energy. However, it appears that we are only given an array and no extra space for a better structure like linkedlist. It seems to me that achieving O(n) with swapping is not possible.

Here's a solution in java using LinkedList with O(n) complexity and no extra space:

public static LinkedList segregatePlusMinus(LinkedList input)
			throws Exception {
		LinkedList plusStart = null;
		LinkedList minusStart = null;
		LinkedList current = input;
		while (current != null && (plusStart == null || minusStart == null)) {
			if (Integer.parseInt(current.getValue()) >= 0 && plusStart == null)
				plusStart = current;
			else if (Integer.parseInt(current.getValue()) < 0
					&& minusStart == null)
				minusStart = current;
			current = current.getNext();
		}

		LinkedList plusCurrent = plusStart;
		LinkedList minusCurrent = minusStart;
		current = input;

		while (current != null) {
			if (plusCurrent != current
					&& Integer.parseInt(current.getValue()) >= 0) {
				plusCurrent.setNext(current);
				plusCurrent = plusCurrent.getNext();
			} else if (minusCurrent != current
					&& Integer.parseInt(current.getValue()) < 0) {
				minusCurrent.setNext(current);
				minusCurrent = minusCurrent.getNext();
			}
			current = current.getNext();
		}
		plusCurrent.setNext(null);
		minusCurrent.setNext(null);

		minusCurrent.setNext(plusStart);
		current = minusStart;
		return current;
	}

The key to this question is to first find the number that's closest to 0 (order n worst case). Use this as a pivot in the quickselect procedure such taht all elements less than the pivot are on one side and the elements greater than the pivot is on the other side. This can be done in worst case order n using quickselect. The worst case order n comes from the fact that the chosen pivot is such that there's a good proportion of elements below and above the pivot value.

Does no extra space mean no stack space as well ? (I know it does not, but did the interviewer expect some crazy recursive solution ?

i have an idea. Instead of trying to partition this array into +ve group and -ve group, in fact, we just need to put all the negative numbers to the front of the array.
Steps:
1. find first negative number, and move the negative number to the front by swapping with the numbers before it
2. find the next negative number, and keep doing the swapping to move till the number before it is a negative number
3. repeat the 2nd step until no negative can be found

ex:
1 7 -5 9 -12 15 ==>find the fist negative number "-5"
1 -5 7 9 -12 15 ==>do swapping to move "-5" to the front
-5 1 7 9 -12 15
-5 1 7 -12 9 15 ==>find the 2nd negative number, do swapping
-5 1 -12 7 9 15
-5 -12 1 7 9 15 ==>stop swapping "-12"
==>done because no more negative number

Because function order() is called N times, there are N variable "i" in the stack. That is the extra space of O(N)

The best I can get is a O(N) algo giving -5 -12 1 9 7 15 using a couple of pointers. Linked list would make this prob a piece of cake...

Start at the end of the array. Going backwards look for the first -ve. PUSH it at the front of the array. Keep going from further back until you have processed all -ves..

instead of a linked list, even if we r allowed another array of the same size,
then we can do this simple in 2 passes,

1st pass: go through the source array and copy all +ve numbers to the destination array
2nd pass: set the source pointer on the source array back to 0 while the pointer on the destination array remains the same and now copy all the -ve numbers to the new array.
Return the destination array.
This is much simpler!

Suggested by my friend manikandan. felt bad after realizing


find whether the number 0 is present in the array.
if yes,
use it as pivot in quicksort partition
else
find the +ve number closest to zero, use it as pivit in qsort partition

O(n) inplace algorithm

// Partition.cc
// (c) souravgh@usc.edu
// Mon Feb 28 1201
#include <stdio.h>

#define Swap(a,b) {\
  int t = a;\
  a = b;\
  b = t;\
  }

void partition (int *arrIntPtr, int sizeInt) {
  int negPtrInt = 0, posPtrInt = 0;

  // Find the no. of -ve no.s
  for (int indexInt = 0; indexInt < sizeInt; indexInt++) {
    posPtrInt = (arrIntPtr[indexInt] < 0) ? posPtrInt + 1 : posPtrInt;
  }

  int negCountInt = posPtrInt;
  // Partition.
  for (int currPtrInt = 0; currPtrInt < sizeInt && currPtrInt < negCountInt; ) {
    if (arrIntPtr[currPtrInt] < 0) { // -ve
      if (currPtrInt == negPtrInt) {
	negPtrInt++;
	currPtrInt++;
	continue;
      }
   
      Swap (arrIntPtr[negPtrInt], arrIntPtr[currPtrInt]);
      negPtrInt++;
    } else { // 0 or +ve
      if (currPtrInt == posPtrInt) {
	posPtrInt++;
	currPtrInt++;
	continue;
      }
      
      Swap (arrIntPtr[posPtrInt], arrIntPtr[currPtrInt]);
      posPtrInt++;
    }
  }
}

int main (void) {
  int a[] = {1, 7, -5, 9, -12, 15};

  partition (a, 6);

  for (int indexInt = 0; indexInt < 6; indexInt++) {
    fprintf (stdout, "%d ", a[indexInt]);
  }
  fprintf (stdout, "\n");

  return 0;
}

O (n) time. O (1) space.

What about this algorithm.

public int[] Rearrange(int[] a)
        {
            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] < 0)
                {
                    for (int j = i; j >= 1; j--)
                    {
                        if (a[j - 1] > 0)
                        {
                            int temp = a[j];
                            a[j] = a[j - 1];
                            a[j - 1] = temp;
                        }
                    }
                }
            }
            return a;
        }

Can't we do this?

count=0;
if(a[i]<0)
{
temp=a[i];
a[i]=a[count];
a[count]=temp;
count++;
}

that code will not work

We should use the partition method used in quicksort (in place).

Who can give the code of the partition method?

How about this approch in C#? Is not O(n) exactly but neither O(n^2)

class Program
{
static void Main(string[] args)
{
//int[] input = { 1, 7, -5, 9, -12, 15 };
int[] input = { 5, -1, 3, -2, 0, 3, -7, 4, -6 };
int[] result = OrderByOrderApperance(input);

Display(result);

Console.Read();
}

public static int[] OrderByOrderApperance(int[] input)
{
int p = 0;
int q = 0;

int i = 0;

int count = 0;
while (i < input.Length)
{
if (input[i] < 0)
{
if (q <= i)
{
Swap(input, i, p);

if (p == q)
q++;

if (p > 1)
{
i = p--;
}

//Display(input);
}
else
{
i = q;
p = 0;
}
}
else
{
if (p > 0)
p++;
else
p = i;

i++;
}

count++;
}

return input;
}

private static int[] Swap(int[] input, int a, int b)
{
if (a != b)
{
input[a] ^= input[b];
input[b] ^= input[a];
input[a] ^= input[b];
}

return input;
}

private static void Display(int[] input)
{
for (int i = 0; i < input.Length; i++)
{
Console.Write(" {0} ", input[i]);
}
Console.WriteLine();
}
}

How about this approch in C#? Is not O(n) exactly but neither O(n^2)

class Program
    {
        static void Main(string[] args)
        {
            //int[] input = { 1, 7, -5, 9, -12, 15 };
            int[] input = { 5, -1, 3, -2, 0, 3, -7, 4, -6 };
            int[] result = OrderByOrderApperance(input);

            Display(result);

            Console.Read();
        }

        public static int[] OrderByOrderApperance(int[] input)
        {
            int p = 0;
            int q = 0;

            int i = 0;

            int count = 0;
            while (i < input.Length)
            {
                if (input[i] < 0)
                {
                    if (q <= i)
                    {
                        Swap(input, i, p);

                        if (p == q)
                            q++;

                        if (p > 1)
                        {
                            i = p--;
                        }

                        //Display(input);                   
                    }
                    else
                    {
                        i = q;
                        p = 0;
                    }
                }
                else
                {
                    if (p > 0)
                        p++;
                    else
                        p = i;

                    i++;
                }

                count++;
            }

            return input;
        }

        private static int[] Swap(int[] input, int a, int b)
        {
            if (a != b)
            {
                input[a] ^= input[b];
                input[b] ^= input[a];
                input[a] ^= input[b];
            }

            return input;
        }

        private static void Display(int[] input)
        {
            for (int i = 0; i < input.Length; i++)
            {
                Console.Write(" {0} ", input[i]);
            }
            Console.WriteLine();
        }
    }