Adobe Interview Question
Computer ScientistsCountry: United States
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
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]...............
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;
}
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
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];
}
}
}
}
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;
}
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
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;
}
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;
}
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;
}
#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;
}
{#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;
}}
- Mando Dong August 08, 2015