## Google Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

I agree. This problem is not coding problem. Probably interviewer wants to know how would you approach it and try to find several solutions and talk about efficiency.

```
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)
{
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;
}
nextEvenNumber(a, indexLow,indexHigh,reverseEven,reverseOdd);
Enumeration en = evenfoundIndexArr.elements();
while(en.hasMoreElements())
{
int valIndex = (Integer) en.nextElement();
temp = a[evenPointer];
a[evenPointer] = a[valIndex];
a[valIndex] = temp;
}
nextOddNumber(a, indexLow,indexHigh,reverseEven,reverseOdd);
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]+ " ");
}
```

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

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.

How doesn't Radix sort move all odd numbers before even numbers and without changing the relative orders?

Well, I think Alessandro meant bucket sort in which uses a hashtable that keeps two lists, one list for odd number and one list for even number. Then walk through the input list and add each number to their corresponding list. Lastly, merge this two list. Or better yet, just do

given a[1..n]

for i in 1..n

if a[i] is odd

odds.append(a[i])

else

evens.append(a[i])

result = odds + evens

The problem becomes very trivial if space can be o(n)

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

The devil is in the details. When you "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)", you inevitably have to replace an existing element each time. That means you should first assign the existing element to the proper place before replacing it, and it's not always obvious where you should put this element you are about to replace.

Or maybe show this is indeed possible with some code.

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

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

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

Like this idea... very cool how it leverages the old trick of swapping the words order in a sentence.

It does end up in O(n^2) as the worst case. I would take this one step further in order to claim for O(nlogn):

1. at each phase, divide the array to blocks of {odd1/even1/odd2/even2}. suppose we have k blocks like this. Note: the first block may be in {even1/odd1/even2} form, which does not matter because we don't move the leading odds anyway.

2. transform each block as suggested above to {odd1/odd2/even1/even2}.

3. now the total number of blocks has gone down to k/2 .

so we only need log(k) phases, which is the number of times a cell is swapped, hence this becomes a standard sorting nlogn complexity.

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

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

}

Its almost impossible to solve this in O(n) and O(1) time.

- Psycho February 01, 2014There 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.