HackerRank "Array Manipulation" challenge (using Microsoft concurrent extensions)

Question

I've been practising my coding skills because I have an interview coming up. The HackerRank challenge has 16 test cases; the code passes 9 of them and the other 7 time out.

If you go to HackerRank Problems Data Structures you might be able to find Array Manipulation under Hard problems. I can't seem to provide a direct link.

Using Microsoft specific parallel extensions in C++ I have gotten execution time for test case 4 down from hours down to 89 seconds when built for release. Test case 4 is one of the test cases that times out on Hacker Rank. I might be able to squeeze another couple of seconds out by using parallel processing in the merge function as well.

Things I don't like about my solution:

• It is totally brute force
• I can't seem to run parallel on HackerRank; maybe I need to try OpenMP.

I'm open to all answers and comments.

Program Challenge Statement

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

Example

Queries are interpreted as follows: a b k
1 5 3
4 8 7
6 9 1

Add the values of k between the indices a and b inclusive:

index-> 1 2 3 4 5 6 7 8 9 10
[0,0,0, 0, 0,0,0,0,0, 0]
[3,3,3, 3, 3,0,0,0,0, 0]
[3,3,3,10,10,7,7,7,0, 0]
[3,3,3,10,10,8,8,8,1, 0]

The largest value is 10 after all operations are performed.

Function Description
Complete the function arrayManipulation.

arrayManipulation has the following parameters:

• int n - the number of elements in the array
• int queries[q][3] - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.

Returns

• int - the maximum value in the resultant array

Constraints
- 3 < n < 10⁷
- 1 < m < 2 * 10⁵
- 1 < a < b < n
- 0 < k < 10⁹

Sample Input
5 3
1 2 100
2 5 100
3 4 100

Sample Output
200

Environment

Dell Precision 7740

Processor Intel(R) Core(TM) i7-9850H CPU @ 2.60GHz 2.59 GHz
Installed RAM 64.0 GB (63.8 GB usable)
System type 64-bit operating system, x64-based processor
Edition Windows 10 Pro Version 20H2
OS build 19042.1348

Visual Studio 2019.

Test Cases

Test Case 1

5
3
1 2 100
2 5 100
3 4 100

Test Case 2

10
3
1 5 3
4 8 7
6 9 1

Test Case 3

10
4
2 6 8
3 5 7
1 8 1
5 9 15

Test Case 4

This is the first 5 lines only, the complete test case is 100,002 lines. You can download the complete test case from my GitHub repository.

10000000
100000
1400906 9889280 90378
6581237 9872072 87106
4386373 9779851 52422

This test case really shows the scope of the problem, 100,000 outer loops, some inner loops with more the 7 million executions.

Test Output

PS C:\Users\PaulC\Documents\ProjectsNfwsi\CodeReview\HackerRankArrayManip\Release> HackerRankArrayManip.exe
How many test cases do you want to run?4
Test Case 1
Test Case 1 File read time 0.271 milliseconds
Test Case 1 result is 200 Execution time 2.0378 milliseconds

Test Case 2
Test Case 2 File read time 0.1541 milliseconds
Test Case 2 result is 10 Execution time 0.0132 milliseconds

Test Case 3
Test Case 3 File read time 0.1068 milliseconds
Test Case 3 result is 31 Execution time 0.0985 milliseconds

Test Case 4
Test Case 4 File read time 77.3068 milliseconds
Test Case 4 result is 2497169732 Execution time 89.1439 Seconds

PS C:\Users\PaulC\Documents\ProjectsNfwsi\CodeReview\HackerRankArrayManip\Release>

C++ Source File

#include <PPL.h>
#include<algorithm>
#include <chrono>
#include<execution>
#include <fstream>
#include <iostream>
#include <mutex>
#include <string>
#include <vector>

constexpr int MAX_TEST_CASE = 4;
/*
* Infrastructure to replace HackerRank input functions
*/
std::vector<int> convertInputLineToIntVector(std::string query_string)
{
    constexpr int query_size = 3;
    std::vector<int> query;

    std::string::iterator intStart = query_string.begin();
    std::string::iterator intEnd;

    for (int i = 0; i < query_size; i++)
    {
        intEnd = std::find(intStart, query_string.end(), ' ');
        int pos = intEnd - query_string.begin();
        std::string tempInt(intStart, intEnd);
        query.push_back(stoi(tempInt));
        if (intEnd < query_string.end())
        {
            intStart = query_string.begin() + pos + 1;
        }
    }

    return query;
}

std::vector<std::vector<int>> getIntVectors(std::ifstream* inFile)
{
    std::vector<std::vector<int>> inputVector;
    std::string string_vector_count;

    getline(*inFile, string_vector_count);

    int strings_count = stoi(string_vector_count);

    for (int i = 0; i < strings_count; i++) {
        std::string string_item;
        getline(*inFile, string_item);

        inputVector.push_back(convertInputLineToIntVector(string_item));
    }

    return inputVector;
}

int getInputLines(std::string inputFileName, int &vectorSize, std::vector<std::vector<int>>& queries)
{
    std::string string_count_size;
    std::ifstream inFile(inputFileName);

    if (!inFile.is_open())
    {
        std::cerr << "Can't open " << inputFileName << " for input.\n";
        std::cout << "Can't open " << inputFileName << " for input.\n";
        return EXIT_FAILURE;
    }

    getline(inFile, string_count_size);
    vectorSize = stoi(string_count_size);

    queries = getIntVectors(&inFile);

    return EXIT_SUCCESS;
}

void getTestCountAndFirstTestCase(int& testCount, int& firstTestCase)
{
    do {
        std::cout << "How many test cases do you want to run?";
        std::cin >> testCount;
        if (testCount < 0 || testCount > MAX_TEST_CASE)
        {
            std::cerr << "The number of test cases must be greater > 0 and less than " << " " << MAX_TEST_CASE << "\n";
        }
    } while (testCount < 0 || testCount > MAX_TEST_CASE);

    if (testCount < MAX_TEST_CASE)
    {
        bool hasErrors = true;
        do {
            std::cout << "What test case file do you want to start with?";
            std::cin >> firstTestCase;
            if (firstTestCase < 0 || firstTestCase > MAX_TEST_CASE)
            {
                std::cerr << "The first test cases must be greater > 0 and less than " << " " << MAX_TEST_CASE << "\n";
                hasErrors = true;
            }
            else
            {
                hasErrors = false;
            }
            if (!hasErrors && testCount + firstTestCase > MAX_TEST_CASE)
            {
                std::cerr << "The first test cases and the test count must be less than or equal to " << MAX_TEST_CASE << "\n";
                hasErrors = true;
            }
        } while (hasErrors);
    }
    else
    {
        firstTestCase = 1;
    }
}

/*
 * Begin HackerRank Solution
*/
constexpr int IDX_FIRST_LOCATION = 0;
constexpr int IDX_LAST_LOCATION = 1;
constexpr int IDX_VALUE_TO_ADD = 2;
constexpr int MAX_THREADS = 16;

unsigned long mergeAndFindMax(std::vector<unsigned long> maxValues, std::vector<std::vector<unsigned long>> calculatedValues, const size_t executionCount)
{
    unsigned long maximumValue = 0;

    for (size_t i = 0; i < MAX_THREADS; i++)
    {
        std::vector<unsigned long>::iterator cvi = calculatedValues[i].begin();
        std::vector<unsigned long>::iterator cvEnd = calculatedValues[i].end();
        std::vector<unsigned long>::iterator mvi = maxValues.begin();
        for ( ; mvi < maxValues.end() && cvi < cvEnd; mvi++, cvi++)
        {
            *mvi += *cvi;
            if (*mvi > maximumValue)
            {
                maximumValue = *mvi;
            }
        }
        if (i > executionCount)
        {
            break;
        }
    }

    return maximumValue;
}

unsigned long arrayManipulation(const int n, const std::vector<std::vector<int>> queries)
{
    std::vector<unsigned long> maximumValues(n, 0);
    std::vector<std::vector<unsigned long>> calculatedValues(MAX_THREADS);
    std::mutex m;
    for_each(calculatedValues.begin(), calculatedValues.end(), [maximumValues](std::vector<unsigned long>& cvi) {cvi = maximumValues; });
    int executionCount = 0;

    Concurrency::parallel_for_each(queries.begin(), queries.end(),
        [&m, &calculatedValues, &executionCount](std::vector<int> query)
        {
            std::lock_guard<std::mutex> guard(m);
            size_t startLoc = query[IDX_FIRST_LOCATION];
            size_t endLoc = query[IDX_LAST_LOCATION];
            const unsigned long valueToAdd = query[IDX_VALUE_TO_ADD];
            for_each(calculatedValues[executionCount % MAX_THREADS].begin() + (startLoc - 1),
                calculatedValues[executionCount % MAX_THREADS].begin() + endLoc,
                [valueToAdd](unsigned long& n) {n += valueToAdd; });
            executionCount++;
        });

    return mergeAndFindMax(maximumValues, calculatedValues, executionCount);
}

int executeAndTimeTestCases(int testCaseCount, int firstTestCase)
{
    using std::chrono::high_resolution_clock;
    using std::chrono::duration_cast;
    using std::chrono::duration;
    using std::chrono::milliseconds;

    for (int i = 0; i < testCaseCount; i++)
    {
        std::string testFileName = "TestCase" + std::to_string(firstTestCase) + ".txt";

        int n = 0;
        std::vector<std::vector<int>> queries;

        std::cout << "Test Case " << firstTestCase << "\n";

        auto fileReadStartTime = high_resolution_clock::now();
        int exitStatus = getInputLines(testFileName, n, queries);
        if (exitStatus != EXIT_SUCCESS)
        {
            return exitStatus;
        }
        auto fileReadEndTime = high_resolution_clock::now();
        duration<double, std::milli> msReadTime = fileReadEndTime - fileReadStartTime;
        std::cout << "Test Case " << firstTestCase << " File read time " << msReadTime.count() << " milliseconds\n";

        auto executionStartTime = high_resolution_clock::now();
        unsigned long result = arrayManipulation(n, queries);
        auto executionEndTime = high_resolution_clock::now();
        duration<double, std::milli> msExecution = executionEndTime - executionStartTime;

        if (msExecution.count() > 1000.0)
        {
            std::cout << "Test Case " << firstTestCase << " result is " << result << " Execution time " << msExecution.count() / 1000.0 << " Seconds\n\n";
        }
        else
        {
            std::cout << "Test Case " << firstTestCase << " result is " << result << " Execution time " << msExecution.count() << " milliseconds\n\n";
        }
        firstTestCase++;
    }

    return EXIT_SUCCESS;
}

int main()
{
    int testCaseCount = 0;
    int firstTestCase = 0;
    getTestCountAndFirstTestCase(testCaseCount, firstTestCase);

    return executeAndTimeTestCases(testCaseCount, firstTestCase);
}

Answer 1

Practicing for an interview you say?

constexpr int MAX_TEST_CASE = 4; You're off to a good start! Though you might use auto instead of int, or make it a size_t if it will be compared with vector lengths. Do you have warnings turned on? Signed/unsigned mismatch in comparison is a serious one to beware of.

std::vector<int> convertInputLineToIntVector(std::string query_string)
And now your first serious ding. Why are you passing a string by value? That is rare enough to be a code review issue and distracts reviewers even when there is a legitimate reason to do so. Passing by value is a telltale mistake of people coming from other languages that have reference semantics for objects, and is something the interviewer will immediately spot with concern. You're not familiar enough with C++ source code to think this looks weird.

You should use std::string_view to pass string things into functions. This gives you the best efficiency for passing either a std::string or a lexical string literal.

---

std::string::iterator intStart = query_string.begin();
std::string::iterator intEnd;

Declaring the full elaborated type of intStart is brutal, unnecessary, and gets in the way if the type of query_string changes. Try and write in a generic manner even if it's not a template -- that will help in maintenance, as changing the type of something is a very common change to make. You want any dependent things in the function to be worked out automatically. In short, use auto.

As for intEnd, why are you declaring it here, without any initializer? It should be declared where you actually use it, inside the loop.

    for (int i = 0; i < query_size; i++)
    {
        intEnd = std::find(intStart, query_string.end(), ' ');
        int pos = intEnd - query_string.begin();

vs.

    for (int i = 0; i < query_size; ++i)
    {
        const auto intEnd = std::find(intStart, query_string.end(), ' ');
        const auto pos = intEnd - query_string.begin();

Prefer prefix increment!
Define the variable where you initialize it. Use const as well.
Here, pos is not an int! Let auto figure out the difference_type between the iterators for you.

What you are doing here, it appears, is splitting the string. This should be a function call, not elaborated out into the middle of the main code. In real life you'll already have a reusable function for this. So call it something that's not so specific to this usage. Like, parse_csv_ints and take the number of fields to expect as a template argument.

Since the number of fields is known at compile-time, you can avoid the dynamic memory of a vector and use an array. My function is:

template <size_t N>
auto split (char separator, std::string_view input)
{
    std::array<std::string_view, N> results;
          ⋮        
    return results;
}

This doesn't do the conversion to int of each field; it just separates them out (including whitespace). The caller allocates the fixed-size array on its stack, and the result is populated as pointers into the original input so does not copy any string data at all.

This is a more reusable core that can have any type of data reading adding around it as another layer.

---

std::vector<std::vector<int>> getIntVectors(std::ifstream* inFile)
{
    std::vector<std::vector<int>> inputVector;
    std::string string_vector_count;

    getline(*inFile, string_vector_count);

Why are you passing inFile as a pointer? You're using it without checking for nullptr and you don't assign back over the object to modify the caller's copy, so this should be a reference (not a pointer).

The return type has a lot of overhead. Each test case has exactly 3 values per element, so make a struct for that, or an array, or tuple; not a variable-length dynamically-allocated vector! Not only will this use tons more memory, but it requires dynamic allocation (and later freeing).

---

int getInputLines(std::string inputFileName, int &vectorSize, std::vector<std::vector<int>>& queries)

This is returning a SUCCESS/FAILURE flag, and passing the results back through "out" parameters. Furthermore you wrote int &vectorSize instead of int& vectorSize, nevermind that it's a size_t not an int or that the vector itself already knows its own size. This is a weird miss-mash of C code with some C++ features added.

Reviewing the data to be read, I see that it contains not just a list of commands but the cell count as well. The number of commands becomes the vector of commands' size. But where to store the cell count? You should abstract out the Test Case into its own class, even though it's just a vector plus another number. This will make the code clearer since you know when you have a single Test Case or an array of Test Cases, or the vector of commands without the cell count.

---

    do {
        std::cout << "How many test cases do you want to run?";
        std::cin >> testCount;
        if (testCount < 0 || testCount > MAX_TEST_CASE)
        {
            std::cerr << "The number of test cases must be greater > 0 and less than " << " " << MAX_TEST_CASE << "\n";
        }
    } while (testCount < 0 || testCount > MAX_TEST_CASE);

This is something that bothers me about code like this. You write your own ad-hoc "trying to be robust" user input routines. That's not part of the actual problem, and such routines are never perfect anyway.

In a real program, it won't prompt you. It looks at command-line arguments, and gives an error message if they are not suitable, or a help message if there are none. No loop and retry needed.

And don't use "out" parameters for returning things!

---

unsigned long mergeAndFindMax(std::vector<unsigned long> maxValues, std::vector<std::vector<unsigned long>> calculatedValues, const size_t executionCount)
Did you notice that you're passing not just a vector but also a vector of vectors by value to this function, causing the whole dynamic memory tree to be duplicated?!

Scanning ahead, I see other functions doing that too.

Name the types: your vector<unsigned long> should be the cell array type. Don't use unsigned long as that's implementation defined as to what range it holds. Use the explicitly sized names like uint64_t.

---

std::vector<unsigned long> maximumValues(n, 0);
You know that maximumValues[n] does not exist in this vector? I think they intended for subscripts to range from 1 to n inclusive ("1 based"), but you have 0 through n-1 inclusive.

---

Where can you put const that you haven't?

Good luck, and keep practicing! And always have fun.

Answer 2

Yes, brute-force is a sub-optimal solution.

A better way:

1. Decompose each query a b k into two parts:

   • At index a, add k
   • At index b + 1, add -k

2. Store those sub-queries in one vector.

3. Sort the sub-queries.

4. Iterate the sub-queries to find the solution.

Opportunities for parallel execution? Sparse outside the sort.

---

Inefficiencies common to challenge sites:

• Using std::vector when the number of elements is known and small. The overhead of dynamically allocating all those small bits adds up.

• Copying huge amounts of data unnecessarily, most of the time by passing above big vectors of vectors by value.

• Flushing the output-stream all the time. If you actually need the flush also contained in std::endl, be explicit and use std::flush.