AMD Interview Question for Analysts


Country: India
Interview Type: In-Person




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

Here's an O(n log n) solution in Python, assuming the input array is unsorted

# Maxmin.py

def splitAt(i,arr):
    return (arr[:i],arr[i:])

def maxmin(a):
    arr = list(a)
    arr.sort() # O(n log n)

    mins,maxes = splitAt(len(arr)/2,arr)
    mins.reverse() # need to pop them in ascending order

    result = []
    while len(maxes) != 0 or len(mins) != 0:
        if len(maxes) != 0:
            result.append(maxes.pop())

        if len(mins) != 0:
            result.append(mins.pop())

    return result


test1 = [1, 2, 3, 4, 5, 6, 7]

assert splitAt(len(test1)/2,test1) == ([1,2,3],[4,5,6,7])
assert maxmin(test1) == [7,1,6,2,5,3,4]

print "tests passed!"

- lick December 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c++, implemention, O(n log n)

void zigZagSort(vector<int>& arr) {
	vector<int> copy = arr;
	int i, k, n;

	sort(copy.begin(), copy.end());

	n = arr.size() * 2 - 1;
	for (i = 0; i < arr.size(); i++) {
		k = i * 2 + 1;
		if (k >= arr.size()) k = n - k;
		arr[k] = copy[i];
	}
}

- kyduke December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinMax {

public static void main(String args[]){
int[] array = {1,2,3,4,5,6,7};
Arrays.sort(array);
int minMaxArray[] = new int[array.length];
for(int index =0,firstPos =0, lastPos = array.length-1;index<array.length;index++){
if(index % 2 != 0){
minMaxArray[index] = array[firstPos];
firstPos++;
}
else{
minMaxArray[index] = array[lastPos];
lastPos--;
}
}
System.out.println("Input:" + Arrays.toString(array));
System.out.println("Output:" + Arrays.toString(minMaxArray));

}
}

- pkshah912 December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Formatted code:

public class MinMax {

    public static void main( String args[] ){
        int[] array = { 1,2,3,4,5,6,7 };
        Arrays.sort( array );

        int minMaxArray[] = new int[ array.length ];
        for( int index = 0, firstPos = 0, lastPos = array.length - 1; index < array.length;index++ ){
            if( index % 2 != 0 ){
                minMaxArray[ index ] = array[ firstPos ];
                firstPos++;
            }
            else {
                minMaxArray[ index ] = array[ lastPos ];
                lastPos--;
            }
        }

        System.out.println( "Input:" + Arrays.toString( array ) );
        System.out.println( "Output:" + Arrays.toString( minMaxArray ) );
    }
}

- Jay January 05, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

is there a solution without using extra space? i.e. swapping elements in input array?

- supatroopa December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

yes!

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

This code solve the problem in O(log(n))

public static void main(String[] args) {
        int [] input = {1,2,3,4,5,6,7};
        int [] output = function1(input);
    }
    
    public static int[] function1( int [] input){
        int n = input.length;
        if (n<=3){ //BASE CASE
            for (int i = 0; i<n; i++){
                if (input[i]>input[0]){ swap(input,i,0);}
                if (input[i]<input[1]){ swap(input,i,1);}
            }
            return input;
        }
        else{ //RECURSIVE
            int p = n/2;
            int [] a = function1(Arrays.copyOfRange(input, 0, p));
            int [] b = function1(Arrays.copyOfRange(input, p, n));
            if (b[0] > a[0]){
                int temp = a[0];
                a[0] = b[0];
                b[0] = temp; 
            }
            if (b[1] < a[1]){
                int temp = a[1];
                a[1] = b[1];
                b[1] = temp;
            }
            int [] result = Arrays.copyOf(a, a.length + b.length);
            System.arraycopy(b, 0, result, a.length, b.length);
            return result;
        }
    }
    
    public static void swap(int [] array, int pos1, int pos2){
        int temp = array[pos1];
        array[pos1] = array[pos2];
        array[pos2] = temp;
    }

- Fabio December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This code solve the problem in O(log(n))

public static void main(String[] args) {
        int [] input = {1,2,3,4,5,6,7};
        int [] output = function1(input);
    }
    
    public static int[] function1( int [] input){
        int n = input.length;
        if (n<=3){ //BASE CASE
            for (int i = 0; i<n; i++){
                if (input[i]>input[0]){ swap(input,i,0);}
                if (input[i]<input[1]){ swap(input,i,1);}
            }
            return input;
        }
        else{ //RECURSIVE
            int p = n/2;
            int [] a = function1(Arrays.copyOfRange(input, 0, p));
            int [] b = function1(Arrays.copyOfRange(input, p, n));
            if (b[0] > a[0]){
                int temp = a[0];
                a[0] = b[0];
                b[0] = temp; 
            }
            if (b[1] < a[1]){
                int temp = a[1];
                a[1] = b[1];
                b[1] = temp;
            }
            int [] result = Arrays.copyOf(a, a.length + b.length);
            System.arraycopy(b, 0, result, a.length, b.length);
            return result;
        }
    }
    
    public static void swap(int [] array, int pos1, int pos2){
        int temp = array[pos1];
        array[pos1] = array[pos2];
        array[pos2] = temp;
    }

- fobia December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This code solve the problem in O(log(n))

public static void main(String[] args) {
        int [] input = {1,2,3,4,5,6,7};
        int [] output = function1(input);
    }
    
    public static int[] function1( int [] input){
        int n = input.length;
        if (n<=3){ //BASE CASE
            for (int i = 0; i<n; i++){
                if (input[i]>input[0]){ swap(input,i,0);}
                if (input[i]<input[1]){ swap(input,i,1);}
            }
            return input;
        }
        else{ //RECURSIVE
            int p = n/2;
            int [] a = function1(Arrays.copyOfRange(input, 0, p));
            int [] b = function1(Arrays.copyOfRange(input, p, n));
            if (b[0] > a[0]){
                int temp = a[0];
                a[0] = b[0];
                b[0] = temp; 
            }
            if (b[1] < a[1]){
                int temp = a[1];
                a[1] = b[1];
                b[1] = temp;
            }
            int [] result = Arrays.copyOf(a, a.length + b.length);
            System.arraycopy(b, 0, result, a.length, b.length);
            return result;
        }
    }
    
    public static void swap(int [] array, int pos1, int pos2){
        int temp = array[pos1];
        array[pos1] = array[pos2];
        array[pos2] = temp;
    }

- petroni@dis.uniroma1.it December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def func(a=[]):
        b = []
        c = len(a)-1
        for n in range(0,c,1):
                if n != c:
                        b.append(a[c])
                        b.append(a[n])
                elif n == c:
                        b.append(a[n])
                        break
                else:
                        break
                c-=1
        return b

a = [1, 2, 3, 4, 5, 6, 7]
print func(a)

- caf4 December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void rearrange(int[] a){

        Arrays.sort(a);
        int[] result = new int[a.length];
        int l = 0,r = a.length-1,i = 0;

        while (l<r){
            result[i++] = a[r--];
            result[i++] = a[l++];
        }
        
        if(l==r) result[result.length-1] = a[l];
        
        for (int n : result) System.out.print(n);

}

- abhay0609 December 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.
DP, D&C.
O(n*logn).

using System;

namespace ZigZagArrange {

    public static class Program {

        static public int[] ZigZagArrange( int[] arr ) {

            if ( arr.Length < 2 ) { return arr; }

            int[] part1 = GetReArrangedPart1( arr );
            int[] part2 = GetPart2AsIs( arr, part1.Length );

            if ( part2 != null ) {
                part2 = ZigZagArrange( part2 );
            }
            return Concat( part1, part2 );
        }

        static private int[] GetReArrangedPart1( int[] arr ) {

            int i = 1;
            while( arr[ 0 ] == arr[ i ] && i < arr.Length - 1 ) { i++; } // handle duplicates

            int fMinI = arr[ 0 ] > arr[ i ] ? i : 0 ;
            int fMaxI = arr[ 0 ] < arr[ i ] ? i : 0 ;

            if ( fMaxI == 0 ) {
                fMinI = getfMinI( arr, i );
            } else {
                fMaxI = getfMaxI( arr, i );
            }
            int[] res = new int[ Math.Abs( fMaxI - fMinI ) + 1 ];
            for ( i = 0; i <= Math.Max( fMinI, fMaxI ); i++ ) {
                res[ i ] = arr[ i ];
            }
            res = ReArrange( res, fMaxI, fMinI );
            return res;
        }

        private static int[] ReArrange( int[] arr, int fMaxI, int fMinI ) {
            int[] res = new int[ arr.Length ];
            int i = 0;
            while ( i < res.Length ) {
                res[ i++ ] = arr[ fMaxI ];
                if ( i >= res.Length ) { break; }
                res[ i++ ] = arr[ fMinI ];
                fMaxI = fMaxI > fMinI ? fMaxI - 1 : fMaxI + 1;
                fMinI = fMinI > fMaxI ? fMinI - 1 : fMinI + 1;
            }
            return res;
        }

        private static int[] Concat( int[] part1, int[] part2 ) {
            if ( part1 == null ) { return part2; }
            if ( part2 == null ) { return part1; }
            int[] res = new int[ part1.Length + part2.Length ];
            for ( int i = 0; i < part1.Length; i++ ) {
                res[ i ] = part1[ i ];
            }
            for ( int i = 0; i < part2.Length; i++ ) {
                res[ part1.Length + i ] = part2[ i ];
            }
            return res;
        }

        private static int[] GetPart2AsIs( int[] arr, int p2Length ) {
            if ( arr.Length == p2Length ) { return null; }
            int[] res  = new int[ arr.Length - p2Length ];
            for ( int i = p2Length; i < arr.Length; i++ ) {
                res[ i - p2Length ] = arr[ i ];
            }
            return res;
        }

        static private int getfMinI( int[] arr, int i ) {
            if ( i == arr.Length - 1 ) { return i; }
            if ( arr[ i ] >= arr[ i + 1 ] ) {
                return getfMinI( arr, i + 1 );
            }
            return i;
        }

        static private int getfMaxI( int[] arr, int i ) {
            if ( i == arr.Length - 1 ) { return i; }
            if ( arr[ i ] <= arr[ i + 1 ] ) {
                return getfMaxI( arr, i + 1 );
            }
            return i;
        }

        static void Main(string[] args) { }
    }
}

- zr.roman December 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

could you please clarify what will be the output if we are given input {1, 2, 3, 4, 5, 6, 7, 6,5,4,3,2,1}.
Many thanks.

- zr.roman December 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxMin {

public static void main(String[] args) {
// TODO Auto-generated method stub
int max=0;
int min=0;
int a[]= {5,6,7,1,3,4};
if(a[0] > a[1]) {
max = a[0];
min =a[1];
} else {
max = a[1];
min = a[0];
}
for(int i=0;i<a.length-1;i++) {
if(a[i] > max) {
max = a[i];
} if(a[i] < min) {
min = a[i];
}
}
int b[] = new int[a.length];
int i = 0;
int j=2;
b[0] = max;
b[1] = min;
while (i<a.length && j <b.length) {
if(a[i] != max && a[i]!=min) {
b[j] = a[i];
i++;j++;
}else {
i++;
}
}
for(int k=0;k<b.length;k++) {
System.out.println(b[k]);
}
//System.out.println(max + " " + min);
}

}

- Anonymous December 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxMin {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int max=0;
		int min=0;
		int a[]= {5,6,7,1,3,4};
		if(a[0] > a[1]) {
			max = a[0];
			min =a[1];
		} else {
			max = a[1];
			min = a[0];
		}
		for(int i=0;i<a.length-1;i++) {
			if(a[i] > max) {
				max = a[i];
			} if(a[i] < min) {
				min = a[i];
			}
		}
		int b[] = new int[a.length];
		int i = 0;
		int j=2;
		b[0] = max;
		b[1] = min;
		while (i<a.length && j <b.length) {
			if(a[i] != max && a[i]!=min) {
				b[j] = a[i];
				i++;j++;
			}else {
				i++;
			}
		}
		for(int k=0;k<b.length;k++) {
			System.out.println(b[k]);
		}
		//System.out.println(max + " " + min);
	}

}

public class MaxMin {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int max=0;
		int min=0;
		int a[]= {5,6,7,1,3,4};
		if(a[0] > a[1]) {
			max = a[0];
			min =a[1];
		} else {
			max = a[1];
			min = a[0];
		}
		for(int i=0;i<a.length-1;i++) {
			if(a[i] > max) {
				max = a[i];
			} if(a[i] < min) {
				min = a[i];
			}
		}
		int b[] = new int[a.length];
		int i = 0;
		int j=2;
		b[0] = max;
		b[1] = min;
		while (i<a.length && j <b.length) {
			if(a[i] != max && a[i]!=min) {
				b[j] = a[i];
				i++;j++;
			}else {
				i++;
			}
		}
		for(int k=0;k<b.length;k++) {
			System.out.println(b[k]);
		}
		//System.out.println(max + " " + min);
	}

}

- supreme December 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{

	int a[] = { 10, 2, 1,4,7,8,3,9,5,6};

	//o/p---10,1,8,2,7,3,4

	//sort the array
	int len = sizeof(a)/sizeof(int);
	for (int i = 0; i <len-1; i++)
	{
		for (int  j = 0; j < len-i-1; j++)
		{		
			int temp = a[j];
			if (a[j] > a[j + 1])
			{
				//swap
				temp = a[j + 1];
				a[j + 1] = a[j];
				a[j] = temp;
			}
		}
	}
	//o/p form
	int k = 0;
	for (int i = len - 1; i > 0; i -= 2)
	{
		int temp = a[len-1];
		int j = 0;
		for (j = len - 1; j > k; j--)
		{
			a[j] = a[j - 1];
		}
		k += 2;
		a[j] = temp;
	}

	return 0;

}

- arun kumar December 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In place soluton in Java

package com.concurrency.pkg;

import java.util.Arrays;

public class FirstMaxFirstMin {

public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {1,2,3,4,5,6,7,8,9,10,11};
Arrays.sort(a);
int j = a.length-1;
int i =0;
for(; i<j ;i+=2 )
{
int start = a[i];
int last = a[a.length-1];
int next = a[i+1];

if((i+1) == j){
a[i]= a[j];
a[j]= last;
a[a.length-1] = start;
swapLastTwo(a);
break;
}

a[i]= a[j];
a[i+1]= (i > 0) ? last : start;
a[a.length - 1] = (i > 0) ? start : next;
a[j] = next;
if( a[a.length-2] < a[a.length-1]){
swapLastTwo(a);
}
j--;
}
if((a.length - i) > 2 && (a.length%2 != 0) ){
int temp = a[a.length - 2];
a[a.length - 2] = a[a.length - 1];
a[a.length - 1] = temp;


}
for (i =0 ; i< a.length ; i++)
System.out.print(a[i]+" , ");

}
private static void swapLastTwo(int a[]){
int temp = a[a.length-1];
a[a.length-1] = a[a.length-2];
a[a.length-2] = temp;
}

private static int swap(int i , int j, int[] a){
int next = a[i+1];
int last = a[a.length-1];
int curr = a[i];
a[i+1] =
a[i]= a[--j];
a[i+1]= a[i];
if( i == 0)
a[j]= next;
return j;

}
}

- Suresh Patel December 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort it and then go to the middle of the array and pull out the element and put that in the end of the output array.

After sorting
1 2 3 4 5 6
If size of the array is even or odd you will do accordingly pull out the array element from the middle. After that you start going from mid to start and mid to end and pull out elements and put it in alternate places in the output array. You should use recursion or iterative approach, either will work.
6 1 5 2 4 3

- aka December 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My first time posting.
hope it helps.
It's all basic code

public class SpecialOrder {
// main application
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}

// helper method to help me print the array
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}

// I assume that the array is not sorted, and we're not allowed to use the code from library
public static void sortSpecialOrder(int [] orig){
int number;//the length of array
// if the length is smaller than 2, I don't need to sort it.
if((number = orig.length) >= 2){
int num = 0;// variable to help me check the loop times and the position
while(num < number)
{
// variables that help me find the position of the biggest and smallest variables among the rest ones
// every time when I finish a loop, I'll sort start from the unsorted part.
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
// every time when I finish a loop, I'll sort start from the unsorted part.
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}

if(min > temp )
{
min = temp;
minIndex = index;
}
}
// the confusing part
// problem is if the position I want to swap is exactly the position I'm going to put my another value,
// I need to change that "another" value first to make sure there's no effect for first one. eg. I have
// 0,1,_,_,_,7, if I swap 0 and 7 first, the value of minIndex position becomes 7, which will swap again.
if(maxIndex == num + 1)
{
// but both min and max are at the exact opposite position. I just need to swap them one time.
if(minIndex == num)
maxMove(num,maxIndex,orig);
// first move the max, then min, in this case
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
// first move the min, then max, in this case
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
// if all 4 positions are different(minIndex, num, num+1, maxIndex), whatever order will be fine.
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
//every loop, I'll determine the 2 positions
num = num + 2;
//when I have one left, I'll just leave it there, since it's the one at the middle
if(num + 1 == number)
break;
}
}
}

//helper method that help me move the max part
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
//helper method that help me move the min part
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;

}
public static void sortSpecialOrder(int [] orig){
int number;
if((number = orig.length) >= 2){
int num = 0;
while(num < number)
{
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;

int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}

if(min > temp )
{
min = temp;
minIndex = index;
}
}
if(maxIndex == num + 1)
{
if(minIndex == num)
maxMove(num,maxIndex,orig);
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
num = num + 2;
if(num + 1 == number)
break;
}
}
}

public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}

public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;

}

- Kaige December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SpecialOrder
{// main application
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));}

// helper method to help me print the array
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;}

// I assume that the array is not sorted, and we cannot use the code from library
public static void sortSpecialOrder(int [] orig){
int number;//the length of array
// if the length is smaller than 2, I don't need to sort it.
if((number = orig.length) >= 2){
int num = 0;// variable to help me check the loop times and the position
while(num < number)
{
// variables that help me find the position of the biggest and smallest variables among the rest ones
// every time when I finish a loop, I'll sort start from the unsorted part.
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
// every time when I finish a loop, I'll sort start from the unsorted part.
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;}

if(min > temp )
{
min = temp;
minIndex = index;}}
// the confusing part
// problem is if the position I want to swap is exactly the position I'm going to put my another value,
// I need to change that "another" value first to make sure there's no effect for first one. eg. I have
// 0,1,_,_,_,7, if I swap 0 and 7 first, the value of minIndex position becomes 7, which will swap again.
if(maxIndex == num + 1)
{
// but both min and max are at the exact opposite position. I just need to swap them one time.
if(minIndex == num)
maxMove(num,maxIndex,orig);
// first move the max, then min, in this case
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);}}
// first move the min, then max, in this case
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);}
// if all 4 positions are different(minIndex, num, num+1, maxIndex), whatever order will be fine.
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig); }
//every loop, I'll determine the 2 positions
num = num + 2;
//when I have one left, I'll just leave it there, since it's the one at the middle
if(num + 1 == number)
break;}}}

//helper method that help me move the max part
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;}
//helper method that help me move the min part
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;}

- Kaige December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package reviewSet;

public class SpecialOrder {
// main application
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}

// helper method to help me print the array
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}

// I assume that the array is not sorted, and we're not allowed to use the code from library
public static void sortSpecialOrder(int [] orig){
int number;//the length of array
// if the length is smaller than 2, I don't need to sort it.
if((number = orig.length) >= 2){
int num = 0;// variable to help me check the loop times and the position
while(num < number)
{
// variables that help me find the position of the biggest and smallest variables among the rest ones
// every time when I finish a loop, I'll sort start from the unsorted part.
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
// every time when I finish a loop, I'll sort start from the unsorted part.
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}

if(min > temp )
{
min = temp;
minIndex = index;
}
}
// the confusing part
// problem is if the position I want to swap is exactly the position I'm going to put my another value,
// I need to change that "another" value first to make sure there's no effect for first one. eg. I have
// 0,1,_,_,_,7, if I swap 0 and 7 first, the value of minIndex position becomes 7, which will swap again.
if(maxIndex == num + 1)
{
// but both min and max are at the exact opposite position. I just need to swap them one time.
if(minIndex == num)
maxMove(num,maxIndex,orig);
// first move the max, then min, in this case
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
// first move the min, then max, in this case
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
// if all 4 positions are different(minIndex, num, num+1, maxIndex), whatever order will be fine.
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
//every loop, I'll determine the 2 positions
num = num + 2;
//when I have one left, I'll just leave it there, since it's the one at the middle
if(num + 1 == number)
break;
}
}
}

//helper method that help me move the max part
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
//helper method that help me move the min part
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;

}
}

- Kaige December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package reviewSet;

public class SpecialOrder {
// main application
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}

// helper method to help me print the array
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}

// I assume that the array is not sorted, and we're not allowed to use the code from library
public static void sortSpecialOrder(int [] orig){
int number;//the length of array
// if the length is smaller than 2, I don't need to sort it.
if((number = orig.length) >= 2){
int num = 0;// variable to help me check the loop times and the position
while(num < number)
{
// variables that help me find the position of the biggest and smallest variables among the rest ones
// every time when I finish a loop, I'll sort start from the unsorted part.
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
// every time when I finish a loop, I'll sort start from the unsorted part.
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}

if(min > temp )
{
min = temp;
minIndex = index;
}
}
// the confusing part
// problem is if the position I want to swap is exactly the position I'm going to put my another value,
// I need to change that "another" value first to make sure there's no effect for first one. eg. I have
// 0,1,_,_,_,7, if I swap 0 and 7 first, the value of minIndex position becomes 7, which will swap again.
if(maxIndex == num + 1)
{
// but both min and max are at the exact opposite position. I just need to swap them one time.
if(minIndex == num)
maxMove(num,maxIndex,orig);
// first move the max, then min, in this case
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
// first move the min, then max, in this case
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
// if all 4 positions are different(minIndex, num, num+1, maxIndex), whatever order will be fine.
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
//every loop, I'll determine the 2 positions
num = num + 2;
//when I have one left, I'll just leave it there, since it's the one at the middle
if(num + 1 == number)
break;
}
}
}

//helper method that help me move the max part
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
//helper method that help me move the min part
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;

}
}

- Kaige December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package reviewSet;

public class SpecialOrder {
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}

public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}

public static void sortSpecialOrder(int [] orig){
int number;
if((number = orig.length) >= 2){
int num = 0;
while(num < number)
{
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}

if(min > temp )
{
min = temp;
minIndex = index;
}
}
if(maxIndex == num + 1)
{
if(minIndex == num)
maxMove(num,maxIndex,orig);
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
num = num + 2;
if(num + 1 == number)
break;
}
}
}

public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;

}
}

- Kaige December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package reviewSet;

public class SpecialOrder {
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}

public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}

public static void sortSpecialOrder(int [] orig){
int number;
if((number = orig.length) >= 2){
int num = 0;
while(num < number)
{
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}

if(min > temp )
{
min = temp;
minIndex = index;
}
}
if(maxIndex == num + 1)
{
if(minIndex == num)
maxMove(num,maxIndex,orig);
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
num = num + 2;
if(num + 1 == number)
break;
}
}
}

public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;

}
}

- Kaige December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is O(n/2) if input array is already sorted. Yes, that's the same as O(n) theoretically but in practice, n and n/2 could make a lot of difference for large n.

int *maxmin(int arr[], int size)
{
    // sort array in ascending order if not already sorted 

    // create new array
    int *outputarr = new int [size];

    int i, j;
    for (i=0, j=size-1; i <= j; i++, j--)
    {
        outputarr[i*2] = arr[j];
        if (i == j) break;          // so we don't write outside of array
        outputarr[i*2+1] = arr[i];
    }

    return outputarr;
}

- aman.wardak December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void RearrangeArraysEasy() {
			List<int> array_integers =  new List<int> {  10, 1, 29, 8, 10, 45, 56, 100, 98, 34, 11, 9 };
			array_integers.Sort();
			
			List<int> sorted = new List<int>();
			int middle = array_integers.Count / 2;
			for(int i = 0; i< middle; i++) {
				sorted.Add(array_integers[array_integers.Count-1] - i);
				sorted.Add(array_integers[i]);
			}
			if(array_integers.Count % 2 == 1) sorted.Add(array_integers[middle]);
			
			foreach (var i in sorted) {
				Console.Write("{0} ",  i);
			}
		}

- maximilianorios December 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's in-place and O(n):

def maxMin(array):
    for index in range(len(array) - 2, -1, -1):
        if array[index + 1] > array[index]:
            aux = array[index + 1]
            array[index + 1] = array[index]
            array[index] = aux

        if index < len(array) - 2:
            if array[index + 2] < array[index + 1]:
                aux = array[index + 2]
                array[index + 2] = array[index + 1]
                array[index + 1] = aux

    return array

print maxMin([1, 2, 3, 4, 5, 6, 7])                     # [7, 1, 2, 3, 4, 5, 6]
print maxMin([100000, 200, 31235, 40, 522, 6, 748])     # [100000, 6, 31235, 200, 748, 40, 522]
print maxMin([7, 6, 5, 4, 3, 2, 1])                     # [7, 1, 6, 5, 4, 3, 2]

- kiamli December 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void Sorting(int Number[],int size)
{
int temp;
int count = size /2;
int k = 0;
int incr = 0;
while(k < count)
{
for(int i=incr;i<size;i++)
{
for(int j = i+1;j<size;j++)
{
if(Number[j] > Number[i])
{
temp = Number[j];
Number[j] = Number[i];
Number[i] = temp;
}
}
}
incr++;
for(int i = incr;i<size;i++)
{
for(int j = i+1;j<size;j++)
{
if(Number[j] < Number[i])
{
temp = Number[i];
Number[i] = Number[j];
Number[j] = temp;
}
}
}
incr++;
k++;
}

for(int k=0;k<size;k++)
{
std::cout<<Number[k];
}

}

- Rohit Hajare December 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
class TestSort1{
public static void main(String args[]){

ArrayList<Integer> al=new ArrayList<Integer>();
al.add(5);
al.add(1);
al.add(7);
al.add(3);

Collections.sort(al);
Iterator itr=al.iterator();

int size=al.size()-1;
System.out.println(al.get(size));
while(size>0){
System.out.println(itr.next());
size--;
}




}
}

- Lareb Zafar June 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void maxMin(int[] a) {
		Arrays.sort(a);
		int[] b=new int[a.length];
		for(int i=0,j=0,k=a.length-1; i<a.length;i++) {
			if(i%2==0) {
				b[i]=a[k];
				k--;
			}
			else {
				b[i]=a[j];
				j++;
			}
		}
		System.out.println(Arrays.toString(a));
		System.out.println(Arrays.toString(b));
	}

- Shradha December 17, 2015 | 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