Adobe Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
That will fall in the case 3, where exactly one pointer points to wrong number(pointer 2 which points to odd number)
Not able to get the (3) point can u explain further? How does it brings the wrong pointer value to right place?
According to the above algo....
The answer to the above array would be----
1,4,5,2,3,6,7,8
Are we maintaining the order ?
The original question is questionable. What about an array containing more odd/even numbers than even/odd ones? The extreme case is all numbers are even or odd.
Do not waste your time until the guy posting it comes forward to clarify it.
If the order of numbers doesn't change that what is the alternative, do we leave the positions blank which is again equivalent to having initialization values there. For example: 1,2,4,7
a[0] = 1
a[1]= ??
a[2]= 2
a[3] = ??
class ArrayRearrange {
void checkArray(int[] array) {
int oddCount = 0;
int evenCount = 0;
for (int entry : array) {
if (entry % 2 == 0) {
++evenCount;
} else {
++oddCount;
}
}
if (oddCount != evenCount) {
throw new IllegalArgumentException("there should be same number of odd an even entries");
}
}
public void swapOddEven(int[] array) {
checkArray(array);
int lastEvenImbalance = -1;
int lastOddImbalance = -1;
for (int i = 0; i < array.length; ++i) {
if (array[i] % 2 == 0) {
if (i % 2 != 0) lastEvenImbalance = i;
} else {
if (i % 2 == 0) lastOddImbalance = i;
}
if (lastEvenImbalance != -1 && lastOddImbalance != -1) {
int temp = array[lastEvenImbalance];
array[lastEvenImbalance] = array[lastOddImbalance];
array[lastOddImbalance] = temp;
lastEvenImbalance = -1;
lastEvenImbalance = -1;
}
}
}
public static void main(String[] args) {
int[] array = {1,2,3,4};
ArrayRearrange arrayRearrange = new ArrayRearrange();
arrayRearrange.swapOddEven(array);
for (int entry : array) {
System.out.println(entry);
}
}
}
static void Main(string[] args)
{
int[] arr = {1,1,3,4,1,6,5,8};
for (int i = 0, j = 1; j < arr.Length; i++, j++)
{
if (i % 2 == 0 && arr[i] % 2 != 0)
{
while (arr[j] % 2 != 0)
{
j++;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
if (j != arr.Length - 1)
{
j = i + 1;
}
}
else if(i%2 !=0 && arr[i]%2 == 0)
{
while (arr[j] % 2 == 0)
{
j++;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
if (j != arr.Length - 1)
{
j = i + 1;
}
}
}
}
Order of numbers are not restored but still need to understand the Q
Assumptions:
Assume the problem is referring to a 1-indexed array (implementation could be 0 indexed, but the "first" spot is odd)
There are the floor[Length/2] even numbers and ceiling[length/2] odd numbers (so every number has a place).
By "order of numbers should not change", I'll take that to mean that if Ai and Ak are both odd or both even and i < k in the original, then Ai will be before Ak in the final output. I.e the order of odds and evens are maintained separately.
Algo:
Two pointers. OddPtr starts at 1, EvenPtr at 2
"Good" check for OddPtr => Arr[OddPtr] % 2 = 1
"Good" check for EvenPtr => Arr[EvenPtr] % 2 = 0
If they're both wrong, switch and go to finishing step.
If OddPtr is wrong, move to EvenPtr + 1 and check if good. If so, walk the value and pointer back to original position of OddPtr (swap all elements down along the way, instead of direct swap). If EvenPtr + 1 not odd, OddPtr++ and try again.
If EvenPtr is wrong, EvenPtr++ and check. Do the same thing as OddPtr.
Finishing: Add two to OddPtr and EvenPtr, until EvenPtr > Arr.Length().
Walkthrough:
() = OddPtr
[] = EvenPtr
Initial array: 2,4,1,3,5,7,6,8
Step 1: (2),[4],1,3,5,7,6,8 => OddPtr is wrong. Go to EvenPtr+1=> 2,[4],(1),3,5,7,6,8. Valid, walk 1 and OddPtr back (EvenPtr stays at pos2), giving (1),[2],4,3,5,7,6,8. Move pointers
Step 2: 1,2,(4),[3],5,7,6,8 => Both wrong, swap & finish.
Step 3: 1,2,3,4,(5),[7],6,8 => EvenPtr wrong. Move up one. 6 is even, so walk it back & finish.
Step 4: 1,2,3,4,5,6,(7),[8] => Good. Finish, which hits terminal condition, done.
Code:
inline bool CheckOdd(int n) { return (n % 2 == 1); }
inline bool CheckEven(int n){ return (n % 2 == 0); }
inline void Swap(int *arr, int ptr1, int ptr2) { int temp = arr[ptr1]; arr[ptr1] = arr[ptr2]; arr[ptr2] = temp }
public int* ShuffleOddsAndEvens (int* arr, int arrLength)
{
int OddPtr = 0;
int EvenPtr = 1;
while(EvenPtr < arrLength)
{
if( !CheckOdd(arr[OddPtr]) && !CheckEven(arr[EvenPtr])) { swap(arr, OddPtr, EvenPtr); }
else if( !CheckOdd(arr[OddPtr])
{
int originalOddPtr = OddPtr;
OddPtr = EvenPtr + 1;
while(OddPtr < arrLength && !CheckOdd(arr[OddPtr]))
{
OddPtr++;
}
while(OddPtr > originalOddPtr)
{
swap(arr, OddPtr, OddPtr-1);
OddPtr--;
}
}
else if (!CheckEven(arr[EvenPtr]))
{
//Same as above, just Even
}
OddPtr += 2;
EvenPtr += 2
}
return arr;
}
Not sure if the code is 100%, but the algo should work
/*
Working Code in C
*/
#include <stdio.h>
enum marker {is_inactive = 0, is_odd = 1, is_even = 2, is_both = 3};
void swapandshift(int first, int last);
void printArray();
int number[] = {3, 4};
int size = (int)sizeof(number)/(int)sizeof(int);
int main() {
int even = 0;
int odd = 1;
enum marker swapmarker = is_inactive;
while(even < size && odd < size){
if(number[even]%2 == 0 && number[odd]%2 != 0 && swapmarker == is_inactive) {
even = even +2;
odd = odd + 2;
}
else if(number[even]%2 != 0 && number[odd]%2 != 0){
swapmarker = is_even;
}
else if(number[even]%2 == 0 && number[odd]%2 != 1){
swapmarker = is_odd;
}
else if(number[even]%2 != 0 && number[odd]%2 != 1){
swapmarker = is_both;
}
switch(swapmarker) {
case 1 : if(number[even]%2 == 1){swapandshift(odd, even);odd = odd+2;}even++;break;
case 2 : if(number[odd]%2 == 0){swapandshift(odd, even);even = even+2;}odd++;break;
case 3 : swapandshift(even, odd);even = even+2;odd = odd+2;
default : break;
}
}
printArray();
return 0;
}
void swapandshift(int first, int last) {
int temp = number[first];
number[first] = number[last];
while(last > first+1) {
number[last] = number[last-1];
last--;
}
number[last] = temp;
}
void printArray() {
int index = 0;
printf("{");
while(index < size-1) {
printf("%d, ", number[index]);
index++;
}
printf("%d}", number[index]);
}
the idea is to :
increment both even and odd pointer by two if both satisfies the condition of even value a even index and odd value at odd index.
suppose while incrementing
consider a scenario
value at odd index comes even, then we fix the odd pointer at that index and keep incrementing even index by one till it encounters any odd value.
then we change the value pointed by odd pointer to the value pointed by even pointer and then we shift the array between odd and even pointer.
even pointer remains at the same position and advances from thereafter .
and odd pointer increments by 2
and do the above steps .
//Logic
//
//For entire array.
//1. check if at current position correct number is placed
// if yes then continue
// if NOT then follow 2 to 5
//2. find the position of the correct number let this position be jposition
//3. store jpositionth number in temp
//4. shift array from current position to jposition
//5. store temp at current position...
//code
#include "iostream"
using namespace std;
void print(int a[],int size)
{
for (int i =0;i<size;i++)
cout << a[i] << "==>";
}
void ArrangeArrayEvenOdd(int a[],int size)
{
for(int i = 0; i<9; ++i)
{
//step 1
if(i%2 == a[i]%2)
continue;
else
{//step2
int j = 1+i;
if(i%2 ==0)
{
while(a[j]%2 != 0)
++j;
}
else
{
while(a[j]%2 !=1)
++j;
}
//step 3
int temp = a[j];
//step 4 shifting array
int k = j;
while(k>i)
{
a[k] = a[k-1];
k--;
}
//step 5 correct element at correct position
a[i] = temp;
}
}
}
int main ()
{
int a[] = {1,5,7,2,3,8,6,0,10};
print(a,9);
cout << endl;
cout << endl;
ArrangeArrayEvenOdd(a,9);
print(a,9);
return 0;
}
shifting an array would increase complexity ..
we can use extra space instead.
1.maintain two queues.
2.replace values in original array one from even queue and one from odd queue.
After seeing so many comments , I felt that I need to give more details. Consider the array below:
a[ ]={2,8,1,9,10,5,7,11,13}
output={1,2,9,8,5,10,7,11,13}. Here the order of odd and even numbers are same. The one which is more in number will be assembled at last. I hope the qns is now clear.
void arrangeOddEven(int a[])
{
int size=a.length;
for(int i=0;i<size;i++)
{
if((i+1)%2==1 && a[i]%2==0)
{
int j=i+1;
while(j<size && a[j]%2==0) j++;
if(j<size)
{
int t=a[j];
while(j>i) {a[j]=a[j-1]; j--;}
a[j]=t;
}
}
else if((i+1)%2==0 && a[i]%2==1)
{
int j=i+1;
while(j<size && a[j]%2==1) j++;
if(j<size)
{
int t=a[j];
while(j>i) {a[j]=a[j-1];j--;}
a[j]=t;
}
}
}
}
package samplejava;
public class Arrayoddevensort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={2,8,1,9,10,5,7,11,13};
int b[]=new int[a.length];
int odd[]=new int[6];
int even[]=new int[3];
for(int i=0,k=0,n=0;i<a.length;i++){
if(a[i]%2==0)
{
even[k]=a[i];
//b[i]=even[k];
k++;
}
else
{
odd[n]=a[i];
//b[i]=odd[n];
n++;
}
}
for(int i=0,k=0,n=0;i<b.length;i++){
if((i)%2==0)
{
//even
if(k<even.length)
{
b[i]=even[k];
k++;
}
else{
b[i]=odd[n];
n++;
}
}
else{
if(n<odd.length){
b[i]=odd[n];
n++;
}
else
{
b[i]=even[k];
k++;
}
//odd
}
}
for(int i=0;i<b.length;i++)
{
System.out.println("SORTED ARRAY:"+b[i]);
}
}
}
I don't understand the point of writing so much code. The question is absolutely JUNK.
The original question is to arrange the nos. in an array such that odd numbers are in odd position and even nos. are in even position.
Let's consider the case where all the nos. of the array are odd e.g. :-
1 3 5 7 9 11 13 15
How the HELL are you going to solve this problem? Same if all the nos. are even. There has to be a constraint if u want to solve this problem generically.
package testpack;
//there should be same number of even and odd numbers
public class Program7 {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4 };
int eve = 0, odd = 0, ce = 0, co = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] % 2 == 0) {
++eve;
} else {
++odd;
}
}
int[] eve_arr = new int[eve];
;
int[] odd_arr = new int[odd];
for (int i = 0; i < a.length; i++) {
if (a[i] % 2 == 0) {
eve_arr[ce] = a[i];
ce++;
} else {
odd_arr[co] = a[i];
co++;
}
}
// System.out.println(eve_arr.length+" "+odd_arr.length);
/*
* int i_ = 0, e1 = 0, o1 = 0;
*
* while(i_ <= a.length){
*
*
* if( i_ % 2 == 0){ System.out.println(e1); a[i_] = eve_arr[e1]; e1++;
*
* } else{ a[i_] = odd_arr[o1]; o1++;
*
* }
*
*
*
* i_++;
*
*
*
* }
*/
int m = 0, n = 1;
for (int i = 0; i < odd_arr.length; i++) {
a[n] = odd_arr[i];
n = n + 2;
}
for (int i = 0; i < eve_arr.length; i++) {
a[m] = eve_arr[i];
m = m + 2;
}
for (int i1 = 0; i1 < a.length; i1++) {
System.out.print(a[i1] + " ");
}
}
}
Yes, this question has to have a constraint. The constraint being the presence of equal no. of even and odd numbers...or else u end up facing ArrayIndexOutOfBoundsException..which took most of my time to rectify :-/
#include <stdio.h>
#include <stdlib.h>
//The idea behind the algorithm :
//If even occurs at even OR odd occurs at odd, go to next
//Else stop at wrong index, scan elements after it based on
// a. If elements after that occuring correctly, then just swap with wrong
// b. Else if element not correct and index same type as wrong one, then skip
// c. Else if index of other type, then swap and move to next element
// The method works fine for the cases in the discussion.
main() {
int *arr;;
int i, j, k, l, n;
//Taking input array
scanf("%d", &n);
arr = (int *)malloc(sizeof(int)*n);
for(i = 0; i < n; i++)
scanf("%d", &arr[i]);
i = -2;
j = -1;
k = 0;
l = 0;
//go till end of loop
while(k < n) {
//if at even position, an odd element occurs or vice versa
if((k+arr[k]) & 1L)
{
if(l <= k)
l = k+1;
else
l++;
//if right positions, even at even OR odd at odd
if(!((l+arr[l]) & 1L))
{
int temp = arr[k];
arr[k] = arr[l];
arr[l] = temp;
}
//if wrong positions
else
{
//if type different from k type
if((k+l) & 1L)
{
int temp = arr[k];
arr[k] = arr[l];
arr[l] = temp;
k++;
}
}
}
//if the eleeent if right, even at even OR odd at odd
else
k++;
}
for(i = 0; i < n; i++)
printf("%3d", arr[i]);
printf("\n");
return 0;
}
java solution:
public class ArrayOddEven {
public static void main(String[] args) {
int [] a= {2,8,1,9,10,5,7,18,12,13};
ArrayOddEven aoe = new ArrayOddEven();
for(int i=0,j=1;i<a.length && j<a.length;)
{
if(i<a.length && j<a.length){
if((a[i]%2 == 0)&& (a[j]%2 != 0)){
i = i+2;
j = j+2;
}
else if((a[i]%2 != 0) && (a[j]%2 == 0)){
aoe.swap(i, j, a);
i = i+2;
j = j+2;
}
else if((a[i]%2 != 0) && (a[j]%2 !=0)){
int k = i+2;
while(k<a.length && a[k]%2 != 0){
k++;
}
if(k >= a.length){
System.out.print("array finished");
}
else{
int temp = a[k];
while(k>i){
a[k] = a[k-1];
k--;
}
a[k] = temp;
}
i = i+2;
j = j+2;
}
else if((a[i]%2 == 0) && (a[j]%2 == 0)){
int m = j+1;
while(m<a.length && a[m]%2 == 0){
m++;
}
if(m >= a.length){
System.out.print("array finished");
}
else{
int temp = a[m];
while(m>j){
a[m] = a[m-1];
m--;
}
a[m] = temp;
}
i = i+2;
j = j+2;
}
}
}
for(int k : a)
System.out.print(", "+k);
}
public void swap(int i,int j,int []a){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
I don't see a way of doing this in-place without an additional data structure like a stack or a simulated one through recursion. Below is my recursive version. Basically pos, numEven and numOdd are all 0 initially. The idea is to store arr[pos] as a variable, then rely on recursion to properly place all numbers in the rest of the array. After the recursive call, we can then put arr[pos] in the appropriate place. We know where to place it because we keep track of how many even & odd numbers we have seen so far.
Note that I am assuming there's enough even and odd numbers to properly place in the array.
static void rearrange(int[] arr, int pos, int numEven, int numOdd) {
if(pos >= arr.length)
return;
int n = arr[pos];
if(n%2 == 0) {
rearrange(arr, pos+1, numEven+1, numOdd);
arr[2*numEven] = n;
} else {
rearrange(arr, pos+1, numEven, numOdd+1);
arr[2*numOdd+1] = n;
}
}
O(n) algo
- loveCoding September 16, 2012Take two pointers and point to first and second element respectively
1. If first pointer points to odd number and second points to even, they are in correct position so move both pointers by two.
2. If first pointer points to even number and second points to odd, swap values and move both pointers by two.
3. If exactly one pointer moves to wrong position i.e first pointer points to even on second pointer points to odd, move the pointer in correct position by two places and go to step 1.
EDIT : To maintain the order, we can change the third condition by swapping the values at wrong pointer and right pointer before moving forward by two places.