Maximum slice problem

On Codility there is a section dedicated to problems about determining the maximum slice in a vector. The generic problem, disscused in a pdf, is this:

Given a vector of integers, find the slice with the largest sum, and return that value.

An example is provided, that I converted on the spot to a C++11 GoogleTest test case:
TEST(MaxSlice, Given)
{
    std::vector<int> input { 5, -7, 3, 5, -2, 4, -1 };
    EXPECT_EQ(10, solution(input));
}
The biggest slice is the one ranging from input[2] to input[5], resulting in a sum of 10.

A quadratic solution

It shouldn't be complicated to think of a solution asymptotically quadratic in time. Loop on all the elements in the sequence. For each of them loop on all the subsequence starting there up to the input end, calculating their sums. The biggest one of them is our result.

Here is a possible implementation of this algorithm:
int solution(const std::vector<int>& input)
{
    int result = 0;
    for(unsigned i = 0; i < input.size(); ++i) // 1
    {
        int tentative = 0; // 2
        for(unsigned j = i; j < input.size(); ++j) // 3
        {
            tentative += input[j];
            result = std::max(result, tentative); // 4
        }
    }
    return result;
}
1. Check all the subsequences, defining i as their begin.
2. Store here the sum for the current subsequence.
3. Try all the possible subsequences starting from i.
4. Save the current subsequence if it is the current biggest one.

A linear solution

The previous solution works fine, but it mindlessly repeat adding on and on the same elements. We could save time just performing a single linear scan of our data, observing that when we get a negative result adding an element, it is more worthy to get rid of that subsequence, and starting from the next element:
int solution(const std::vector<int>& input)
{
    int result = 0;
    int candidate = 0;
    for(int cur : input)
    {
        candidate = std::max(0, candidate + cur); // 1
        result = std::max(result, candidate); // 2
    }

    return result;
}
1. Keep the candidate until adding the current element gives a positive value. Otherwise, reset the sequence. In the worst case, all negative input element, we won't never accept any value, and we would return the total relative to the empty subsequence, namely zero.
2. If the current candidate is a better solution, save it.

Go to the full post

Codility EquiLeader

Given a vector of integers, check if there is a leader (aka dominator) in it. If so, define equi-leader as an element of such a vector that split the vector in two subsequences, each of them has the same leader. Write a function that returns the number of equi-leaders in the passed vector.

You could find this problem, and test your solution (possibly) in your preferred programming language in the Leader codility section.

Actually, if you have already solved the other problem in the codility Leader section, named Dominator, you are already very close to the solution of this one.

To better explain what the point of the problem is, codility provides a test case, here it is, in a C++11 GoogleTest version:
TEST(EquiLeader, Given)
{
    std::vector<int> input { 4, 3, 4, 4, 4, 2 };
    ASSERT_EQ(2, solution(input));
}
The number four dominates the input sequence. If we split it on the first element (index 0) we get two subsequences where four is again a leader. The same if take the third element (index 2) as a pivot. These are the only cases correctly working on these vector, so we want our function to return 2.

I have split my C++11 solution in two parts. Firstly I wrote a utility function that gets a candidate leader for the entire sequence:
int getCandidateLeader(const std::vector<int>& input)
{
    int count = 0;
    int candidate;
    for(int cur : input) // 1
    {
        if(count == 0)
        {
            count = 1;
            candidate = cur;
        }
        else
        { // 2
            count += (candidate == cur) ? 1 : -1;
        }
    }

    return count ? candidate : std::numeric_limits<int>::max(); // 3
}
1. I am still not very used to the new C++11 range based for-loop. This is a place where it helps to make the code more readable. I am looping on the entire vector, and I don't care much about the index of any of its element, I am just interested in their values.
2. This is the central idea of this algorithm. Increasing the counter, when the current element is the same that the previously detected candidate, or throw away both elements, if they are different, let us solve the problem of getting a candidate leader in linear time.
3. If no good candidate has been detected, I return a non-acceptable value.

And this is the solution to the actual problem:
int solution(std::vector<int>& input)
{
    int leader = getCandidateLeader(input);
    if(leader == std::numeric_limits<int>::max()) // 1
        return 0;

    const unsigned count = std::count(input.begin(), input.end(), leader);
    if(count < input.size() / 2) // 2
        return 0;

    int leaders = 0; // 3
    unsigned leftLeaders = 0; // 4
    for(unsigned i = 0; i < input.size(); ++i)
    {
        if(input[i] == leader) // 5
            leftLeaders++;
        unsigned rightLeaders = (count - leftLeaders); // 6
        if(leftLeaders > (i + 1) / 2 && rightLeaders > (input.size() - i - 1) / 2)
            ++leaders; // 7
    }

    return leaders;
}
1. No candidate leader found, no need to go on.
2. The candidate leader is not dominant.
3. Keep memory of the current number of equi-leaders.
4. Here I store the number of leader occurrences in the current left subsequence. In the first loop, it contains just the leftmost element. It would grow till it would get all the sequence.
5. If the current element is a leader, increase the left counter.
6. Get the right subsequence number of leaders by subtraction.
7. If both left and right leader count are dominant in their subsequence, increase the equi-leader counter.

Go to the full post

Codility Dominator

Given a vector of integers, check if there is a dominator, meaning a value that occurs more than half the times, in it.

I have already written a couple of posts about this Codility problem. In the first one I solve it using a map as a buffer, in the second one I use the cheaper golden leader algorithm.

My porting to C++11 didn't change much of the original code. For instance, having to define a synonim to a type, instead of "typedef" it, I referred to the "using" keyword.

Go to the full post

Codility Fish

We are given in input two same sized integer vectors, the first containing fish dimensions, all of them are different, the second their direction, upstream or downstream.
The river is so narrow that fishes going in opposite direction have no choice but colliding, and the smaller one will soccumb, eaten by the other.
We want to know how many fishes will survive in the end.

I have already written a couple of posts on this problem. One where I show a naive, with N squared time complexity, solution, and another one where I implement a linear solution.

I worked on it once again, now that we can use C++11 to solve codility problems. However I didn't get anything different from that time. I just wrote the test cases in a more clean way, using the new syntax that allows creating a vector from an initialization list.

Nothing new to say about it, I am sorry to say.

Go to the full post

Codility StoneWall

We are given a sequence of integers representing the height of a wall that we have to build. We should return the minimum number of rectangular blocks needed to build it.

A good hint is that this problem has been included in the Stacks and Queues codility section. If you want more clues, you could have a look at the codility blog, where this problem is discussed and a solution is given.

Actually, I found the discussion in there more confusing than helping. Still I got a couple of elements to think on. I pondered on them, and in the end I came out with a sort of pseudo-code.

I use a stack to keep track of the current status of the wall, each element in it represent a block I am using to reach the current level.
Let's say that I am at the i-th step. The stack reflects the status of the previous step.
Maybe I don't have to do anything. The current level is the same. OK, just move to the next step.
Maybe I have to increase the wall height. That's easy, just put a new block of the right size on top the stack.
Maybe I have to decrease the wall height. That's a bit more complicate. I should remove enough blocks to get the right size, or something less than it. And then add a new block, if required.
And, well, that's it.

Then I wrote a few test cases, C++ for GoogleTest:
TEST(StoneWall, Given) // 1
{
    std::vector<int> input { 8, 8, 5, 7, 9, 8, 7, 4, 8 };
    ASSERT_EQ(7, solution(input));
}

TEST(StoneWall, Simple) // 2
{
    std::vector<int> input { 1, 2, 1 };
    ASSERT_EQ(2, solution(input));
}

TEST(StoneWall, Bad) // 3
{
    std::vector<int> input { 0 };
    ASSERT_EQ(-1, solution(input));
}
1. Provided by codility.
2. A sort of minimal pyramid.
3. As usual, Codility does not care about bad input data. I decided to add a basic check to avoid non-positive input. A more robust solution would have been using assertions (if the data check would be a Somebody Else's Problem) or exceptions. Here I decided to keep it simpler and just return a minus one.

And here is my solution:
int solution(std::vector<int>& input)
{
    if(std::find_if_not(input.begin(), input.end(), [](int cur){ return cur > 0; }) != input.end()) // 1
        return -1;

    int blocks = 0;
    std::stack<int> buffer;

    std::for_each(input.begin(), input.end(), [&](int cur) // 2
    {
        while(!buffer.empty() && cur < buffer.top()) // 3
        {
            buffer.pop();
        }

        if(buffer.empty() || cur > buffer.top()) // 4
        {
            buffer.push(cur);
            ++blocks;
        }
    });

    return blocks;
}
1. The STL find_if_not() is used to ensure all the element in input are positive. Paranoid check not required by codility.
2. Loop on all the elements. Notice that the lambda captures by reference the external variables so that it can modify them in its body.
3. If the previous wall height is taller than the current request, remove block(s) from the stack.
4. Add a new block to the stack to match the current request. Besides, increase the block counter.

Go to the full post

Codility Nesting

Given a string that contains only open and close round brackets, check if they are all properly nested.

This is "painless" codility problem in the Stacks and Queues, is very close to its brother Brackets that we have just seen. Only, it is even simpler than that.

Well, it is painlessly easy if we take the right path, and consider it, as suggested by the section in which it is included, as a stack-related problem. If you miss this detail, you could find yourself in a bit more complicated territory. Have a look at this other post if you want to read some more stuff in that direction.

Otherwise, you could have a look at my C++11 solution:
int solution(std::string& input)
{
    int count = 0; // 1
    for(auto it = input.begin(); it != input.end(); ++it) // 2
    {
        if(*it == '(')
            ++count;
        if(*it == ')') // 3
        {
            if(!count)
                return 0;
            --count;
        }
    }
    return count == 0 ? 1 : 0; // 4
}
1. In this simple case, instead of using a proper stack, we can emulate it by using an integer. Have a look at Brackets to see a slight different version of this problem where a real stack makes more sense.
2. Loop on all the input elements, when we find an open bracket the counter is increased, as if we put it in a stack.
3. When a close bracket is found, we should pop the stack (i.e. decrease the counter). Still, we have to be careful, and ensure that the stack is not empty, that would mean no matching open bracket was previously seen.
4. I could have relied on the C++ automatic conversion from boolean type to integer, and avoid the use of the ternary operator. In any case, the meaning of this line is, only if the stack is empty (actually, the counter is zero) the function returns success.

Go to the full post

Codility Brackets

Given a string that contains only open and close brackets (round, squared, curly), check if they are all properly nested.

This is a "painless" problem in the Stacks and Queues, practicing area, on the codility web site.

When I compared my current solution to the previous one that I developed when codility didn't support C++11, I found out only minimal differences.

Firstly I wrote a few test cases, a couple of them are given by codility in the problem definition, I merely implemented them for GoogleTest:
TEST(Brackets, Given1)
{
    std::string input { "{[()()]}" };
    ASSERT_EQ(1, solution(input));
}

TEST(Brackets, Given2)
{
    std::string input { "([)()]" };
    ASSERT_EQ(0, solution(input));
}

TEST(Brackets, Empty)
{
    std::string input { "" };
    ASSERT_EQ(1, solution(input));
}
And this is my latest implementation:
int solution(std::string& input)
{
    if(input.size() % 2) // 1
        return 0;

    std::stack<char> buffer; // 2

    for(auto it = input.begin(); it != input.end(); ++it) // 3
    {
        switch(*it) // 4
        {
        case '(': case '[': case '{':
            buffer.push(*it);
            continue;
        }

        if(buffer.empty()) // 5
            return 0;

        char prev = buffer.top(); // 6
        if((*it == ')' && prev == '(') || (*it == ']' && prev == '[') || (*it == '}' && prev == '{'))
            buffer.pop();
        else
            return 0;
    }

    return buffer.empty() ? 1 : 0; // 7
}
1. An odd numbers of brackets implies bad nesting.
2. I am going to push on a stack all the open brackets, popping them as soon as a close one is found.
3. Loop on all the input elements.
4. If the current character is an open bracket, in any supported flavor, push it on the stack.
5. Otherwise, if the buffer is empty the current element is a bad one. It could be an unexpected close bracket or a dirty character. In any case I return failure.
6. Check the current element on stack top. If it is a matching bracket, pop it and check the next input value.
7. After checking all the elements, we return success only if no open bracket is still lingering in the stack.

Go to the full post

Codility Triangle

Given a vector of integer, detect if there is at least a triplet of elements that could represent the length of edges in a triangle.

You could find this "painless" problem in the Sorting section, practicing area, on the codility web site.

I have already solved it in a previous post, when codility referred to a C++98 compiler. Here I refactor the solution for the current C++11 codility programming environment. Please look at the previous post for more chatting on it.

We know that in a triangle, the sum of any two edges should be less that the third one, this lead to the condition we have to verify. Our function would get in input a STL vector of int, and return 1 for success and 0 for failure.

A couple of test case for this problem, C++11 for GoogleTest:
TEST(Triangle, Given1)
{
    std::vector<int> input { 10, 2, 5, 1, 8, 20 };
    ASSERT_EQ(1, solution(input));
}

TEST(Triangle, Given2)
{
    std::vector<int> input { 10, 50, 5, 1 };
    ASSERT_EQ(0, solution(input));
}
I have implemented my solution in this way:
int solution(std::vector<int>& input)
{
    if(input.size() < 3) // 1
    {
        return 0;
    }

    std::sort(input.begin(), input.end()); // 2

    for(unsigned i = 2; i < input.size(); ++i) // 3
    {
        if(input[i] < 0) // 4
        {
            i += 2;
            continue;
        }

        if(static_cast<unsigned>(input[i - 2] + input[i - 1]) > static_cast<unsigned>(input[i])) // 5
        {
            return 1;
        }
    }

    return 0;
}
1. Paranoid check, not required by codility.
2. Instead of checking all the possible triplets, that would generate a cubic time complexity solution, we can sort the input data before checking them.
3. Check all the possible triplets. The i-th one represent the third element in the current triplet.
4. We should expect also negative elements in input, still they make no sense for our problem. If the i-th element is negative, we can safely discard the current triplet and the next two ones (that would include this negative value).
5. We are considering three positive sorted elements. It is enough to ensure that the third one is bigger than the sum of the previous two ones to answer to the original question. I need to cast the values to unsigned to avoid any possible overflow problem.

Go to the full post

Codility MaxProductOfThree

Given a vector of integer, return the maximal value we could get multiplying any possible triplet.

You could find this problem, marked as painless, in the Sorting section, practicing area, on the codility web site.

And here is a test case, that I have translate for C++11 on GoogleTest, that is provided to make more clear the request:
TEST(MaxProductOfThree, Given)
{
    std::vector<int> input { -3, 1, 2, -2, 5, 6 };
    ASSERT_EQ(60, solution(input));
}
It is easy to spot that the maximal solution here is given by multiplying 2, 5, and 6, being them the biggest positive elements in the collection. Still, this test case it is not enough to capture all the interesting input data. It could happen also that we have two big negative elements, and we should remember that multiplying two negatives numbers gives a positive one.

I have already solved this problem some time ago, in a previous you could find my C++98 solution and some more testing and chatting about the requisites. Please have a look at it for more details.

Now Codility supports a C++11 compiler, and this is my refactoring for the new programming environment:
int solution(std::vector<int>& input)
{
    if(input.size() < 3) // 1
        return 0;

    std::sort(input.begin(), input.end()); // 2

    int pos = input.back() * *(input.rbegin() + 1) * *(input.rbegin() + 2); // 3
    int neg = input.front() * *(input.begin() + 1) * input.back(); // 4

    return std::max(pos, neg); // 5
}
1. Input checking is usually not considered for codility problems, still I didn't fill right not to state explicitly that we are expecting at least three elements in the input vector. Admittedly, throwing an exception would have been a more clean approach.
2. Checking all the triples would lead to a cubic time complexity. Much better to sort the collection, which costs a mere N*lgN.
3. Vanilla case, just pick the first three values to the left and multiply them.
4. Alternative solution, a couple of big negative values change the rule of the game. Get them, and multiply them to the one to the extreme left.
5. Compare the two tentative solutions, and return the big one.

If you think a bit about it, the pos and neg tentatives cover all the possible cases (all negative numbers, and any variation I could have thought of).

Go to the full post

Codility Distinct

We want to know how many distinct values in a passed integer vector.

This simple problem is available also on the Codility Sorting section. This fact is a huge hint to solve it, because sorting it before do any check makes our job a lot easier.

Reading the codility description, you could also find the description of a test case, that here I have ported to GoogleTest in C++11:
TEST(Distinct, Given)
{
    std::vector<int> input { 2, 1, 1, 2, 3, 1 };
    ASSERT_EQ(3, solution(input));
}
There are three distinct values in the input vector, so our function should return 3.

Here is a possible solution:
int solution(std::vector<int>& input)
{
    if(input.size() < 2) // 1
        return input.size();

    std::sort(input.begin(), input.end()); // 2

    int result = 1;
    int prev = input.front(); // 3
    std::for_each(input.begin() + 1, input.end(), [&](int cur){ // 4
        if(cur != prev) // 6
        {
            ++result;
            prev = cur;
        }
    });

    return result;
}
1. Trivial cases.
2. We are modifying the input data. This is not commonly seen as a good idea, since the caller usually doesn't want having such kind of surprises. On codility problems we usually assume that performances are of paramount importance.
3. There is at least a distinct value in the vector, the first one.
4. Loop on all the other values. Notice that I capture by reference the external values, so that I could change them in the lambda function.
5. Each time I see a new value, increase the result and keep track of the new value that I have to check.

Unique

The above solution works fine, still, meetingcpp tweeted me, what about std::unique?

Right, std::unique(). Here you can see it in action:
int solution(std::vector<int>& input)
{
    if(input.size() < 2)
        return input.size();

    std::sort(input.begin(), input.end());
    return std::unique(input.begin(), input.end()) - input.begin();
}
Isn't that a beauty?

The STL unique() function rearrange the elements in a sorted collection moving the duplicates to its end and returning an iterator to the new logical end - the actual collection size is not changed.

Go to the full post

Codility GenomicRangeQuery

Given a string representing a DNA sequence as a collection of 'A', 'C', 'G', 'T' letters, and number of subsequences in it, we should tell which is the minimal impact factor for each subsequence, where nucleotides A, C, G and T have impact factors of 1, 2, 3 and 4, respectively.

You could solve this problem on your own in the Codility Prefix Sum section. I have already given a couple of C++ solutions on a previous post, here I would just refactor the linear one to C++11.

Here is the Codility given test case, ported to GTest:
TEST(GenomicRangeQuery, Given)
{
    std::string dna { "CAGCCTA" };
    std::vector<int> first { 2, 5, 0 };
    std::vector<int> last { 4, 5, 6 };
    ASSERT_EQ(first.size(), last.size());

    std::vector<int> result = solution(dna, first, last);

    ASSERT_EQ(first.size(), result.size());
    EXPECT_EQ(2, result[0]); // 1
    EXPECT_EQ(4, result[1]);
    EXPECT_EQ(1, result[2]);
}
1. Subsequence 2, 4 is "GC", C has a lower impact factor, the result should be 2.
2. "T" leads to 4.
3. The full sequence has A's in it, so 1 is its minimal impact factor.

This is my C++11 solution:
int getType(char nucleotide) // 1
{
    switch (nucleotide)
    {
    case 'A':
        return 0;
    case 'C':
        return 1;
    case 'G':
        return 2;
    default:
        return 3;
    }
}

std::vector<int> solution(std::string& sequence, std::vector<int>& first, std::vector<int>& last)
{
    std::vector<std::vector<int>> parsums(4); // 2
    std::for_each(parsums.begin(), parsums.end(), [&sequence](std::vector<int>& cur)
    {
        cur.resize(sequence.size());
    });

    for (unsigned i = 0; i < sequence.size(); ++i) // 3
    {
        parsums[getType(sequence[i])][i] = 1;
    }

    for (int i = 0; i < 4; ++i) // 4
    {
        std::partial_sum(parsums[i].begin(), parsums[i].end(), parsums[i].begin());
    }

    std::vector<int> result(first.size()); // 5
    for (unsigned i = 0; i < first.size(); ++i)
    {
        int type = 3;
        for (unsigned j = 0; j < 3; ++j)
        {
            int left = first[i] > 0 ? parsums[j][first[i] - 1] : 0; // 6
            int right = parsums[j][last[i]];
            if (right != left) // 7
            {
                type = j;
                break;
            }
        }

        result[i] = type + 1; // 8
    }

    return result;
}
1. Trivial utility function to convert any nucleotide in a zero-based index.
2. I am going to put each nucleotide in its own vector. It would cost quite a lot in term of memory, but it is worthy in terms of execution time.
3. If I spot a T on position i, the element i on the T-vector is marked as found.
4. I convert each nucleotide specific vector in its own partial sum. In this way I am going to see just accessing first and last element in a give subsequence if that nucleotide is there. No need to loop in a loop, no quadratic complexity.
5. This is the vector I am going to give back to the caller.
6. We need to pay attention to the special case that occurs when the subsequence starts at the beginning of the sequence. Usually we need to get the value of the previous element, in this case there is not such a thing.
7. If the right partial sum has changed (actually, it could only be greater or equal) we have a nucleotide of the specific type. Since I am checking from the lowest value up, as soon as I find it, I break the loop.
8. The user wants a 1-based index to identify the solution.

Go to the full post

Codility MinAvgTwoSlice

Given a vector sized 2 or more, find the index where starts the first subsequence of two or more elements with a minimal average value.

Like CountDiv, I don't get why this problem is in the Codility Prefix Sum section. To solve it we could create our sort-of partial sums vector, but this would just add space complexity without giving anything back.

I guess the most interesting point in this problem is about the size of candidate subsequences. Let's say that we have spotted a good subsequence of four elements in our vector. We would always find a way of splitting it and get the same or better result by one of its subsequences, think for instance to { 1, 1, 1, 1 } . We can't always do that when the elements are just three, and this is as an example: { -12, 0, -12 }.

So, that's it. We need to check for 2- and 3- sized subsequences.

Here are a few GoogleTest C++11 test cases:
TEST(MinAvgTwoSlice, Given)
{
    std::vector<int> input { 4, 2, 2, 5, 1, 5, 8 };
    ASSERT_EQ(1, solution(input));
}

TEST(MinAvgTwoSlice, Neg)
{
    std::vector<int> input { 4, 2, 2, 5, -100, 5, -100 };
    ASSERT_EQ(4, solution(input));
}

TEST(MinAvgTwoSlice, Last)
{
    std::vector<int> input { 100, 100, 1 };
    ASSERT_EQ(1, solution(input));
}
And this is my solution:
int solution(std::vector<int>& input)
{
    assert(input.size() > 1); // 1

    int index = 0;
    double minimal = std::numeric_limits<double>::max();
    for(unsigned i = 0; i < input.size() - 2; ++i) // 2
    {
        double candidate = (input[i] + input[i+1]) / 2.0; // 3
        if(candidate < minimal)
        {
            index = i;
            minimal = candidate;
        }

        candidate = (input[i] + input[i+1] + input[i+2]) / 3.0; // 4
        if(candidate < minimal)
        {
            index = i;
            minimal = candidate;
        }
    }

    double candidate = (input.back() + *(input.rbegin() + 1)) / 2.0; // 5
    if(candidate < minimal)
        return input.size() - 2;

    return index;
}
1. Problem prerequisite.
2. Looping an all the elements but the last couple.
3. Check the current couple.
4. Check the current triplet.
5. Last couple.

Go to the full post