Sunday, May 29, 2016

MaxCounters (Codility)

Problem Statement: MaxCounters

C++ Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// you can use includes, for example:
#include <algorithm>
#include <vector>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(int N, vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    std::vector<int> counters(N, 0);

    auto maxCounter = 0;
    auto effectiveMaxCounter = 0;

    for (auto const &e : A)
    {
        if (e <= N)
        {
            if (counters[e - 1] > effectiveMaxCounter)
            {
                counters[e - 1]++;
            }
            else
            {
                counters[e - 1] = effectiveMaxCounter + 1;
            }
            maxCounter = std::max(maxCounter, counters[e - 1]);
        }
        else
        {
            effectiveMaxCounter = maxCounter;
        }
    }

    for (auto &e : counters)
    {
        e = std::max(e, effectiveMaxCounter);
    }

    return counters;
}

C# Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    public int[] solution(int N, int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int[] counters = new int[N];
        for(var index = 0; index < counters.Length; ++index)
        {
            counters[index] = 0;
        }

        var maxCounter = 0;
        var effectiveMaxCounter = 0;

        foreach (var e in A)
        {
            if (e <= N)
            {
                if (counters[e - 1] > effectiveMaxCounter)
                {
                    counters[e - 1]++;
                }
                else
                {
                    counters[e - 1] = effectiveMaxCounter + 1;
                }
                maxCounter = Math.Max(maxCounter, counters[e - 1]);
            }
            else
            {
                effectiveMaxCounter = maxCounter;
            }
        }

        for(var index = 0; index < counters.Length; ++index)
        {
            counters[index] = Math.Max(counters[index], effectiveMaxCounter);
        }

        return counters;
            
    }
}

Learnings

  • O(N*M) Solution
It is easy to create a solution with N*M time complexity. Whenever, the input array has an element greater than N, go through each element of the counters array and set each element to the current max so far. But this solution is rejected by Codility. However, the catch is that each time \an element greater than the number of counters is encountered in the input array, we need not update each element of the counters array to the current max. We can simply store the value of current max and then use the check 'counters[e - 1] > effectiveMaxCounter' on the next update to ensure that we increment from the effectiveMaxCounter onwards. This however requires at least one increment operation after the max operation
  • std::max operation
This was another important catch because not every counter may encounter an increment operation after the max operation. Therefore, a loop is required to run at the end to ensure that every element is at least as large as the effectiveMaxCounter
  • foreach variable in C#
The foreach variable in C# is readonly and cannot be used to modify the original element in the collection unlike the flexibility in a C++11 for loop.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)