CareerCup

hey arun
Is it the question of amazon online exam. I got the same question.
R u able to solve. ?

Probably not, since no one has solved the pancake sorting problem: http :// en.wikipedia.org / wiki / Pancake_sorting

Simple Bubble sort or shell sort.

Yeah..simple bubble sort,since in bubble sort we swap only consecutive elements, so that can be done using reverse(i,i+1);

or what abt selection sort

- bubble sort
- selection sort
- insertion sort

One example:

void insertionSort(int[] arr){
for( int i = 1; i < arr.length; i++ ){
int index = i;
for( int j = i-1; j >= 0; j-- ){
if( arr[j] > arr[index] ){
reverse(arr, j, index);
index = j;
}
}
}
}

yeah it can be done by bubble sort reverse(i,i+1)
But we are not making use of reversing entire sub array.
We just swapping ...
I think there exists a better algo..

Quicksort maybe also used:

void quicksort(int[] arr, int from, int to){

if( to -from < 2 ){
return;
}

int i = -1;
int j = 0;

int pivotElement = arr[to];

for(int k = 0; k < to; k++){
if(arr[k] <= pivotElement ){
reverse(arr, i+1, j);
++i;
}
++j;
}

reverse(arr, i+1, to);

quicksort(arr, from, i);
quicksort(arr, i+2, to);
}

Sorry error:
if( to -from < 2 ){
return;
}

Fixed:

if( from >= to ){
return;
}

Vector is a wrapper to std::vector with length(), get(i), and reverse(i,j)

#include <vector>
template <typename T>
class Vector
{
public:
    Vector(T t[], unsigned int n) {
        for(unsigned int i = 0; i < n; i++) {
            v.push_back(t[i]);
        }
    }
    size_t length() {
        return v.size();
    }
    T get(unsigned int i) {
        if (i >= length())
            std::__throw_out_of_range;
        return v[i];
    }
    void reverse(unsigned int i, unsigned int j) {
        if (i == j)
            return;
        v[i] = get(i) ^ get(j);
        v[j] = get(i) ^ get(j);
        v[i] = get(i) ^ get(j);
    }
protected:
    std::vector<T>v;
};
void quicksort(Vector<int>&v, unsigned int left = 0, unsigned int right = 0)
{
    if (right == 0 || right >= v.length() - 1)
        right = v.length() - 1;
    int pivot = v.get(right);
    unsigned int j = left;
    for (unsigned int i = left; i <= right - 1; i++) {
        if (v.get(i) < pivot)
            v.reverse(i, j++);
    }
    v.reverse(j, right);
    if (left < j - 1)
        quicksort(v, left, j - 1);
    if (j + 1 < right)
        quicksort(v, j + 1, right);
}

int main()
{
    int a[] = {9, 27, 35, -8, 7, -3, 4, 12};
    Vector<int>v(a, sizeof(a) / sizeof(a[0]));
    quicksort(v);
    for(unsigned int i = 0; i < v.length(); i++)
        printf("%d ", v.get(i));
    printf("\n");
}

Output:
-8 -3 4 7 9 12 27 35

@varun Yes , it was asked in amazon online test.

Looks like merge sort is the most efficient solution for this problem.

quich sort with single index .... see keringhan ...

Hi... Can i have the gmail id's of varun and arun... Guys.. I am also looking for the Job in Amazon.. But i am preparing rite now.. Please can i discuss with you some of your experiences about the tests @ amason.....

How to appear for online test @ Amazon??

There is a O(n) algorithm for this particular problem.
Hint:

"The system exposes 3 functions of O(1)"
and one of them is reverse(i,j) - reverses the elements in the array from index i to index j (both indexes

doing reverse(i,j) in O(1) is impossible in real world, but nevertheless this hypothetical system gives you this power, use it.

@wizard: O(n)..???

Think of insertion sort. Assume that 1 to k is sorted. Consider x the number at k+1. Using binary search find the location p where the x has to be inserted. then to insert x perform reverse(p,k+1) and reverse(p+1,k+1). Now the array 1 to k+1 is sorted. This is worst case nlog(n).

k=0;
while(k <length(arr))
{
for(i=1;i<length(arr);i++)
{
if(getindex(a[k])>getindex(a[i+1]))
{
reverse(a[i],a[i+1])
}
}
k++
}

all functions used ...

<pre lang="" line="1" title="CodeMonkey50466" class="run-this">void
sort () {
int i, j, m, n, L;

L = length ()

for (i = 1; i < L; i++) {
m = get (i - 1)
n = get (i)
k = i

while (m > n) {
reverse (k - 1, k)
k = k - 1;
if (k == 0)
break;
m = get (k - 1)
n = get (k)
}
}
}</pre>

Use quicksort...

Bubble sort?

I'm not sure you may implement quick sort. Bublesort is doable.

yes! i implemented bubble sort in during the test. I could not think of an O(nlogn) solution for this or better.

Same as Question id 7935667

No need to use reverse two times in quick sort. Just use the middle element as the pivot for quick sort. Implementation code

public void quickSort(List<Integer> array) {
int pivot = array.get(array.size() / 2);
int left = 0, right = array.size() - 1;
while (left < right) {
while (array.get(left) < pivot) {
left++;
}

while (array.get(right) > pivot) {
right--;
}

reverse(array, left, right);
/*if (left < right) {
int temp = array.get(left);
array.set(left, array.get(right));
array.set(right, temp);
}*/
}

if (left > 0) {
quickSort(array.subList(0, left));
}

if (right < array.size() - 1) {
quickSort(array.subList(right + 1, array.size()));
}
}

<pre lang="" line="1" title="CodeMonkey93594" class="run-this">public void quickSort(List<Integer> array) {
int pivot = array.get(array.size() / 2);
int left = 0, right = array.size() - 1;
while (left < right) {
while (array.get(left) < pivot) {
left++;
}

while (array.get(right) > pivot) {
right--;
}

reverse(array, left, right);
/*if (left < right) {
int temp = array.get(left);
array.set(left, array.get(right));
array.set(right, temp);
}*/
}

if (left > 0) {
quickSort(array.subList(0, left));
}

if (right < array.size() - 1) {
quickSort(array.subList(right + 1, array.size()));
}
}</pre><pre title="CodeMonkey93594" input="yes">
</pre>