Adobe Interview Question for Computer Scientists

• 2

Country: United States

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

``````def sort_array array
(0..array.length-1).step(2).each do |index|
if index + 1 < array.length-1 and array[index] > array[index+1]
swap array, index, index+1
end
if index + 2 < array.length-1 and array[index+1] < array[index+2]
swap array, index+1, index+2
end
end
array
end

def swap array, index, index2
temp = array[index]
array[index] = array[index2]
array[index2] = temp
end``````

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

One bubble sort iteration:

``````void swap(int* x, int* y)
{
int t = *x;
*x = *y;
*y = t;
}

void rearrange(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
if (i % 2 == 0)
{
if (arr[i] > arr[i+1])
swap(arr + i, arr + i + 1);
}
else
{
if (arr[i+1] > arr[i])
swap(arr + i, arr + i + 1);
}
}
}``````

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

Just iterate over array and fix this property if it's not true. Fixing the property at n'th step can't break property at n-1'th step since e.g. a[n-2] <= a[n-1] and suppose a[n - 1] <= a[n], then a[n-2] <= a[n] and we can replace a[n-1] with a[n]. Same for >=

``````def rearrange(arr):
for i in xrange(len(arr) - 1):
if i % 2 == 0:
if not arr[i] <= arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
else:
if not arr[i] >= arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]

def check_property(arr):
good = True
for i in xrange(len(arr) - 1):
if i % 2 == 0:
good &= arr[i] <= arr[i + 1]
else:
good &= arr[i] >= arr[i + 1]
if not good:
break
return good

for example in [
[1, 2, 3, 4],
[0, 5, 1, 9, 6, -1],
[2, 1],
[0, 0, 0, 0, 1],
[2, 1, 3, -1, 5, 2, 7]
]:
rearrange(example)
assert check_property(example)
print example``````

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

i am not sure this is the correct or not but think about it.

1) assume array is {7,3,5,6,2,1,9,4,8}
2) sort the array {1,2,3,4,5,6,7,8,9}
3)re arrange like this {1,3,2,4,5,7,6,8,9}

u can do this by swapping array[1] with array[3], array[5] with array[6]...............

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

sorting of array takes nlogn time.

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

{sorting of array takes nlogn time}

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

``sorting of array takes nlogn time``

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

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

Sort array 0 1 2 3 4 5
Then swap each 2 elements starting from index 1 i.e. swap 1 with 2, 3 with 4 and so on
0 <= 2 >= 1 <= 4 >= 3 <= 5 <= 6

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

``````int[] rearrage(int[] a) {
for(int i=0; i<a.Length-2; i++) {
if(i % 2 == 0) {
if(a[i] <= a[i+1])	swap(ref a[i+1], ref a[i]);
else				swap(ref a[i], ref a[i+1]);
}
else {
if(a[i] >= a[i+1])	swap(ref a[i+1], ref a[i]);
else				swap(ref a[i], ref a[i+1]);
}
}
return a;
}

void swap(ref int a, ref int b) {
int temp = a;
a = b;
b = temp;
}``````

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

If array is sorted... Print postfix of those elements.. Then it will be our answer..

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

Print post fix if array is sorted

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

``````def rearrange(arr):
for i in xrange(len(arr) - 1):
if i % 2 == 0:
if not arr[i] <= arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
else:
if not arr[i] >= arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]

def check_property(arr):
good = True
for i in xrange(len(arr) - 1):
if i % 2 == 0:
good &= arr[i] <= arr[i + 1]
else:
good &= arr[i] >= arr[i + 1]
if not good:
break
return good

for example in [
[1, 2, 3, 4],
[0, 5, 1, 9, 6, -1],
[2, 1],
[0, 0, 0, 0, 1]
]:
rearrange(example)
assert check_property(example)
print example``````

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

``````bool ascending = true;
for (int i = 1; i < array.Length; i++) {
if ((array[i] > array[i-1]) != ascending) {
int tmp = array[i-1];
array[i-1] = array[i];
array[i] = tmp;
}
ascending = !ascending;
}``````

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

``````void Reorder(vector<int>& A){
if(!A.size()){
cout<<"Empty Vector"<<endl;
}
for(int i=1;i<A.size();i++){
if(i%2 ==1 ){
if(A[i]<A[i-1]){
A[i] ^= A[i-1];
A[i-1] ^= A[i];
A[i] ^= A[i-1];
}
}
}
for(int i=1;i<A.size();i++){
if(i%2 ==1 && (i != A.size()-1)){
if(A[i]<A[i+1]){
A[i] ^= A[i+1];
A[i+1] ^= A[i];
A[i] ^= A[i+1];
}
}
}
}``````

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

I think this can be achieved through 2 passes which O(n) - even if given vector V is not sorted

Pass - 1) start with i=1. If i is odd and V[i]<V[i-1], swap values
Pass -2 ) Start with i=1. if ( i is odd and i!= V.size()-1) and V[i]<V[i+1], swap values

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

There's a pattern here. First, sort the integers using count sort(linear time). Then, use the pattern...

``````A0 <= A1
A2 <= A1

A2 <= A3
A4 <= A3

A4 <= A5
A6 <= A5

----
1 2 3 4 5 6

A0=1
A2=2
A1=3
-----
A3=5
A2=2
A4=4
-----
A5=6
A4=4
A6=5``````

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

A (n log n) approach. MakeHeap (in-place, linear time). Pop n/2 largest elements, and insert them in the even position of a new array. Insert the remaining elements into the odd positions.

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

Thanks for user smarthbehl sharing this problem. I believe I came up with a linear time constant space solution. Due to code complexity, my code uses recursive, hence it has stack space overhead. But one can convert it into a non-recursive one and get a constant space solution.
Assume elements are distinct. otherwise there may or may not be a problem.

pseudo-code:
median <- quickSelection(A); // linear time, A is bi-partitioned such that A[left elements]<A[medianIndex]=median<A[right elements];
while (leftPointer < medianIndex)
swap(A[leftPointer],A[rightPointer]);
leftPointer+=2; rightPointer-=2;
end;

code:

``````#include <ctime>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int* ZigZagArray(int A[], int n);

int main()
{
srand(time(0));
int N = rand()%20+1;
int *A = new int [N];
for (int i=0; i<N; i++)
{
A[i] = rand()%100;
printf("%02d ",A[i]);
}
printf("\n");
int *B = ZigZagArray(A, N);
for (int i=0; i<N; i++)
{
printf("%02d ",B[i]);
}
printf("\n");
delete [] A;
delete [] B;

return 0;
}

int quickSelect(int A[], int quantile, int L, int R)
{
if (R-L==1)
return L;
int pivotID = L + rand()%(R-L);
int pivot = A[pivotID];
int l = L, r = R-1;
A[pivotID] = A[R-1];
while (l<r)
{
while ((l<r)&&(A[l]<=pivot))
l++;
if (l>=r)
break;
A[r--] = A[l];
while ((l<r)&&(A[r]>pivot))
r--;
if (l>=r)
break;
A[l++] = A[r];
}
pivotID = l;
A[pivotID] = pivot;
if (pivotID==quantile)
return pivotID;
if (pivotID<quantile)
return quickSelect(A,quantile,pivotID+1,R);
else
return quickSelect(A,quantile,L,pivotID);
}

int *ZigZagArray(int A[], int n)
{
int *B = new int [n];
for (int i=0; i<n; i++)
B[i] = A[i];
int medianI = quickSelect(B,n/2,0,n);
int pivot = B[medianI];
int l = 0, r = n-1-(n%2);
while (l<medianI)
{
int k = B[l];
B[l] = B[r];
B[r] = k;
l += 2; r -= 2;
}
return B;
}``````

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

recursive solution

``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define SIZE 10

int arr[SIZE] = { 42, 19, 41, 33, 39, 96, 19, 24, 38, 96 };

void reArrange(int *arr, int i, int size){
if (i == size) return;
int left = i % 2;
int right = left;
int mid = (left == 0) ? 1 : 0;
if (mid){
if (arr[i] > arr[i + 1]) swap(arr + i, arr + i + 1);
if (arr[i + 1] < arr[i + 2]) swap(arr + i + 1, arr + i + 2);
}
else{
if (arr[i] < arr[i + 1]) swap(arr + i, arr + i + 1);
if (arr[i + 1] > arr[i + 2]) swap(arr + i + 1, arr + i + 2);
}
reArrange(arr, i + 1, size);
}
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int main()
{
reArrange(arr, 0, SIZE);
return 0;
}``````

OutPut :: 19 42 33 41 39 96 19 38 24 96

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

Just find the max element for consecutive 3 elements and place it at even position.

``````static void weirdSorting(int[] arr){
int max = 0;
int temp = 0;
for(int i=1;i<arr.length;i+=2){
max = Ideone.findMax(arr,i);
temp = arr[max];
arr[max] = arr[i];
arr[i] = temp;
}

}
static int findMax(int[] arr, int i){
int max = 0;
if(i<arr.length-1){
max = arr[i]>arr[i-1]? i:i-1;
max = arr[i+1]>arr[max]? i+1:max;
}else{
max = arr[i]>arr[i-1]? i:i-1;
}
System.out.println(max +"max	");
return max;
}``````

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

Solution with O(N)

``````void arrangeArray(int[] array){

for(int i=1; i<array.length; i=i+2){
if(array[i-1]>array[i]){
swap(array, i-1, i);
}
if(i+1<array.length && array[i+1]>array[i]){
swap(array, i, i+1);
}
}
}
private void swap(int[] array, int i1, int i2) {
int temp = array[i1];
array[i1]= array[i2];
array[i2]=temp;

}``````

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

``````void arrangeArray(int[] array){

for(int i=1; i<array.length; i=i+2){
if(array[i-1]>array[i]){
swap(array, i-1, i);
}
if(i+1<array.length && array[i+1]>array[i]){
swap(array, i, i+1);
}
}
}

private void swap(int[] array, int i1, int i2) {
int temp = array[i1];
array[i1]= array[i2];
array[i2]=temp;

}``````

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

#include<bits/stdc++.h>
using namespace std;
int main()
{
long int tc,t,i,n,p;
scanf("%d",&tc);
while(tc--)
{
scanf("%ld",&n);long int a[n];
for(i=0;i<n;i++)
scanf("%ld",&a[i]);
//sort(a,a+n);
for(i=0;i<n-1;i++)
{
if(i%2==0)
{
if(a[i]>=a[i+1])
{
t=a[i];a[i]=a[i+1];a[i+1]=t;
}

}
else if(i%2!=0)
{
if(a[i]<=a[i+1])
{
p=a[i];a[i]=a[i+1];a[i+1]=p;
}
}
}
for(i=0;i<n;i++)
printf("%ld ",a[i]);
printf("\n");
}
return 0;
}

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

{#include<bits/stdc++.h>
using namespace std;
int main()
{
long int tc,t,i,n,p;
scanf("%d",&tc);
while(tc--)
{
scanf("%ld",&n);long int a[n];
for(i=0;i<n;i++)
scanf("%ld",&a[i]);
//sort(a,a+n);
for(i=0;i<n-1;i++)
{
if(i%2==0)
{
if(a[i]>=a[i+1])
{
t=a[i];a[i]=a[i+1];a[i+1]=t;
}

}
else if(i%2!=0)
{
if(a[i]<=a[i+1])
{
p=a[i];a[i]=a[i+1];a[i+1]=p;
}
}
}
for(i=0;i<n;i++)
printf("%ld ",a[i]);
printf("\n");
}
return 0;
}}

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.