Adobe Interview Question for Computer Scientists


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

- Mando Dong August 08, 2015 | Flag Reply
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);
		}
	}
}

- JonathanBarOr November 01, 2015 | Flag Reply
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

- mitmeedle August 02, 2015 | Flag Reply
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]...............

- manoj August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorting of array takes nlogn time.

- samrath October 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

{sorting of array takes nlogn time}

- samrath October 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorting of array takes nlogn time

- samrath October 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

is A sorted already?

- anon August 01, 2015 | Flag Reply
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

- Dee August 02, 2015 | Flag Reply
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;
	}

- tus124 August 02, 2015 | Flag Reply
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..

- Praveen August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Print post fix if array is sorted

- Praveen August 02, 2015 | Flag Reply
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

- Anonymous August 02, 2015 | Flag Reply
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;
    }

- Frank August 02, 2015 | Flag Reply
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];
           }
       }
   }   
}

- Srinivas August 05, 2015 | Flag Reply
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

- Srinivas August 05, 2015 | Flag Reply
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

- Yev August 05, 2015 | Flag Reply
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.

- Pyramid August 28, 2015 | Flag Reply
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;
}

- Pyramid September 03, 2015 | Flag Reply
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

- praveen pandit March 03, 2016 | Flag Reply
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;
	}

- Joey March 07, 2016 | Flag Reply
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;
		
	}

- shikha August 06, 2016 | Flag Reply
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;
		
	}

- shikha August 06, 2016 | Flag Reply
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;
}

- ROHIT KUMAR August 23, 2016 | Flag Reply
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;
}}

- Rohit Rumani August 23, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More