## Google Interview Question for Software Engineer / Developers

• -8

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 3 vote

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.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

it seems kind of impossible, especially in 40mins :(

Comment hidden because of low score. Click to expand.
0

``````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)
{
}
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)
{
}
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]+ " ");

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

YEAH. BAN THE F(_)<KER.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

I wrote a code like that. The problem is it doesnt work for a sequence like:
0 2 8 4 7 9 1 5 5 8
It first moves 0 to the place of 7 and then move it again to the replace the second 5. So it doesn't preserve order.

Comment hidden because of low score. Click to expand.
0
of 0 vote

could someone give an example input and output array?

Comment hidden because of low score. Click to expand.
0

Input: [2 1 5 3]
Output: [1 5 3 2]

Input: [1 2 3]
Output: [1 3 2]

Input: [8 2 5 6]
Output: [5 8 2 6]

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

For stable partition we may use:

``````for (i = 0; i < N; i++)
b[i] = a[i] % 2 ? i : N + i;

sort b with the linear radix sort algorithm;

for (i = 0; i < N; i++) {
k = b[i] % N;
print a[k];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Doesn't preserve the order of elements, try with [0,1,2,5].

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

I forgot: after the swap, there should be
i++;
j++;

Comment hidden because of low score. Click to expand.
0
of 2 vote

Can someone please provide some examples of inputs and outputs?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()
{
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

Comment hidden because of low score. Click to expand.
0

Reverse is an O(n) operation. Reverse within a while loop makes the algo O(n^2)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

O(nlog n) is same as sorting, isn't it?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args) {
ArrayList<Integer> input = new ArrayList<Integer>();

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

You seem to have ignored "relative order does not change".

Otherwise the problem is trivial, the partition step of quicksort, as you noted.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
{
}
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)
{
}
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]+ " ");

}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

Nice,but this solution doesnt preserve relative order of elements.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.