Interview Question
Country: India
Interview Type: In-Person
class Main
{
public static void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String arr[])
{
int elem[] =
{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
};
int p[] = new int[20];
createPosArr(p);
System.out.println(Arrays.toString(p));
sort(elem, p);
System.out.println(Arrays.toString(elem));
}
public static void createPosArr(int pos[])
{
int i = pos.length - 1;
int j = 0;
while (i - 1 >= 0)
{
pos[i] = j;
pos[i - 1] = (pos.length - 1) - j;
j++;
i = i - 2;
}
}
public static void sort(int a[], int b[])
{
for (int i = 0; i < a.length; i++)
{
while (i != b[i])
{
int c = a[b[i]];
a[b[i]] = a[i];
a[i] = c;
swap(b, i, b[i]);
}
}
}
}
This sample code uses no temp variables, aka "extra space"
public class ArraySort
{
public static void Sort02(int[] array)
{
if (array == null || array.Length == 1)
return;
if (array.Length == 2)
{
Swap(array, 0, 1);
return;
}
for (int left = -1, right = array.Length, index = right - 1; index > left && index > -1; index--)
{
if ((array.Length - index) % 2 == 1)
{
// Updating the left side...
Swap(array, index, ++left);
}
else
{
// Updating the right side..
Swap(array, index, --right);
}
}
// At this point for even lengthed arrays, the majority of the Array
// should be sorted less its middle two elements.
if (array.Length % 2 == 0)
Swap(array, array.Length / 2, array.Length / 2 - 1);
}
private static void Swap(int[] array, int indexA, int indexB)
{
// TODO: validate input
int temp = array[indexA];
array[indexA] = array[indexB];
array[indexB] = temp;
}
}
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
bool flag=false;
void rever(vector<int>&V,int start,int end)
{
if(start>=end)
return;
for(int i=start,j=end;i<j;i++,j--)
swap(V[i],V[j]);
if(flag==false)
{
flag=!flag;
rever(V,start+1,end);
}
else
{
flag=!flag;
rever(V,start,end-1);
}
}
int main(void)
{
vector<int>V;
int n;
cin>>n;
int x;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
V.push_back(x);
}
rever(V,0,V.size()-1);
for(int i=0;i<V.size();i++)
cout<<V[i]<<" ";
return 0;
}
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
bool flag=false;
void rever(vector<int>&V,int start,int end)
{
if(start>=end)
return;
for(int i=start,j=end;i<j;i++,j--)
swap(V[i],V[j]);
if(flag==false)
{
flag=!flag;
rever(V,start+1,end);
}
else
{
flag=!flag;
rever(V,start,end-1);
}
}
int main(void)
{
vector<int>V;
int n;
cin>>n;
int x;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
V.push_back(x);
}
rever(V,0,V.size()-1);
for(int i=0;i<V.size();i++)
cout<<V[i]<<" ";
return 0;
}
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
bool flag=false;
void rever(vector<int>&V,int start,int end)
{
if(start>=end)
return;
for(int i=start,j=end;i<j;i++,j--)
swap(V[i],V[j]);
if(flag==false)
{
flag=!flag;
rever(V,start+1,end);
}
else
{
flag=!flag;
rever(V,start,end-1);
}
}
int main(void)
{
vector<int>V;
int n;
cin>>n;
int x;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
V.push_back(x);
}
rever(V,0,V.size()-1);
for(int i=0;i<V.size();i++)
cout<<V[i]<<" ";
return 0;
}
#include <stdio.h>
#include <stdlib.h>
void print(int v[], int n)
{
for (int i=0; i<n; ++i)
printf("%d ", v[i]);
printf("\n");
}
int* sortArr(int v[], int n)
{
int *t = (int *) malloc(n*sizeof(int));
int i;
int j = 0;
for (i=n-1; i>=0 && j<n; i-=2, ++j)
t[j] = v[i];
for (i=((n%2) ? 1 : 0); i<n && j<n; i+=2, ++j)
t[j] = v[i];
return t;
}
int main()
{
int v[] = {3,6,7,14,19,21,26,32,38,40,41,46,53,54,60,66,70};
int n = sizeof(v)/sizeof(v[0]);
print(v,n);
int *t = sortArr(v,n);
print(t,n);
free(t);
return 0;
}
Hi. I couldn't find a O(n) algoritm to it that would truly work without any extra space. I only have O(nlogn) in place solution. So the basic idea is to try to split the array to two regions left and right. In right half of the array you have all the second largest at last, fourth largest at last -1 etc. You can do it in one for loop with swap function inside, and after this loop you have all this elements in place. In the left half of the array after the for loop you have all the elements like largest at first, third largest at second etc. but they are out of place so we need to sort it. I choose quicksort to sort left half of array in desc order to do it in place.
For example {1,2,3,4,5,6} array after for loop should be something like this {4,2,6,1,3,5}.Notice left half out of order so we quick sort left half and we have our answer {6,4,2,1,3,5}.
public class Order{
public static void quickSort(int a[], int left, int right)
{
if(left >= right)
{
return;
}else
{
int pivot = partitionIt(a, left, right);
quickSort(a, left, pivot - 1);
quickSort(a, pivot, right);
}
}
public static int partitionIt(int a[], int left, int right)
{
int pivot = right;
while(true)
{
while(left < right && a[++left] > a[pivot])
;
while(right > left && a[--right] < a[pivot])
;
if(left < right)
{
swap(a, left, right);
}else
{
break;
}
}
swap(a, left, pivot);
return left;
}
private static void swap(int a[], int ind1, int ind2)
{
int temp = a[ind1];
a[ind1] = a[ind2];
a[ind2] = temp;
}
public static void reOrder(int a[])
{
int right = a.length - 1;
//for loop shift apropriate group of numbers to right half
//taking advantage of fact that input is sorted
for(int i = a.length - 2; i >= 0; i -= 2)
{
swap(a, i, right--);
}
//sort left group, because they are out of place even thou in apropriate group
quickSort(a, -1, right);
}
public static void main(String []args){
int a[] = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14};
reOrder(a);
for(int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
//14,12,10,8,6,4,2,1,3,5,7,9,11,13
}
}
This sample code uses some temp variables, aka "extra space"
- OregonMike August 25, 2016using static ArraySorting.LastUpdatedSide; namespace ArraySorting { public enum LastUpdatedSide { LeftSide = 0, RightSide = 1 }; public class ArraySort { public static void Sort01(int[] array) { if (array == null || array.Length == 1) return; if (array.Length == 2) { Swap(array, 0, 1); return; } int left = -1; int right = array.Length; int index = right - 1; LastUpdatedSide lastUpdatedSide = RightSide; for (; index > left && index > -1; index--) { if (lastUpdatedSide == RightSide) { // Updating the left side... Swap(array, index, ++left); lastUpdatedSide = LeftSide; } else { // Updating the right side.. Swap(array, index, --right); lastUpdatedSide = RightSide; } } // At this point for even lengthed arrays, the majority of the Array // should be sorted less its middle two elements. if (array.Length % 2 == 0) Swap(array, --right, ++left); } private static void Swap(int[] array, int indexA, int indexB) { // TODO: validate input int temp = array[indexA]; array[indexA] = array[indexB]; array[indexB] = temp; } } }