CareerCup

Its almost impossible to solve this in O(n) and O(1) time.
There is a paper which describes citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.5554&rep=rep1&type=pdf : In the stable 0-1 sorting problem the task is to sort an array of n elements with two distinct values such that equal elements retain their relative input order.

But in order to do that we have to destroy the initial input array. But its just not done for just interviews of 1 hour.

I have two solutions: one is of O(n) time complexity and O(n) space complexity, the other is of O(n^2) complexity and O(1) space complexity. I'm wondering if there is a better solution?

If the problem means {1, 2, 3, 4, 5} --> {1, 3, 5, 2, 4},
my code is as follows:
(By the way, you were asked this many questions in one day interview??)

import java.util.Arrays;

public class JE5 {
	public static void main(String[] args) {
		int[] input1 = {2, 4, 1, 3, 6, 5};
		int[] input2 = {2, 1, 3, 5, 7, 9};
		int[] input3 = {0};
		int[] input4 = {1, 2, 3, 3, 6, 6};
		
		sortByEvenOdd(input1);
		sortByEvenOdd(input2);
		sortByEvenOdd(input3);
		sortByEvenOdd(input4);
		
		System.out.println(Arrays.toString(input1));
		System.out.println(Arrays.toString(input2));
		System.out.println(Arrays.toString(input3));
		System.out.println(Arrays.toString(input4));
	}
	
	public static void sortByEvenOdd(int[] input) {
		int ptr = 0;
		int even = 0;
		while(ptr < input.length) {
			if(input[ptr]%2 == 0)
				even++;
			else
				swapDownward(input, ptr, even);
			ptr++;
		}
	}
	public static void swapDownward(int[] input, int ptr, int num) {
		for(int i=0; i<num; i++)
			swap(input, ptr-i, ptr-i-1);
	}
	public static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

I don't think your solution is O(n).
If you have an array 1 2 3 4 5 6 .... with a lot of numbers,
then you have a main loop (

while(ptr < input.length)

) and second loop:

for(int i=0; i<num; i++)

together O(n) each, so it should be O(n^2) total

void swap(int &a, int &b)
{
int tmp=a; a=b; b=tmp;
}

void odd_even_sort(int* num, int n)
{
int k=0;
for(int i=0; i<n; i++) {
if( num[i]%2==1 ) {
swap(num[i],num[k]);
k++;
}
}
}

forgot to surround the code:

void swap(int &a, int &b)
{
	int tmp=a; a=b; b=tmp;
}

void odd_even_sort(int* num, int n)
{
	int k=0;
	for(int i=0; i<n; i++) {
		if( num[i]%2==1 ) {
			swap(num[i],num[k]);
			k++;
		}
	}
}

I think it is wrong, too.
Test {1,2,3,4,5}, i=0, k=0 -> {1,2,3,4,5}, i=1,k=1 -> {1,3,2,4,5}, i = 2, k = 2 ->
{1,3,2,4,5}, i = 3, k = 2 -> {1,3,5,4,2} i = 4, k = 3. And that fails, because the correct answer should be {1,3,5,2,4} to save the relative order.

Thanks Alex, the following will preserve the relative order -- although the space complexity is O(1), it's time complexity is O(n^2). Wonder if one can solve this in time O(n) and space O(1)

void swap(int &a, int &b)
{
	int tmp=a; 	a=b; b=tmp;
}

void odd_even_sort(int* num, int n)
{
	int swap_cnt = 0;
	int k=0;
	for(int i=0; i<n; i++) {
		if( num[i]%2==1 ) {
			swap(num[i],num[k]);
			for(int j=i; j>k+1; j--)
				swap(num[j],num[j-1]);			
			k++;
		}
	}
}

This question seems really fishy. To solve this you need to have read the paper "STABLE MINIMUM SPACE PARTITIONING IN LINEAR TIME" before the interview. If the space wasn't a problem you could simple use a Radix Sort and have the result in O(N) time and O(N) space.

Solving this in O(n) time and O(1) space seems impossible and I could only come up with a 'workaround' that involves using a recurrent algorithm so I could rely on the stack to hold the odd values. When the recursion returns, I just simply fill the array with the odd values from the stack.

void OddBeforeEven(int* array, int currPos, int oddValueCaried, int& lastOddPos, int& fillCounter)
{
	if (currPos < 0)
	{
    	return;
	}

	while (currPos >= 0 && array[currPos] % 2 == 0)
	{
    	// Move even elements to the right and mark the last position of the even element
       	array[lastOddPos--] = array[currPos--];
	}

	if (currPos == 0)
	{
    	// Handled case where the first element is odd
    	fillCounter++;
	}
	else
	{
    	OddBeforeEven(array, currPos - 1, array[currPos], lastOddPos, fillCounter);
	}

	// Start filling the array with the odd values returned from the recursion
	if (fillCounter <= lastOddPos)
	{
    	array[fillCounter++] = oddValueCaried;
	}
}

I suppose we can solve it in this way:
(1)Go through the array and find how many odd numbers there are, say it's oddNum.
(2)If oddNum == 0 || oddNum == arr.length then sort is done.
(3)Else now we know that all odd numbers will be arr[0] to arr[oddNum-1] and all even numbers will be arr[oddNum] to arr[arr.length-1]. Thus we can go through the array again and at the same time put all the odd numbers into [0, oddNum) and all the even numbers into [oddNum, arr.length).

FYI: OP is just copy pasting interview questions found on glassdoor, OR Google just really likes interviewing him :P

"""
sort the array so that the odd number in front of the even number and their relative order doesn't change in Time O(n) and Space O(1). I believe quickselect can do this, but it would change the relative input order.
"""
input = [1, 2, 3, 4, 5, 6, 7, 8]
i = 0
j = i + 1
length = len(input)

while(j < length):
  if(input[i] % 2 == 0 and input[j] % 2 == 1):
    temp = input[i]
    input[i] = input[j]
    input[j] = temp

  while(i < length-1 and input[i] % 2 != 0):
    i += 1
  while(j < length and input[j] % 2 != 1):
    j += 1

print input

could someone give an example input and output array?

How about this?

for (i = 0; a[i] %2  && i < N; i++);  // a[0] ...a[i-1] are odd, and a[i] is even
for (j=i+1; j < N; j++) 
    if (a[j] % 2) {
        swap(a[i], a[j]);
        i++;
    }

int i = 0;
		for(int j = 0; j<10; j++){
			if (a[i]%2 ==1){
				i++;
			} else if(a[j]%2==1){
				swap(i,j);
				i++;			
			}
			else continue;
		}

Going from left to right can preserve the relative order.

void sort(int[] A) {
    int m = A.length;
    if (m<=1) return;
    int odd = 0;
    for (int x : A) {
        if (x%2==1) {
            odd++;
        }
    }
    int i = 0, j = odd;
    while (i<odd && j<A.length) {
        if (A[i]%2==1) {
            i++;
            continue;
        }
        if (A[j]%2==0) {
            j++;
            continue;
        }
        int temp = A[j];
        A[j] = A[i];
        A[i] = temp;
    }    
}

Can someone please provide some examples of inputs and outputs?

This problem can indeed be solved in O(n) time complexity and O(1) space complexity.

Think of the array as contiguous streaks of even and odd numbers: [o_lead, e1, o1, e2, o2, e3, o3, ...].

Each streak can have any amount of numbers in it.

We can ignore the leading streak of odd numbers o_lead (if any) because they are already in the sorted position.

Now we need to find a solution to sort each [ei, oi] pair of even streak followed by an odd streak.

After sorting the [ei, oi] pair we get [oi, ei] -- essentially swap/switch the locations of the even and odd streaks.

To do this, do the following steps

-- Reverse ei to get rev(ei)
-- Reverse oi to get rev(oi)
-- Reverse [ rev(ei), rev(oi) ] to get [ rev(rev(oi)), rev(rev(ei)) ] which is equal to [oi, ei]
-- Now the array will be [already-sorted-stuff, oi, ei, ei+1, oi+1, ...]. Now merge ei into ei+1.

This is very similar to reversing all the words within a sentence (not the whole sentence).

#include <vector>
#include <iostream>
#include <stdio.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repv(i, v) for(int i = 0; i < v.size(); i++)

void printArray(const vector<int> &A)
{
	repv(i, A) cout << A[i] << " ";
	cout << endl;
}

void reverse(vector<int> &A, int start, int end)
{
	while(start < end) swap(A[start++], A[end--]);
}

void sortEvenOdd(vector<int> &A)
{
	// find and sort each segment of even-streak followed by odd-streak
	// time complexity -- O( A.size() ) , space complexity -- O(1)
	int evstart, evend;
	int ostart, oend;
	int i = 0;
	
	while(i < A.size())
	{
		// ignore leading streak of odds
		if( i == 0 )
		{	
			while(i < A.size() && A[i] % 2 > 0) i++;		
			if(i == A.size()) break;
			//printf( "leading odd-streak: (%d,%d)\n", 0, i-1);

			evstart = i;
			evend = evstart;
		}	

		// find start and end of even-streak -- O( length(even-streak) )
		while(evend < A.size() && A[evend] % 2 == 0) evend++;
		if(evend-- == A.size()) break;

		//printf( "even-streak: (%d,%d)\n", evstart, evend);

		// find start and end of odd-streak -- O( length(odd-streak) )
		ostart = evend+1;

		oend = ostart;
		while(oend < A.size() && A[oend] % 2 > 0) oend++;
		oend--;

		//printf( "odd-streak: (%d,%d)\n", ostart, oend);

		// now swap positions even-streak with odd-streak
		// Note: this is just like reversing words in a sentence
		reverse(A, evstart, evend); // O( length(even-streak) )
		reverse(A, ostart, oend); // O( length(odd-streak) )
		reverse(A, evstart, oend); // O( length(even-streak) + O( length(odd-streak) )
		// update the position of the even-streak which we just moved
		evstart = oend - (evend - evstart);
		evend = oend;

		// A[0] to A[oend] has been sorted now move on to the rest of the array
		i = oend + 1;
	}	
}

int main()
{
	// read data
	int N;
	cin >> N;

	vector<int> A(N);
	rep(i, N) cin >> A[i];
	cout << "Before sorting: " << endl;
	printArray(A);

	// sort the array
	sortEvenOdd(A);
	cout << "After sorting: " << endl;
	printArray(A);

	return 0;
}

Please correct me if anything is wrong

public static void main(String[] args) {
		ArrayList<Integer> input = new ArrayList<Integer>();
		input.add(2);
		input.add(1);
		input.add(3);
		input.add(2);
		input.add(4);
		input.add(6);
		input.add(8);
		input.add(4);
		input.add(2);
		input.add(1);
		input.add(5);
		input.add(4);
		input.add(5);
		input.add(4);
		
		
		System.out.println(input);
		
		int i = 0, j=0;
		int k = 0;
		int temp;
		int arrayLength = input.size();
		
		System.out.println("Array length : " + arrayLength);
		boolean check = false;
		while(i < input.size()){
		
			Integer t = input.get(i);
			if(t%2 == 0 && !check){
				if(arrayLength ==  input.size()){
					temp = t;
					j = i;
					input.add(t);
					check = true;
				}
				
			} else if (t%2 == 1){
				System.out.println("Odd ball");
				if(check){
					input.set(j, t);
					input.set(i, input.get(input.size() - 1));
					input.remove(input.size() - 1);
					evenSwap(input, j+1 ,i);
					i = j;
					j = 0;
					
					check = false;
						
				}
			}
			
			i++;
		}
		if(arrayLength + 1 ==  input.size()){
			if(check){
				input.remove(arrayLength);
			}
		}
		System.out.println("Over all output :" + input);

	}
	
	public static void evenSwap(ArrayList<Integer> array, int i, int j){
		
		boolean cont = true;
		System.out.println("Input :" + array);
		while(cont){
			if(i == j){
				cont = false;
			} else {
				Integer temp = array.get(i);
				array.set(i, array.get(j));
				array.set(j, temp);
			}
			i++;
			
			
		}
		System.out.println("Output : " + array);
	}

Hello there, the code below seems to work ( passes the test cases that i could conjure) but neverthless it is not O(n) vis-a-vis runtime.

#include <iostream>
using namespace std;


void debug_arr(int *arr,int len, const char* msg)
{
	cout << msg << " : "; 
	for (int i = 0; i < len; ++i)
	{ 
		cout<<arr[i]<<" ";
	}
	cout<<"\n";

}
void insert(int atIndex,int withIndex,int*arr, int arr_len)
{


	debug_arr(arr, arr_len, "==before insert");

	cout << "==Goal : replace arr[" << atIndex << "]= "<<arr[atIndex]<<" with arr[" <<withIndex << "] = " << arr[withIndex]<< "\n";

	int temp=arr[withIndex];

	for(int i=withIndex;i > atIndex ;i--)
	{
		//cout<< "------replacing " << "arr[" << i <<"] = " << arr[i]<< " with arr[" << i -1 << "] = " << arr[i-1] << "\n";
		arr[i]=arr[i-1];

	}
	arr[atIndex]=temp;

	debug_arr(arr, arr_len , "==after insert");

}


void partition(int *arr,int len)
{
	int lastEvenIndex=0;
	int firstEvenIndex = 0;
	int i=0;
	bool isOddStreak=true;
	while(i<len)
	{
		if(arr[i]%2==0)
		{
			//even
			if(isOddStreak)
			{
				firstEvenIndex=i;
			}
			lastEvenIndex = i;

			cout << " firstEvenIndex " << firstEvenIndex <<" , lastEvenIndex " << lastEvenIndex  << "\n";
			isOddStreak=false;
		}
		else
		{
			//odd
			if(isOddStreak == false)
			{		
				isOddStreak	=true;
				insert(firstEvenIndex,i ,arr, len);
				i = firstEvenIndex;
				continue;
			}

		}
		i++;
	}
}

int main() 
{
	int arr[]={ 1 ,2,3,4,5,6,7,8,9,7,6 };
	debug_arr(arr,sizeof(arr)/sizeof(int),"===before partition");
	partition(arr,sizeof(arr)/sizeof(int));
	debug_arr(arr,sizeof(arr)/sizeof(int) ,"===after partition");
	return 0;
}

It is possible. The solution is following: we scan the array from end to the beginning holding 2 pointers. 1st is on current odd number and 2nd is on current even number(when we start they are on first odd and even numbers). Further we swap numbers under pointers and move pointers till they meet corresponding numbers toward beginning of array.

basically we can introduce some count
count1 = 0. keep track of # even visited
count2 = 0. keep track of first even will need to start to swap
if(array[0] %2 ==0){
swap (array[0],array[1]);
}
for (int i =1 ; i< array.size; i++){
if(array[i]%2 = =0 && array[i-1]%2 == 1){
//case even pre odd
if(count1 == 0){
count2 = i;
}
count1 ++;
} else if(array[i]%2 = =1 && array[i-1]%2 == 2){
//swap the odd with the first occurred even
swap(array[i],array[count2 + count1]);
count1 --;
}

}

#include <iostream>
#include <algorithm>
using namespace std;

void putOddInFrontOfEven(int a[], int n)
{
    int i = 0;
    //skip continuous odd numbers at front
    for(; i < n && (a[i] & 1); ++i) ;

    while(i < n){
        //now a[i] is an even number
        int evenStart = i;
        for(; i < n && (a[i] & 1) == 0; ++i) ;
        if(i == n) break;

        //now a[i] is an odd number
        int oddStart = i;
        for(; i < n && (a[i] & 1); ++i) ;

        //put those odd numbers in front of those even numbers
        reverse(a + evenStart, a + oddStart);
        reverse(a + oddStart,  a + i);
        reverse(a + evenStart, a + i);
    }
}

int main()
{
    int a[] = {2, 1, 5, 3}, n = sizeof(a)/sizeof(a[0]), i;

    cout << "Initially:\n";
    for(i = 0; i < n; ++i) cout << a[i] << " ";

    putOddInFrontOfEven(a, n);

    cout << "\nAfter putting odd numbers in front:\n";
    for(i = 0; i < n; ++i) cout << a[i] << " ";

    return 0;
}

There's a limit to stupidity. I don't understand what are these companies trying to prove by asking questions that have no solutions. If these companies really want people who can answer prize-winning questions like this, they should hold a coding competition and select the winners to work for them. There's no point in conducting 45 min interviews. So, which ever company asks such questions should simply eliminate the concept of interviewing and just seek winners from a coding competition, if such winners do exist.

void Resort(int* a,int n)
{//find the leftmost even
 int left=0;
 while(a[left]%2==1 && left <n)
    {left++;}
 if(left==n){return;}//all odd
 //find the rightmost odd
 int right=n-1;
 while(a[right]%2==0 && right >=0)
    {right--;}
 if(right<0){return;}//all even
 while(left<right)
    {
     swap(a[left],a[right]);
     while(a[left]%2==1 && left <n)
         {left++;}
     if(left==n){return;}
     while(a[right]%2==0 && right >=0)
         {right--;}
     if(right<0){return;}
    }
}

Test the code below, it is O(n), memory usage O(1). Cheers!!!

#include <iostream>
using namespace std;


void sortoddeven(int * a, int n)
{
int oddcount = 0;
for(int i = 0; i<n; i++)
	oddcount += a[i]%2;
int i_e = oddcount;
int i_o = 0;
int i = 0;
while(i_o<oddcount)
{
if(a[i]%2)
swap(a[i++],a[i_o++]);
else
swap(a[i++],a[i_e++]); 	
if (i==oddcount)
	i = i_o;
}
}

int main() {
	// your code goes here
	int n = 20;
	int *a = new int[n];
	for(int i = 0; i<n; i++)
		a[i] = i;
	sortoddeven(a,n);
	
	for(int i = 0; i<n; i++)
		cout<<a[i]<<" ";
	return 0;
}

Sorry, still seems to have some problem.

Split and merge the arrays and while merging arrange odd numbers at the beginning and even numbers at the end. Take care to perform insert instead of swapping even number to odd number at back of array. Below code does the job. Try it out yourself.

package com.sunpria;

public class SegregateOddEven {

	public static void main(String[] args) {
		int [] a = {4,5,8,9,2,3,47,52,34,38};
		segregateOddEven(a,0,a.length-1);
		for(int i=0;i<a.length;i++)
			System.out.println("a["+i+"] = "+a[i]);
	}
	
	public static void merge(int []a, int l, int m, int h) {
		int i=l,j=m+1;
		while(i<=h && j<=h) {
			if(((a[i] & 0x1) == 0x0)) {
				if(((a[j] & 0x1) == 0x0)) {
					break;
				}
				int tmp=a[j];
				for(int k=j;k>i;k--){					
					a[k] = a[k-1];					
				}
				a[i] = tmp;
				j++;
			}
			i++;
		}
	}
	
	public static void segregateOddEven(int []a, int l, int h)
	{
		int m = (l+h)/2;
		
		if ((l<0) || (h > a.length) || (l>=h))
			return;
		
		segregateOddEven(a, l, m);
		segregateOddEven(a, m+1, h);
		merge(a, l, m, h);		
		
	}

}

Input: 4,5,8,9,2,3,47,52,34,38
Output: 5,9,3,47,4,8,2,52,34,38

// group even number on left and keep the order
public void Group(int[] data)
{
    int l = 0, r = 0;
    while (r < data.Length)
    {
        if (data[l] % 2 == 0)   // even number, shift to right
        {
            l++;
        }
        else
        {
            r = r == 0 ? l + 1 : r;  // r = 0, r is not used.
            while (r < data.Length && data[r] % 2 != 0)
                r++;
            if (r < data.Length)
            {
                int p = r;
                while (p > l)
                    swap(ref data[p - 1], ref data[p--]);
                l++;    r++;
            }
        }
    }
}

0  1  2  3  4   5  6
2, 4, 1, 3, 6, 10, 7 [0, 0] // left pointer and right pointer
2, 4, 1, 3, 6, 10, 7 [1, 0]
2, 4, 1, 3, 6, 10, 7 [2, 0] // [2] = 1 is even, find 6
2, 4, 6, 1, 3, 10, 7 [3, 5]
2, 4, 6, 10, 1, 3, 7 [4, 6]
2, 4, 6, 10, 1, 3, 7 [4, 7]

output = 2, 4, 6, 10, 1, 3, 7

well not really O(1) space but recursion can solve this problem without actually we allocating memory

count number of evens
recursively keep storing the numbers, and when recursion is returning position the numbers.
arrange(Arr)
{
  int o= -1 // next odd position
  int e=Arr.length - CountEvens(Arr) -1 // next even position
  int i=0 // current counter position
  Arrange(Arr, &o, &e, &i)
}

Arrange(Arr, &o, &e, &i)
{
  if(i>=Arr.length) return;
  N = Arr[i]; // save the number
  if(A[i]%2==0) e++ //even increment
  else o++ // odd increment
  i++;
  Arrange(Arr,&o,&e,&i)
  if(N%2==0) {A[e]=N; e--;}
  else {A[o] = N; o--;}
}

someone explain what it means to sort something, and without changing the relative order, is it a joke?

O(n) and one traversal and order maintained

import java.util.Collections;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.Vector;


public class EvenandOdd {

	/**
	 * @param args
	 */
	
	public static Vector evenfoundIndexArr = new Vector();
	public static Vector oddfoundIndexArr = new Vector();

	
	public static void nextEvenNumber(int a[],int indexLow,int indexHigh,boolean reverseEven,boolean reverseOdd){
		evenfoundIndexArr.clear();
		while(indexLow < indexHigh)
		{
			if(a[indexLow]%2==0)
			{
				evenfoundIndexArr.add(indexLow);
			}
			indexLow++;
		}
		if(reverseEven)
		{
			Collections.reverse(evenfoundIndexArr);
		}
		
 
	}
	
	public static void nextOddNumber(int a[],int indexLow,int indexHigh,boolean reverseEven,boolean reverseOdd){
		oddfoundIndexArr.clear();
		while(indexLow < indexHigh)
		{
			if(a[indexLow]%2==1)
			{
				oddfoundIndexArr.add(indexLow);
			}
			indexLow++;
		}
		if(reverseOdd)
		{
			Collections.reverse(oddfoundIndexArr);
		}
 
	}

	
	public static int[] putOddatoddEvenateven(int a[])
	{
		int evenPointer=1;
		int oddPointer=0;
		int indexLow = 0;
		int indexHigh = 0;
		
		boolean reverseEven = false,reverseOdd = false;
	
		while(true)
		{
			
			while(oddPointer <= a.length-2)
			{
				if(a[oddPointer]%2==1)
				oddPointer=oddPointer+2;
				else
					break;
			}
			
			while(evenPointer <= a.length-1)
			{		
				if(a[evenPointer]%2==0 )
				evenPointer=evenPointer+2;
				else
					break;	
			}
			
			if(oddPointer <= a.length-2 && evenPointer <= a.length-1)
			{
				
				// swapping for putting even at even pos and odd at odd pos but order has changed at this point
				int temp = a[oddPointer];
				a[oddPointer] = a[evenPointer];
				a[evenPointer] = temp;
				
					if(evenPointer < oddPointer)
					{
						indexLow = evenPointer+1;
						indexHigh = oddPointer;
						reverseEven = true;
						reverseOdd = false;
					}
					else
					{
						indexLow = oddPointer+1;
						indexHigh = evenPointer;
						reverseEven = false;
						reverseOdd = true;
					}
					
					// getting the even elements order that are present between swapped elements
					 nextEvenNumber(a, indexLow,indexHigh,reverseEven,reverseOdd);
					// maintaing even number order
					 Enumeration en = evenfoundIndexArr.elements();
						while(en.hasMoreElements())
						{	
							int valIndex = (Integer) en.nextElement();
							temp = a[evenPointer];
							a[evenPointer] = a[valIndex];
							a[valIndex] = temp;
						}
			
					// getting the odd elements order that are present between swapped elements
					nextOddNumber(a, indexLow,indexHigh,reverseEven,reverseOdd);
					// maintaing odd number order
					Enumeration en1 = oddfoundIndexArr.elements();
						while(en1.hasMoreElements())
						{
							int valIndex = (Integer) en1.nextElement();
							temp = a[oddPointer];
							a[oddPointer] = a[valIndex];
							a[valIndex] = temp;
						}
			}
			else
				break;
		}
		return a;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		
		//int a[]={5,1,2,7,9,11,10,6,8,12};
		//int a[]={2,4,6,8,1,3,5,7};
		//int a[]={1,3,5,7,2,4,6,8};
		
		int a[]={1,5,7,6,3,8,4,2};
		
		
		System.out.println("input array");
		for(int i=0;i<a.length;i++)
			System.out.print(a[i] + " ");
		
		a=putOddatoddEvenateven(a);
		
		System.out.println("\n output array");
		for(int i=0;i<a.length;i++)
		System.out.print(a[i]+ " ");	

	}

}

Go through the array and maintain the last even index. Whenever you encounter and odd number, swap the number with the number at last even index

private void frontlineOdd(int []array) {
    int lastEvenIndex = -1;
    for (int i = 0; i < array.length; i++) {
        if (array[i]%2 == 1) {
            if (lastEvenIndex != -1) {
                swap(a[i], a[lastEvenIndex]);
            }
        } else if (lastEvenIndex == -1) {
           lastEvenIndex = i;
        }
    }
}

Go through the array and maintain the last even index. Whenever you encounter and odd number, swap the number with the number at last even index

private void frontlineOdd(int []array) {
    int lastEvenIndex = -1;
    for (int i = 0; i < array.length; i++) {
        if (array[i]%2 == 1) {
            if (lastEvenIndex != -1) {
                swap(a[i], a[lastEvenIndex]);
                lastEvenIndex++
            }
        } else if (lastEvenIndex == -1) {
           lastEvenIndex = i;
        }
    }
}

}