CareerCup

let a[] be d array...where v have 2 store the number.
let i point's to 0th loc of a[] and j point's to last index(last index is nothing but d last index of given array.)
check if func returns 1 then store that number at ith loc and increment i by 1.
if func returns 0 then store that number at jth loc and decrement j by 1.
finally array a[] wil have required result.

Dutch national flag once again. (2 colours, though).

Counting sort will do this in O(N + 2), but it will also require O(N + 2) extra space.

if (1<<N > UINT_MAX) then, below procedure can be followed.

void arrange(int Arr[], int Arr_len)
{
  unsigned int chk = 0;
  for (int i=0; i<Arr_len; i++)
  {
    chk = chk | 1<<i;
  }

  int a = 0;
  int b = 0;

  while(1)
  {
    if(chk&(1<<a)<1)
    {
      a++;
    }
    if(chk&(1<<b)>1)
    {
      b++;
    }
    if(a>=Arr_len && b>=Arr_len) break;

    swap(Arr[a], Arr[b]);
    chk = chk | 1<<b;
  }
}

Since no one has actually posted code for it, here is a solution using a 2 color Dutch National Flag algorithm. O(N) time, O(1) space

public class YahooPartitionArray {

	public static void main(String[] args) {
		int a[] = new int[] {4,5,2,4,3,9,8,1};
		partition(a, new SomeInterface() {
			@Override
			public int someFunction(int i) {
				if (i % 2 == 0) {
					return 1;
				}
				else {
					return 0;
				}
			}
		});
		System.out.println(Arrays.toString(a));
	}

	interface SomeInterface {
		public int someFunction(int i);
	}
	
	// Use Dutch National Flag algorithm with 2 colors.
	//
	// O(N) time, O(1) space	
	static void partition(int a[], SomeInterface s) {
		int i = 0, j = a.length - 1;
		while (i < j) {
			int result = s.someFunction(a[i]);
			if (result == 0) {
				i++;
			}
			else {
				swap(a, i, j--);
			}	
		}
	}
	
	static void swap(int a[], int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
}

int run()
{

int A[] = {4, 2, 5, 8, 1, 7, 9, 4, 6};

int N = sizeof(A) / sizeof(A[0]) - 1;

print_v(A, sizeof(A) / sizeof(A[0]));

for(int i = 0; i <= N; i ++) {

if(f(A[i])) continue;

else {int t = A[i]; A[i] = A[N]; A[N] = t; N --; i --;}

}

print_v(A, sizeof(A) / sizeof(A[0]));

return 0;
}

int run()
{
int A[] = {4, 2, 5, 8, 1, 7, 9, 4, 6};
int N = sizeof(A) / sizeof(A[0]) - 1;
print_v(A, sizeof(A) / sizeof(A[0]));
for(int i = 0; i <= N; i ++) {
if(f(A[i])) continue;
else {int t = A[i]; A[i] = A[N]; A[N] = t; N --; i --;}
}
print_v(A, sizeof(A) / sizeof(A[0]));
return 0;
}

use Linked List. if returns 1 add to head else add to tail?

We can update the values in the same input array only. Let assume a condition of number is even/odd and the function returns 1 if that is odd else 0. Now start traversing array from the 0th index and check util it reached to endIndex. Keep all the even on the left side and odd values to the right side. If the number is even , just increment startIndex and proceed else swap the values and decrement endIndex and proceed.

// odd or even
bool isOdd(int n)
{
    return (n % 2 == 0 ? 0: 1);
}

// Arrange element of the array
void arrangeArray(int * A, int size )
{
    // Start from left
    int startIndex = 0; // start index
    int endIndex = size -1; // end index
    
    int temp = 0;
    while ( startIndex <= endIndex)
    {
        if ( isOdd(A[startIndex]))
        {   // Store odd number at the end , decrement end index
            temp = A[endIndex];
            A[endIndex] = A[startIndex];
            A[startIndex] = temp;
            endIndex--;
        }
        else{
            startIndex++;
        }
    }
}

int func(int num)
{
return num&1;
}

void storeNum(int *arr, int nLength)
{
if (NULL == arr)
return;

int i = 0,j = nLength-1;
while (i <= j)
{
if (!func(arr[i]))
{
while (i <= j)
{
if (leftNum(arr[j]))
break;
j--;
}
if (j < i)
break;
swap(arr+i,arr+j);
}
i++;
}
}

#include<stdio.h>
int main()
{
int arr[10]={7,6,4,3,2,9,0,1,5,8};
int i=0,j=9;
while(i<j)
{

if(!func(arr[i]) || func(arr[j]))
{

if(!func(arr[i]) && func(arr[j]))
{
swapper(arr,i,j);
i++;
j--;
}
else if (!func(arr[i]))
{
j--;
}
else
{
i++;
}
}
else
{
i++;j--;
}
}
int k;
for(k=0;k<10;k++)
printf("%d ",arr[k]);
}

int func(int a)
{
return a%2;
}

void swapper(int arr[],int i,int j)
{
int temp;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}

One can use two index i and j and move them in opp direction till
I and j cross each other. Similar to quick sort

public class Solution
{
public static void main(String arg[])
{
int array[]={45,43,12,78,12,15,14};
int i=0;
int j=array.length-1;
while(i<j)
{
while(func(array[i])==1)
i++;
while(func(array[j])==0)
j--;
if(i<j)
{
int temp=array[j];
array[j]=array[i];
array[i]=temp;
}
}
for(int num : array)
{
System.out.print(num + " ");
}
}
public static int func(int array)
{
System.out.println(array%2);
return (array%2);
}
}

Use Insertion sort properties i.e if function return 1 insert it into the place after number whose return is 1 otherwise leave at its own place.

take two pointers say i and j. at starting i is pointing to a[0] , and traverse the array with the pointer j. if fun(a[j])==1 ,then then replace a[j] with a[i] and increment both pointer i.e. i++ and j++. time complexity O(n).

If we see the values of what each functions return we will be able to see that it is only 0 and 1.
Assuming we are allowed this we can apply a quick sort on these values such that each swapping is reflected on the actual array as well.