Microsoft

  www.microsoft.com
Work in HR? Unlock Free Profile

Microsoft Software Development Engineer In Test (SDET) II Interview Question

I interviewed in Mountain View, CA and was asked:
"Should able to write code of Quick Sort in limited time."
Add Tags [?]
Answer

Part of a Software Development Engineer In Test (SDET) II Interview Review - one of 3,371 Microsoft Interview Reviews

Answers & Comments

0
of 0
votes
/* 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 && left <= right)
            ++left;
        while (a[right] > 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

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.