Bloomberg LP Interview Question
Financial Software Developerswe do not need to scan two arrays. The number of even and odd are same:2/n. while(i<n || j<n) will be enough.
The solution will fail if negative odd numbers appear in either arrays. The reason: (-231 % 2) does not equals to 1!
#include <stdio.h>
#define ODD 1
#define EVEN 0
int main ()
{
int n = 6, i, j, rep = 0, niter = 0, swap;
int ar1[6] = {1, 2, 3, 4, 5, 6}; // Will hold all even numbers
int ar2[6] = {7, 8, 9, 10, 11, 12}; // Will hold all odd numbers
for (i = 0, j = 0 ; rep < n/2 ; niter++)
{
if ((ar1[i]%2 == ODD) && (ar2[j]%2 == EVEN))
{
rep++;
swap = ar1[i];
ar1[i] = ar2[j];
ar2[j] = swap;
i++; j++;
}
else
{
if (ar1[i]%2 == EVEN)
i++;
if (ar2[j]%2 == ODD)
j++;
}
}
for (i = 0 ; i < n ; i++)
printf ("\n ar1[%d] = %d, ar2[%d] = %d", i, ar1[i], i, ar2[i]);
printf ("\nO(n) = %d", niter);
}
O(n) in this algo will be less than or equal to (2*n - 1)..
The code works for negative numbers also when compiled in ANSI C..
Code is in Java but you can get an idea from this. Time complexity O(n)
public static void sortEvenOdd(int[] arr1,int[] arr2){
int index1 =0;
int index2 =0;
int temp;
while((index1 = getNextOdd(index1,arr1)) != -1){
index2 = getNextEven(index2, arr2);
temp = arr1[index1];
arr1[index1] = arr2[index2];
arr2[index2] = temp;
}
}
public static int getNextOdd(int index,int[] arr){
for(int i=index;i<arr.length;i++){
if(arr[i]%2==1){
return i;
}
}
return -1;
}
public static int getNextEven(int index,int[] arr){
for(int i=index;i<arr.length;i++){
if(arr[i]%2==0){
return i;
}
}
return -1;
}
void rmComma(int a1[], int a2[])
{
int pOdd=0;
int pEven=0;
int length1 = 6;//sizeof(a1)/sizeof(int);//a1 supposed to store odd
int length2 = 6;// sizeof(a2)/sizeof(int);
while(pOdd<length1 && pEven<length2)
{
if(a1[pOdd]%2==0)
{
while(a2[pEven]%2!=1)
pEven++;
swap(a1[pOdd], a2[pEven]);
}
pOdd++;
}
}
int i, j, temp, lastIndex;
int array1[10] = {-1,2,3,4,-5,6,7,8,9,10};
int array2[10] = {11,-12,13,14,15,-16,17,18,19,20};
for ( i = 0, lastIndex = 0; i < 10; i++)
{
if(array1[i] % 2 == 0)
{
temp = array1[i];//even number
for(j= lastIndex; j < 10 ; j++)
{
if(array2[j] % 2 == 1) //odd number
{
//exchange
array1[i] = array2[j];
array2[j] = temp;
lastIndex = j;
break;
}
}
}
}
Have 2 pointers, one points at the first non-even number in the array of evens, the other at the first non-odd number in the array of odds. Swap the numbers and increase both pointers (separately) until they find 2 new numbers to be swapped. In-place and linear time. Java:
public static void arrange(int[] e, int[] o) {
int we=0, wo=0;
do {
while (e[we]%2!=0) we++;
while (o[wo]%2==0) wo++;
int tmp=e[we];
e[we]=o[wo];
o[wo]=tmp;
} while (wo<o.length&&we<e.length);
}
int a1[]={9,10,11,12,13,14,15,16};
int a2[]={-1,-2,-3,-4,-5,-6,-7,-8};
int i=0,j=0;
while(i<8)
{
if(a1[i]%2==0)
{
if(a2[j]%2!=0)
{
int temp=a1[i];
a1[i]=a2[j];
a2[j]=temp;
i++;
j++;
}
else
j++;
}
else
i++;
}
for(i=0;i<8;i++)
System.out.print(a1[i]+" ");
System.out.println();
for(i=0;i<8;i++)
System.out.print(a2[i]+" ");
- Girish January 21, 2010