Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
I didn't initially see this but do now and agree with you. A generalized swap can be implemented using at most two reverse operations as you suggest (one if distance < 3). So O(1) best case and worst 2 * O(1) per swap.
If we presume a more general swap based on O(1) read and write operations it would seem that swap is always 4 * O(1) + a temporary variable needed to cache the first read. So swap based on reverse will definitely save time and space (presuming that it's really O(1) via dedicated hardware for example).
Interesting question if there are sort algorithms specifically optimized to take advantage of O(1) reverse. I don't know the answer (using this question to re-familiarize myself w/details of sort algorithms as I've gotten lazy and generally re-use other people's libraries these days).
This is a version of Pan-Cake sorting where we are allowed to reverse the array from i to j.
1. Find the minimum element say its index is j.
2. reverse(i,j) where i represents how many elements have sorted till now starting from 0 to N-1. So, the minimum element will come to its position.
3. Increment i. Again find the minimum element from i to N-1.
4. Repeat above steps until i is not equal to N-1.
Here is the complete code.
#include <stdio.h>
void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
void reverse(int *arr,int l,int h)
{
while(l<h)
{
swap(&arr[l],&arr[h]);
l++;h--;
}
}
int findMin(int *arr,int l,int h)
{
int min=0,i;
for(i=l+1;i<h;i++)
if(arr[i]<arr[min])
min=i;
return min;
}
void sort(int *arr,int N)
{
int i,j;
for(i=0;i<N;i++)
{
j=findMin(arr,i,N);
reverse(arr,i,j);
}
for(i=0;i<N;i++)
printf("%d ",arr[i]);
}
int main()
{
int arr[]={2,1,5,4,6},size;
size=sizeof(arr)/sizeof(arr[0]);
sort(arr,size);
return 0;
}
According to question we can assume that get() and reverse will be done in O(1).
now we need to only do sorting using these two operations.
If the get() & reverse is O(1), then the sorting reduces to O(N).
No, pan cake is different from insertion sorting.
In insertion sorting, an element is inserted at proper place while it is comparing with every other element. Here elements are inserted at their proper place usin reverse() method.
It can't be o(n) you are running 2 loops one to iterate all element and another to find min.
@shondik: the solution proposed by you is selection sort. And the time complexity will not be O(N) as suggested by you as you are finding min N-1 times. To find min, you need to iterate over the (remaining) array which makes the time complexity O(N^2). Insertion sort performs better than selection (pan cake) sort in case of partially or completely sorted array.
Here's what I came up with:
Algorithm overview:
Each element in the array is examined in turn from left to right (excluding the last element).
Upon examination of the nth element value, all the values that appear to its right are examined left to right (including the last element). This can be thought of as an outer and inner loop with the outer loop element index denoted 'o' and the inner loop index denoted 'i'. Note that o < i by definition.
If get(o) > get(i) then reverse(o, i).
Consider simple input array {2,1}:
Outer loop iterates from 0 to 0, inner loop iterates from 1 to 1
get(o==0) > get(i==1) --> reverse(0,1) --> {1,2} done
Consider input array {3,2,1,0}:
Outer loop iterates from 0 to 2, inner loop iterates from n+1 to 3.
o=0, i=1 :: {2,3,1,0} <= reversed [0,1]
o=0, i=2 :: {1,3,2,0} <= reversed [0,2]
o=0, i=3 :: {0,2,3,1} <= reversed [0,3] -- note that o=0 element is now sorted
o=1, i=2 :: {0,2,3,1} <= no reverse
o=1, i=3 :: {0,1,3,2} <= reverse [1,3] -- note that o=1 element is now sorted
o=2, i=3 :: {0,1,2,3} <= reverse [2,3] -- note that o=2 element is now sorted
also note that o=3 element doesn't need to be examined
CODE:
// C++ on WIndows
#include "stdafx.h"
#include <iostream>
#include <crtdbg.h>
using namespace std;
int input[] = {3,2,1,0};
int const array_size = ((sizeof(input) / sizeof(int)) - 1);
int total_gets = 0;
int total_reverses = 0;
// Per problem statement get is O(1)
int get(int index) {
total_gets++;
return input[index];
}
// Per problem statement reverse is O(1) (even though it's not here)
void reverse(int start, int end)
{
_ASSERT(end >= start);
_ASSERT(start >= 0);
_ASSERT(end <= array_size);
total_reverses++;
int loop_range = (end - start) / 2;
for (int i = 0 ; i <= loop_range ; i++)
{
int const index_start = start + i;
int const index_end = end - i;
int x = input[index_start];
input[index_start] = input[index_end];
input[index_end] = x;
}
}
void print_array()
{
cout << "{";
for (int i = 0 ; i <= array_size ; i++)
{
cout << input[i];
if (i != array_size)
cout << ", ";
}
cout << "}";
}
// Note that the outer loop is implemented via recursion
void sort(int & recursions, int start, int end)
{
recursions++;
int start_val = ::get(start);
// Inner loop
for (int x = start + 1 ; x <= end ; x++)
{
int x_val = ::get(x);
bool reverse_operation = false;
cout << recursions << " | " << start << " | " << x << " :: ";
if (start_val > x_val)
{
reverse_operation = true;
::reverse(start, x);
start_val = ::get(start);
}
print_array();
if (reverse_operation)
cout << " <-- reversed [" << start << ", " << x << "] (inclusive)" << endl;
else
cout << " <-- no reverse" << endl;
}
cout << endl;
if ((start + 1) < end)
::sort(recursions, start+1, end);
}
int _tmain(int argc, _TCHAR* argv[])
{
_ASSERT( ((sizeof(input) / sizeof(int)) - 1) == array_size );
cout << "INITIAL INPUT:" << endl;
print_array();
cout << endl << endl;
int recursions = 0;
sort(recursions, 0, array_size);
cout << "FINAL OUTPUT:" << endl;
print_array();
cout << endl << endl;
cout << "Array elements == " << (array_size + 1) << endl;
cout << "Total get operations == " << total_gets << endl;
cout << "Total reverse operations == " << total_reverses << endl;
int const total_o1_ops = total_gets + total_reverses;
cout << "Total O(1) operations == " << total_o1_ops << endl;
cout << "Total elements squared == " << (array_size + 1) * (array_size+1) << endl;
cout << "Total recursive invocations of sort == " << recursions << endl;
return 0;
}
Given input array:
int input[] = {96, 5, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47};
Program output is:
INITIAL INPUT:
{96, 5, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47}
1 | 0 | 1 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [0, 1] (inclusive)
1 | 0 | 2 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 3 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 4 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 5 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 6 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 7 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 8 :: {3, 23, 19, 7, 2001, 5000, 10, 96, 5, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [0, 8] (inclusive)
1 | 0 | 9 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [0, 9] (inclusive)
1 | 0 | 10 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 11 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 12 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 13 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 14 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 15 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 16 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 17 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 18 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 2 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 3 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 4 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 5 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 6 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 7 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 8 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 9 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [1, 9] (inclusive)
2 | 1 | 10 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 11 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 12 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 13 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 14 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 15 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 16 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 17 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 18 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 3 :: {2, 3, 19, 23, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [2, 3] (inclusive)
3 | 2 | 4 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [2, 4] (inclusive)
3 | 2 | 5 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 6 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 7 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 8 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 9 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [2, 9] (inclusive)
3 | 2 | 10 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 11 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 12 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 13 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 14 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 15 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 16 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 17 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 18 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 4 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [3, 4] (inclusive)
4 | 3 | 5 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 6 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 7 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 8 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 9 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [3, 9] (inclusive)
4 | 3 | 10 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 11 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 12 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 13 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 14 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 15 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 16 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 17 :: {2, 3, 5, 6, 2012, 91, 79, 77, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [3, 17] (inclusive)
4 | 3 | 18 :: {2, 3, 5, 6, 2012, 91, 79, 77, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 5 :: {2, 3, 5, 6, 91, 2012, 79, 77, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 5] (inclusive)
5 | 4 | 6 :: {2, 3, 5, 6, 79, 2012, 91, 77, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 6] (inclusive)
5 | 4 | 7 :: {2, 3, 5, 6, 77, 91, 2012, 79, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 7] (inclusive)
5 | 4 | 8 :: {2, 3, 5, 6, 77, 91, 2012, 79, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 9 :: {2, 3, 5, 6, 11, 32001, 79, 2012, 91, 77, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 9] (inclusive)
5 | 4 | 10 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 10] (inclusive)
5 | 4 | 11 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 12 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 13 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 14 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 15 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 16 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 17 :: {2, 3, 5, 6, 7, 23, 19, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- reversed [4, 17] (inclusive)
5 | 4 | 18 :: {2, 3, 5, 6, 7, 23, 19, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 6 :: {2, 3, 5, 6, 7, 19, 23, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- reversed [5, 6] (inclusive)
6 | 5 | 7 :: {2, 3, 5, 6, 7, 19, 23, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 8 :: {2, 3, 5, 6, 7, 19, 23, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 9 :: {2, 3, 5, 6, 7, 19, 23, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 10 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- reversed [5, 10] (inclusive)
6 | 5 | 11 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 12 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 13 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 14 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 15 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 16 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 17 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- reversed [5, 17] (inclusive)
6 | 5 | 18 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 7 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 8 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 9 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 10 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 11 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- reversed [6, 11] (inclusive)
7 | 6 | 12 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 13 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 14 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 15 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 16 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 17 :: {2, 3, 5, 6, 7, 9, 10, 96, 5000, 2001, 23, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- reversed [6, 17] (inclusive)
7 | 6 | 18 :: {2, 3, 5, 6, 7, 9, 10, 96, 5000, 2001, 23, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 8 :: {2, 3, 5, 6, 7, 9, 10, 96, 5000, 2001, 23, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 9 :: {2, 3, 5, 6, 7, 9, 10, 96, 5000, 2001, 23, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 10 :: {2, 3, 5, 6, 7, 9, 10, 23, 2001, 5000, 96, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- reversed [7, 10] (inclusive)
8 | 7 | 11 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- reversed [7, 11] (inclusive)
8 | 7 | 12 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 13 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 14 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 15 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 16 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 32001, 79, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- reversed [7, 17] (inclusive)
8 | 7 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 32001, 79, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 9 :: {2, 3, 5, 6, 7, 9, 10, 11, 79, 32001, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- reversed [8, 9] (inclusive)
9 | 8 | 10 :: {2, 3, 5, 6, 7, 9, 10, 11, 79, 32001, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 11 :: {2, 3, 5, 6, 7, 9, 10, 11, 79, 32001, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 12 :: {2, 3, 5, 6, 7, 9, 10, 11, 77, 91, 2012, 32001, 79, 23, 2001, 5000, 96, 19, 47} <-- reversed [8, 12] (inclusive)
9 | 8 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 23, 79, 32001, 2012, 91, 77, 2001, 5000, 96, 19, 47} <-- reversed [8, 13] (inclusive)
9 | 8 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 23, 79, 32001, 2012, 91, 77, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 23, 79, 32001, 2012, 91, 77, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 23, 79, 32001, 2012, 91, 77, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 96, 5000, 2001, 77, 91, 2012, 32001, 79, 23, 47} <-- reversed [8, 17] (inclusive)
9 | 8 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 96, 5000, 2001, 77, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 10 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 96, 5000, 2001, 77, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 11 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 96, 5000, 2001, 77, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 12 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- reversed [9, 12] (inclusive)
10 | 9 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- reversed [9, 17] (inclusive)
10 | 9 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 11 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 12 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 47} <-- reversed [10, 17] (inclusive)
11 | 10 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- reversed [10, 18] (inclusive)
12 | 11 | 12 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 2001, 5000, 96, 91, 2012, 32001, 79} <-- reversed [11, 18] (inclusive)
13 | 12 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 2001, 5000, 96, 91, 2012, 32001, 79} <-- no reverse
13 | 12 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 96, 5000, 2001, 91, 2012, 32001, 79} <-- reversed [12, 14] (inclusive)
13 | 12 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 91, 2001, 5000, 96, 2012, 32001, 79} <-- reversed [12, 15] (inclusive)
13 | 12 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 91, 2001, 5000, 96, 2012, 32001, 79} <-- no reverse
13 | 12 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 91, 2001, 5000, 96, 2012, 32001, 79} <-- no reverse
13 | 12 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 32001, 2012, 96, 5000, 2001, 91} <-- reversed [12, 18] (inclusive)
14 | 13 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 2012, 32001, 96, 5000, 2001, 91} <-- reversed [13, 14] (inclusive)
14 | 13 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 96, 32001, 2012, 5000, 2001, 91} <-- reversed [13, 15] (inclusive)
14 | 13 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 96, 32001, 2012, 5000, 2001, 91} <-- no reverse
14 | 13 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 96, 32001, 2012, 5000, 2001, 91} <-- no reverse
14 | 13 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 2001, 5000, 2012, 32001, 96} <-- reversed [13, 18] (inclusive)
15 | 14 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 2001, 5000, 2012, 32001, 96} <-- no reverse
15 | 14 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 2001, 5000, 2012, 32001, 96} <-- no reverse
15 | 14 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 2001, 5000, 2012, 32001, 96} <-- no reverse
15 | 14 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 32001, 2012, 5000, 2001} <-- reversed [14, 18] (inclusive)
16 | 15 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2012, 32001, 5000, 2001} <-- reversed [15, 16] (inclusive)
16 | 15 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2012, 32001, 5000, 2001} <-- no reverse
16 | 15 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 5000, 32001, 2012} <-- reversed [15, 18] (inclusive)
17 | 16 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 5000, 32001, 2012} <-- no reverse
17 | 16 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 2012, 32001, 5000} <-- reversed [16, 18] (inclusive)
18 | 17 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 2012, 5000, 32001} <-- reversed [17, 18] (inclusive)
FINAL OUTPUT:
{2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 2012, 5000, 32001}
Array elements == 19
Total get operations == 233
Total reverse operations == 44
Total O(1) operations == 277
Total elements squared == 361
Total recursive invocations of sort == 18
---
Space for the algorithm (I think) is O(N) (one stack frame per element approximately)
Time for the algorithm is (I think) is O(N^2)
I assume that the setup is similar to below and we can use only get() and reverse(),which will operate in O(1) time (just assume).
class ExternalArray
{
private int [] arr;
public ExternalArray(int [] A)
{
arr=A;
}
public void get(int i)
{
//some code here
}
public void reverse(int i, int j)
{
//some code here
}
}
I think quick sort using the reverse(i,j) could still work out better than the O(n^2) with the pan-cake algorithm although it seems a lot more intuitive to use the latter.
Using a variation of quicksort with the reverse(i,j) instead of the swap would still quarantee nlogn.
I'll need to think about this suggestion some more. reverse(x,y) is a swap of x and y only then (y-x) < 3 so initial thinking was that any sort that depends on a true swap(x,y) would get kind of complicated. maybe I missed something. Do you agree with my space/time estimates BTW?
I woke up agreeing with you: it's trivial to implement swap(x,y) using reverse. In the trivial case (distance = 1 or 2) a single reverse suffices. In the general case (distance > 2) two reverse operations suffices. Given this, implementing quicksort is straight forward.
I note that another poster already posted this observation below. Also suspect this is what you were implying in your original comment.
Good question.
The optimize code for reversing the array between specific start and end location will be :
void reverseArray(int *iArr,int startLoc,int endLoc)
{
int *ptr1=iArr+startLoc;
int *ptr2=iArr+endLoc;
int temp;
while(ptr1 != ptr2 && ptr1<ptr2)
{
temp=*ptr1;
*ptr1=*ptr2;
*ptr2=temp;
ptr1++;
ptr2--;
}
T
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[]={1,2,3,4,5,6,7};
int size= sizeof(arr)/sizeof(arr[0]);
reverseArray(arr,1,6);
return 0;
}
The time complexity for the algo would be less than O(n)
the question doesn't ask for an implementation of reverse but rather a sorting algorithm based on get and reverse (both O(1) per problem statement).
Hi,
The name "reverseArray" in my programe can be replaced by reverse(). it is although the same thing. Yes, i do agree about the use of get() function. I think we can use the get() function to get the starting index and the endIndex for reversing the values. That will be easy and can be done in O(1).
class Utile{
public void reverse(arr,int low,int high){
}
public int get(i){
}
}
class main{
Sortarray(int arr[]){
for(int i=0;i<arr.lenght;i++){
int min = arr[i];
int minpos=i;
for(int j=i;j<arr.length;j++){
if(arr[j] < min ) {
min = arr[j];
minpos=j;
}
}
utils.reverse(arr,i,j);
}
}
}
it will be O(n^2)
Quick sort solution:
int GetPilot(ExternalArray& array, int start, int end) // both start and end are inclusive
{
int pilot = start;
for(int i = start + 1, i <= end; ++i)
{
if(array.get(i) < array.get(start))
{
++pilot;
array.reverse(pilot, i);
}
}
array.reverse(start, pilot);
return pilot;
}
void QuickSort(ExternalArray& array, int start, int end) // both start and end are inclusive
{
if(start >= end) return;
int pilot = GetPilot(array, start, end);
QuickSort(array, start, pilot-1);
QuickSort(array, pilot + 1, end);
}
void Sort(ExternalArray& array, int len)
{
QuickSort(array, 0, len - 1);
}
Time: O(nlogn)
Space: O(n)
You could create a general swap by using reverse(i,j) to swap any i and j and then reverse(i+1,j-1) to reverse all the in-between elements back into place.
- thirdderivative June 26, 2012This swap's time complexity would be O(1) + O(1) = O(1).
Now you can use quicksort, which generally runs in n log n (worst case n^2). What I wonder is if there are any sort algorithms specific to this problem that run in less than n log n (or even O(n log n)), by taking advantage of the full power of the reverse() function.