Saturday, November 5, 2016

Hacker Rank - Quartiles

Problem:

Please find the problem here.

Solution: 

This time around I am challenging myself to implement Quick Select to find all order statistics I needed to compute the quartiles in one call.

The partitioning routine is based on my previous problem. The innovation in this version is that I can select multiple elements in the same call by arranging the target index in a sorted array.

Code:

#include "stdafx.h"

// https://www.hackerrank.com/challenges/s10-quartiles

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;

void select(vector<int>& nums, int start, int end, vector<int>& goals, int goalStart, int goalEnd, vector<int>& result)
{
    if (nums.size() == 1)
    {
        result.push_back(nums[0]);
        return;
    }

    int pivotIndex = rand() % (end - start) + start;
    swap(nums[start], nums[pivotIndex]);

    int pivot = nums[start];
    int left = start;
    int right = end;

    // Maintain these variables
    int smallerEnd = left;             // [left, smallerEnd) are strictly smaller than the pivot
    int smallerOrEqualEnd = left + 1;  // [smallerEnd, smallerOrEqualEnd) are smaller or equal to the pivot
    int largerBegin = right;           // [largerBegin, right) are strictly larger than the pivot

    while (true)
    {
        while (smallerOrEqualEnd < nums.size() && nums[smallerOrEqualEnd] <= pivot)
        {
            if (nums[smallerOrEqualEnd] < pivot)
            {
                swap(nums[smallerEnd], nums[smallerOrEqualEnd]);
                smallerEnd++;
            }

            smallerOrEqualEnd++;
        }

        while (largerBegin > 0 && nums[largerBegin - 1] > pivot)
        {
            largerBegin--;
        }

        if (smallerOrEqualEnd == largerBegin)
        {
            break;
        }

        // [left, smallerEnd) are strictly smaller than the pivot
        // [smallerEnd, smallerOrEqualEnd) are equal to the pivot
        // [largerBegin, right) are strictly larger than the pivot

        // nums[smallerEnd] = pivot
        // nums[smallerOrEqualEnd] > pivot
        // nums[largerBegin - 1] <= pivot
        if (nums[largerBegin - 1] == pivot)
        {
            swap(nums[smallerOrEqualEnd], nums[largerBegin - 1]);
            smallerOrEqualEnd++;
            largerBegin--;
        }
        else
        {
            nums[smallerEnd] = nums[largerBegin - 1];
            nums[largerBegin - 1] = nums[smallerOrEqualEnd];
            nums[smallerOrEqualEnd] = pivot;
            smallerEnd++;
            smallerOrEqualEnd++;
            largerBegin--;
        }
    }

    int leftGoalEnd = -1;
    int pivotCount = 0;
    int rightGoalStart = -1;

    for (int i = goalStart; i < goalEnd; i++)
    {
        int k = goals[i] - left;
        int smallPortionLength = smallerEnd - left;
        if (k < smallPortionLength)
        {
        }
        else
        {
            if (leftGoalEnd == -1)
            {
                leftGoalEnd = i;
            }
            k -= smallPortionLength;
            int pivotPortionLength = smallerOrEqualEnd - smallerEnd;
            if (k < pivotPortionLength)
            {
                pivotCount++;
            }
            else
            {
                k -= pivotPortionLength;
                if (rightGoalStart == -1)
                {
                    rightGoalStart = i;
                    break;
                }
            }
        }
    }
    if (leftGoalEnd == -1)
    {
        leftGoalEnd = goalEnd;
    }

    if (leftGoalEnd > goalStart)
    {
        select(nums, left, smallerEnd, goals, goalStart, leftGoalEnd, result);
    }
    for (int i = 0; i < pivotCount; i++)
    {
        result.push_back(pivot);
    }
    if (rightGoalStart != -1)
    {
        select(nums, smallerOrEqualEnd, right, goals, rightGoalStart, goalEnd, result);
    }
}

int HACKER_RANK_S10_QUARTILES()
{
    int n;
    cin >> n;
    vector<int> data;
    data.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> data[i];
    }
    vector<int> goals;
    vector<int> result;
    if (n % 4 == 3)
    {
        // [0, n/2) [n/2] [n/2 + 1, n)
        goals.push_back(n / 4);
        goals.push_back(n / 2);
        goals.push_back(n / 2 + 1 + n / 4);
        select(data, 0, n, goals, 0, goals.size(), result);
        cout << result[0] << endl;
        cout << result[1] << endl;
        cout << result[2] << endl;
    }
    else if (n % 4 == 2)
    {
        // [0, n/2) [n/2, n)
        goals.push_back(n / 4);
        goals.push_back(n / 2 - 1);
        goals.push_back(n / 2);
        goals.push_back(n / 2 + n / 4);
        select(data, 0, n, goals, 0, goals.size(), result);
        cout << result[0] << endl;
        cout << (result[1] + result[2]) / 2 << endl;
        cout << result[3] << endl;
    }
    else if (n % 4 == 1)
    {
        // [0, n/2) {n/2}, [n/2 + 1, n]
        goals.push_back(n / 4 - 1);
        goals.push_back(n / 4);
        goals.push_back(n / 2);
        goals.push_back(n / 2 + n / 4);
        goals.push_back(n / 2 + n / 4 + 1);
        select(data, 0, n, goals, 0, goals.size(), result);
        cout << (result[0] + result[1]) / 2 << endl;
        cout << result[2] << endl;
        cout << (result[3] + result[4]) / 2 << endl;
    }
    else if (n % 4 == 0)
    {
        // [0, n/2) [n/2, n]
        goals.push_back(n / 4 - 1);
        goals.push_back(n / 4);
        goals.push_back(n / 2 - 1);
        goals.push_back(n / 2);
        goals.push_back(n / 2 + n / 4 - 1);
        goals.push_back(n / 2 + n / 4);
        select(data, 0, n, goals, 0, goals.size(), result);
        cout << (result[0] + result[1]) / 2 << endl;
        cout << (result[2] + result[3]) / 2 << endl;
        cout << (result[4] + result[5]) / 2 << endl;
    }

    return 0;
}

No comments :

Post a Comment