## Amazon Interview Question for Software Engineer / Developers

Team: Kindle
Country: India
Interview Type: In-Person

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

a quick sort version

``````#include <iostream>
#include <iterator>
#include <algorithm>
#include <cmath>
using namespace std;

void Swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}

void QuickSort(int * a, int beg, int step, int end, bool bAsc)
{
int n = ceil( (end - beg) / step);
if (n ==0 || n == 1 || n < 0)
return;

int v = a[beg];
int i = beg + step;
int j = i;
// the invariation is a[beg:i) <= v and a[i:j) > v and a[j:end) are unknown
while (j < end)
{
if ((a[j] > v && bAsc) || (a[j] < v && !bAsc))
{
j += step;
}
else
{
Swap(a + j, a + i);
j += step;
i += step;
}
}
Swap(a + beg, a + i - step);
QuickSort(a, beg, step, i - step, bAsc);
QuickSort(a, i, step, end, bAsc);

}
int main(int argc, char **argv)
{
int a[] = {3, 6, 7, 8, 1, 4, 2, 4, 6, 8, 10};
int n = sizeof(a) / sizeof(int);
QuickSort(a, 0 , 2, n, true);
QuickSort(a, 1, 2, n, false);
copy(a, a + n, ostream_iterator<int>(cout, " "));
cout << endl;
return 0;
}``````

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

Take all even positions into one array and odd positions in to 2nd array... O(n)
Apply any good sorting algorithm for both arrays... O(nlogn)
merge them... O(n)

soo overall time complexity would be: O(nlogn)

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

Why don't you sort the numbers using quick sort (nlogn) and then swap the integers at odd positions O(n). Why do you need extra mem ?.

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

What do you mean exactly by swaping the integers at odd positions?

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

swap - take two pointers (firstOdd, LastOdd)
whie(firstOdd < lastOdd){
swap(a[fistOdd],a[LastOdd]
firstOdd+2;
LastOdd-2;
}

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

@guru:good solution.

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

@guru:
Take array: [3,2,4,5,1,0,6,8,7]
Idle output: [1,8,3,5,4,26,0,7]

But if my understanding is correct according to you...
Initially sort: [0,1,2,3,4,5,6,7,8] and then swap odd position elements...
output: [0,7,2,5,4,3,6,1,8]

tell me if I am wrong...

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

@loknathsudhaka - that is the output you want right ?

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

No..the output should be: [1,8,3,5,4,2,6,0,7]

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

guru, this solution wont work...odd and even positions need to be treated separately.

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

-As you are using extra space here...you can make your algo efficient by using counting sort --O(n).
-B'coz u are traversing the array to separate the elements, at the same time get the "K".

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

void sortTheArry(int *arr,int len)
{
for(int i=0;i<len;i++)
{
for(int j=0;j<len-i-2;j++)
{
if(j%2==0)
{
if(arr[j]>arr[j+2])
{
int val=arr[j];
arr[j]=arr[j+2];
arr[j+2]=val;
}
}
else
{
if(arr[j]<arr[j+2])
{
int val=arr[j];
arr[j]=arr[j+2];
arr[j+2]=val;
}
}
}
}

}

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

``````#include<stdio.h>
#include<conio.h>
void swap(int *a,int *b){
int temp;
temp=*a;
*a=*b;
*b=temp;
}
int partition(int a[],int start,int end,int flag){
int i =start,j;
if(flag)
{
int pivote = a[end];
for(j=start;j<=end-1;j=j+2)
{
if(a[j]<=pivote){
swap(&a[i],&a[j]);
i=i+2;
}
}
swap(&a[i],&a[end]);
}
else{
int pivote = a[end];
for(j=start;j<=end-1;j=j+2)
{
if(a[j]>=pivote){
swap(&a[i],&a[j]);
i=i+2;
}
}
swap(&a[i],&a[end]);
}
return i;
}
void quicksort(int a[],int s,int e,int flag){
if(s>e){
return;
}
int p= partition(a,s,e,flag);
quicksort(a,s,p-2,flag);
quicksort(a,p+2,e,flag);
}
int main(){
int a[] = {3, 6, 7, 8, 1, 4, 2, 4, 6, 8};
int n = sizeof(a) / sizeof(int);
int i=0;
if(n%2!=0){
quicksort(a, 0, n-1,true);
quicksort(a, 1, n-2,false);
}
else{
quicksort(a, 0, n-2,true);
quicksort(a, 1, n-1,false);
}
for(i=0;i<n;i++){
printf("   %d  ",a[i]);
}
getch();
return 0;
}``````

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

We can modify the existing sorting algorithm to do so. I have changes the insertion sort.
Worst case Complexity : O(n^2)
Sample code is in Java.

``````package handson;

public class InsertionSort{
public static void main(String a[]){
int i;
int array[] = {12,9,4,99,120,1,3,10};
System.out.println(" Selection Sort\n\n");
System.out.println("Values Before the sort:");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+"  ");
System.out.println();
insertion_srtEven(array, array.length);
insertion_srtOdd(array, array.length);
System.out.print("Values after the sort:\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+"  ");
System.out.println();
}

public static void insertion_srtOdd(int array[], int n){
for (int i = 2; i < n ; ){
int j = i;
int B = array[i];
while ((j > 0) && (array[j-2] < B)){
array[j] = array[j-2];
j=j-2;
}
array[j] = B;
i=i+2;
}
}

public static void insertion_srtEven(int array[], int n){
for (int i = 3; i < n ; ){
int j = i;
int B = array[i];
while ((j > 1) && (array[j-2] > B)){
array[j] = array[j-2];
j=j-2;
}
array[j] = B;
i=i+2;
}
}
}``````

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

1. you can unify insertion_srtEven and insertion_srtOdd into a single function which is better and easier for maintainment

2. the average time complexity of insert sort is also O(n^2) while the best average complexity of sorting is O(nlgn)

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

Yeah Agree...!!!!
1. I was also trying to modify merg sort to reduce the complexity to O(nlogn).

2. Another approcah if the temp storage is allowed then we can create two different arrays for odd and even positions and use merge sorting; then finally we can create a final sorted (as expected .. odd/even) array.
It will also execute using O(nlogn)+O(n) = O(nlogn)

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

I have written a quick sort version, the function signature is as the following
void QuickSort(int * a, int beg, int step, int end, bool bAsc).

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

Merge Sort version.

``````#include <iostream>
#include <cstdio>
using namespace std;

const int sz = 20;

void mergeEvenOdd(int st1, int en1, int st2, int en2, int arr[]) {
static int tmp[sz];
int ss1 = st1, ss2 = st2, idx = 0;

while(ss1 < en1 && ss2 < en2) {
if(arr[ss1] <= arr[ss2])  {
tmp[idx++] = arr[ss1];
ss1 += 2;
}
else {
tmp[idx++] = arr[ss2];
ss2 += 2;
}
}
while(ss1 < en1) {
tmp[idx++] = arr[ss1];
ss1 += 2;
}
while(ss2 < en2) {
tmp[idx++] = arr[ss2];
ss2 += 2;
}
idx = 0;
while(st1 < en2) {
arr[st1] = tmp[idx++];
st1 += 2;
}
}

void merge(int st1, int en1, int st2, int en2, int arr[]) {
int id1 = st1, id2 = st2;

//even
id1 += (id1 % 2 == 0 ? 0 : 1);
id2 += (id2 % 2 == 0 ? 0 : 1);
mergeEvenOdd(id1, en1, id2, en2, arr);

//odd
id1 = st1, id2 = st2;
id1 += (id1 % 2 == 1 ? 0 : 1);
id2 += (id2 % 2 == 1 ? 0 : 1);
mergeEvenOdd(id1, en1, id2, en2, arr);

}

// sorts range from st to (en-1)
void mergeSort(int st, int en, int arr[]) {
if(en - st <= 1)
return;
int mid = (st + en - 1)/2;
mergeSort(st, mid+1, arr);
mergeSort(mid+1, en, arr);

merge(st, mid+1, mid+1, en, arr);
}

int main()
{
int arr[sz];
for(int i = 0; i < sz; i++)
arr[i] = rand()%50;

cout << "Original array : ";
for(int idx = 0; idx < sz; idx++)
printf("%2d ", arr[idx]);
cout << endl;

mergeSort(0, sz, arr);	// sort function

cout << "Final array    : ";
for(int idx = 0; idx < sz; idx++)
printf("%2d ", arr[idx]);
cout << endl;

return 0;
}``````

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

``````#include<iostream>
#include<stdlib.h>

using namespace std;

typedef struct array {
int x;
int y;
}myarr;

void scan_arr(int *arr, int n) {
cout << "Enter array elements : \n";
for(int i=0;i<n;i++) {
cin >> arr[i];
}
}

void print_arr(int *arr, int n) {
cout << "Enter array elements : \n";
for(int i=0;i<n;i++) {
cout << arr[i] <<", ";
}
cout <<endl;
}

void bubble_sort_x(myarr *a, int n) {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(a[i].x < a[j].x) {
int tmp = a[i].x;
a[i].x=a[j].x;
a[j].x=tmp;
}
}
}
}

void bubble_sort_y(myarr *a, int n) {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(a[i].y > a[j].y) {
int tmp = a[i].y;
a[i].y=a[j].y;
a[j].y=tmp;
}
}
}
}

void sort_even_odd(int *arr, int n) {
myarr *a = (myarr *)arr;
bubble_sort_x(a, n);
bubble_sort_y(a, n);
}

int main(void) {
int n;
int *arr;
cout << "Enter size of array : ";
do {
cin >> n;
}while (n <= 0);

arr = (int *)malloc(n * sizeof(int));

scan_arr(arr, n);

print_arr(arr, n);

sort_even_odd(arr, n/2);

print_arr(arr, n);

free(arr);

return 0;
}``````

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

Here is the modified bubble sort version implemented in C++

``````#include <iostream>
using namespace std;

void swap(int &x, int&y )
{
int temp = x;
x = y;
y = temp;
}

void even_odd_sort(int array[], int size)
{
int i, j;

for( i = 0; i < size - 1; i++ )
{
for(j = 0 ; j < size-2 ; j++ )
{
if( j%2 == 0 )
{
if( array[j] > array[j+2] )
swap( array[j], array[j+2] );
}
else
{
if( array[j] < array[j+2] )
swap( array[j], array[j+2] );
}
}
}
}

void printArray(int array[], int size)
{
for(int i = 0; i < size ; i++ )
{
cout<<array[i]<<" ";
}
cout<<endl;
}

int main()
{
int array[] = {4, 3, 2, 9, 0, 1, 5, 8, 6, 7};
//output should be 0  9   2  8  4  7  5  3  6 1
even_odd_sort(array,10);
printArray(array,10);
return 0;
}``````

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

Quick Sort Version:

``````public class Old_Even_Sort {
public static void main(String[] args) {
int[] arr = {9,10,8,9,7,8,6,7,5,6,4,5};
quickSort(arr, 1, arr.length-1);
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}

public static void quickSort(int[] arr, int start, int end) {
if(start < end) {
int x = partition(arr,start,end);
quickSort(arr, start, x-1);
quickSort(arr, x+1, end);
}
}

public static int partition(int[] arr, int start, int end) {
int x = arr[start];
int i = start;
int j = start + 2;
while(j<arr.length) {
if(start % 2 ==0) {
if(arr[j] < x) {
int temp = arr[i+2];
arr[i+2] = arr[j];
arr[j] = temp;
i = i+2;
}
j = j+2;
}else {
if(arr[j] > x) {
int temp = arr[i+2];
arr[i+2] = arr[j];
arr[j] = temp;
i = i+2;
}
j = j+2;
}

}
arr[start] = arr[i]	;
arr[i] = x;
return i;
}
}``````

output: [4, 10, 5, 9, 6, 8, 7, 7, 8, 6, 9, 5]

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

I took the challenge here as being able to do a generic sort in place. The qsort() function doesn't need to know anything about the indexing scheme; it works using get_elem() and put_elem() passed in.

``````def qsort(get_elem, put_elem, lo, hi, reverse):
def partition(lo, hi):
pivot = get_elem(hi)
i = lo
mid = lo
for i in range(lo, hi):
less_than = get_elem(i) <= pivot
if reverse:
less_than = not less_than
if less_than:
if mid < i:
tmp = get_elem(i)
put_elem(i, get_elem(mid))
put_elem(mid, tmp)
mid += 1
if mid < hi:
tmp = get_elem(mid)
put_elem(mid, get_elem(hi))
put_elem(hi, tmp)
return mid
def _sort(lo, hi):
if lo >= hi:
return
mid = partition(lo, hi)
_sort(lo, mid - 1)
_sort(mid + 1, hi)
_sort(lo, hi)

def even_odd_sort(lst):
def get_even_elem(i):
return lst[i*2]
def put_even_elem(i, v):
lst[i*2] = v
def get_odd_elem(i):
return lst[i*2+1]
def put_odd_elem(i, v):
lst[i*2 + 1] = v
qsort(get_even_elem, put_even_elem, 0, (len(lst)-1) / 2, False)
qsort(get_odd_elem, put_odd_elem, 0, len(lst) / 2 - 1, True)

lst = [4, 1, 2, 3, 0, 5, 6, 7]
even_odd_sort(lst)
print lst``````

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

Using priority queues: O(nlogn)

``````public static void sortOddEvenPositions(int[] input){
int[] output = new int[input.length];
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
for(int i = 0; i < input.length; i = i + 2){
}

for(int i = 0; i < input.length; i = i + 2){
output[i] = queue.remove();
}

for(int i = 1; i < input.length; i = i + 2){
}

for(int i = 0; i < input.length; i = i + 2){
output[i] = queue.remove();
}

System.out.println("SEcond result");
for(int n : input){
System.out.print(n +" ");
}
System.out.println();
}``````

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

``````void Sort15444945(std::string& a, int left, int right, bool ascOrder)
{
if (left >= right)
return;

char x = a[left];

int p = left;
int q = right;
while (p <= q)
{
while (ascOrder ? a[p] < x : a[p] > x)
{
p += 2;
}
while (ascOrder ? a[q] > x : a[q] < x)
{
q -= 2;
}

if (p <= q)
{
std::swap(a[p], a[q]);
p += 2;
q -= 2;
}
}

Sort15444945(a, left, q, ascOrder);
Sort15444945(a, p, right, ascOrder);
}

void Sort15444945(std::string& a)
{
if (a.size() % 2)
{
Sort15444945(a, 0, a.size() - 1, true);
Sort15444945(a, 1, a.size() - 2, false);
}
else
{
Sort15444945(a, 0, a.size() - 2, true);
Sort15444945(a, 1, a.size() - 1, false);
}
}``````

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

We can also perform selection sort on even and odd positions.

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

#include <iostream>

using namespace std;

void sort_array(int *a,int start_point,int len,bool sort_type)
{
for(int i=start_point;i<len; i=i+2)
{
for(int j=i;j<len;j=j+2)
{
if ( (sort_type == true) && a[i] > a[j])
{
int temp = a[j];
a[j]= a[i];
a[i] = temp;
}
if ( (sort_type == false) && (a[i] < a[j]))
{
int temp = a[j];
a[j]= a[i];
a[i] = temp;
}
}
}
}

void sort_even(int *i_array,int len)
{
sort_array(i_array,0,len,true);
}
void sort_odd(int *i_array,int len)
{
sort_array(i_array,1,len,false);

}
void display_array(int *a,int len)
{
for(int i=0;i < len; i++)
{
cout << a[i] << endl;
}
}

int main()
{

int int_array[]={70,20,40,30,50,60,10,80};
display_array(int_array,8);
sort_even(int_array,8);
sort_odd(int_array,8);
cout << "Sorted Array!" << endl;
display_array(int_array,8);
return 0;
}

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

Simple C# solution

``````private static void arraySorter(int[] A)
{
for (int j = 0; j < A.Length; j++)
{
for (int i = 1; i < A.Length - 1; i += 2)
{
if (i + 2 <= A.Length - 1)
{
if (A[i] < A[i + 2])
{
swap(ref A, i, i + 2);
}
}
}
}
for (int j = 0; j < A.Length; j++)
{
for (int i = 0; i < A.Length; i += 2)
{
if (i + 2 <= A.Length)
{
if (A[i] > A[i + 2])
{
swap(ref A, i, i + 2);
}
}
}
}
}

private static void swap(ref int[] A, int i, int j)
{
int f = A[i];
A[i] = A[j];
A[j] = f;
}``````

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

In this way, all your elements will be positive, which may violate the input

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

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

what if we want to maintain the order i e odd elements at odd position ... :O))

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.