Microsoft Interview Question: Should able to write code of ... | Glassdoor

Interview Question

Software Development Engineer In Test (SDET) II Interview Mountain View, CA

Should able to write code of Quick Sort in limited time.

Answer

Interview Answer

1 Answer

0

/* sort a[low]...v[high] into increasing order
   80 15 30 60 55 65 40 35 45 70 =>
   15 30 35 40 45 55 60 65 70 80
 */
void Swap(int a[], int low, int high)
{
    int t = *(a+low);
    *(a+low) = *(a+high);
    *(a+high) = t;
}

void QuickSort(int a[], int low, int high)
{
    if (low >= high)
        return;

    if (low+1 == high)
    {
        if (a[low] > a[high])
            Swap(a, low, high);
        else
            return;
    }

    int mid = (low+high)/2;
    int pivot = a[mid];

    Swap(a, low, mid);

    // Pointers to scan from the left and right
    int left = low+1;
    int right = high;

    do
    {
        while (a[left] pivot)
            --right;
        if (left < right)
            Swap(a, left, right);
    } while (left < right);

    Swap(a, low, right);

    QuickSort(a, low, right-1);
    QuickSort(a, right+1, high);
}

Peter on Jul 21, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.