## AMD Interview Question for Analysts

• 0

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

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

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

}
}

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

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

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?

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

yes!

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

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

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

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

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

}

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

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.

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

}

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

}``````

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

}

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;

}
}

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

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;

}

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

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;

}
}

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;

}
}

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;

}
}

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;

}
}

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

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++) {
}
if(array_integers.Count % 2 == 1) sorted.Add(array_integers[middle]);

foreach (var i in sorted) {
Console.Write("{0} ",  i);
}
}``````

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

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

}

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>();

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

}
}

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

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.