Amazon Interview Question Software Engineer / Developers
Team: Kindle
Country: India
Interview Type: In-Person
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)
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 ?.
swap - take two pointers (firstOdd, LastOdd)
whie(firstOdd < lastOdd){
swap(a[fistOdd],a[LastOdd]
firstOdd+2;
LastOdd-2;
}
@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...
#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;
}
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;
}
}
}
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)
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)
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;
}
#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;
}
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;
}
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]
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
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){
queue.add(input[i]);
}
for(int i = 0; i < input.length; i = i + 2){
output[i] = queue.remove();
}
for(int i = 1; i < input.length; i = i + 2){
queue.add(input[i]);
}
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();
}
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);
}
}
#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;
}
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;
}
a quick sort version
- speedmancs February 17, 2013#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; }