## Adobe Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

O(n) algo
Take 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.

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

And what if both pointers point to odd numbers?

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

That will fall in the case 3, where exactly one pointer points to wrong number(pointer 2 which points to odd number)

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

Not able to get the (3) point can u explain further? How does it brings the wrong pointer value to right place?

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

Still don't see it, [1, 3, 5, 2, 4, 7, 6, 8].

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

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 ?

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

Extreme case : 6 6 6 6 6 6 1 1 1 1 1 1

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

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

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.

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

I think we have to assume the number of odd numbers and the number of even numbers is the same.

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

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] = ??

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

for : {1,2,4,7} ans shuld be : {1,2,7,4}.

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

The position of odd numbers should be same with respect to odd numbers and position of even numbers should be same with respect to even numbers.

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

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

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

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

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

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

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

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

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

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 .

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

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

Comment hidden because of low score. Click to expand.
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.

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

They want in-place algo!

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

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.

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

Cant the original qs be edited instead in mid of discussion ?

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

Also, here in example you are putting an odd element at even index .. as element 1 is put at index 0 and so on.

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

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

}

}
}

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

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

}

}

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

it has to be in-place

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

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.

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

Stop posting your own stupid problems.

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

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

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

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

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

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

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

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

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.