There are just two operation, increase-a-specified-value, and level-to-the-top. To invoke the first one we specify the 1-based index for the element we want to modify, the second one is invoked when N+1 is found. We can safely assume that no other integer would be passed, or we can consider them as no-op.

Here is a C++11 GTest test case, based on a case provided by codility:

TEST(MaxCounters, Given) { const int size = 5; // 1 std::vector<int> input { 3, 4, 4, 6, 1, 4, 4 }; // 2 std::vector<int> output = solution(size, input); ASSERT_EQ(size, output.size()); EXPECT_EQ(3, output[0]); EXPECT_EQ(2, output[1]); EXPECT_EQ(2, output[2]); EXPECT_EQ(4, output[3]); EXPECT_EQ(2, output[4]); }1. We want to operate on a five integer vector.

2. This list of operations translate as:

- increase the third element (from 0 to 1)

- increase the fourth element (to 1)

- increase the fourth element (to 2)

- equalize all the elements to the top value (2)

- increase the first element (to 3)

- increase the fourth element (to 3)

- increase the fourth element (to 4)

The resulting vector should be { 3, 2, 2, 4, 2 }.

I have already solved this problem some time ago, please have a look to that post if you want more information and also a first inefficient solution. This time I have aimed directly to the 100% solution, and I have written C++11 code - at that time codility did not support it.

As I found out comparing the results afterward, differences are minimal. Basically, just the use of a couple of lambda functions in for_each() loops, instead of old plain for loops:

std::vector<int> solution(int n, std::vector<int>& input) { std::vector<int> result(n); // 1 int highest = 0; // 2 int lowest = 0; std::for_each(input.begin(), input.end(), [&](int cur){ // 3 if(static_cast<unsigned>(cur) > result.size()) // 4 { lowest = highest; } else // 5 { int index = cur - 1; // 6 result[index] = std::max(result[index], lowest) + 1; // 7 if(result[index] > highest) // 8 highest = result[index]; } }); std::for_each(result.begin(), result.end(), [lowest](int& cur){ // 9 if(cur < lowest) cur = lowest; }); return result; }1. This is what the caller wants me to generate.

2. Cache the current highest and lowest values in the output vector. This is going to save a lot of computation time. And it comes quite cheap too.

3. Loop on all the operations specified by the caller.

4. I rely on the input data correctness, guaranteed by codility. In my previous implementation I have been more paranoid, and implemented a no-op strategy in case of unexpected values. Anyway. If the current value is not a valid 1-based index, I assume a top leveling is required. Instead of applying the variation to the actual data, I simply state that the current lowest value is just like the highest one.

5. I have been requested to increase a specific value.

6. For sake of readability, I introduced this local variable, representing the actual 0-based index in my vector.

7. Remember about (4). Possibly the current value in that index is not the real one, I have to compare it against the lowest variable to ensure that I get it right. Then increase it.

8. I should ensure the highest cached value is still valid, so that next time I could do the (4) trick.

9. Before returning to the caller, I should ensure any value in the vector is not less than the lowest cached value.

## No comments:

## Post a Comment