## Interview Question

Country: India
Interview Type: In-Person

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

This sample code uses some temp variables, aka "extra space"

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

}
}``````

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

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

}``````

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

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

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

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

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

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

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

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

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

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

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

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

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.