06/10/14

Codility ‘PassingCars’ Solution

Short Problem Definition:

Count the number of passing cars on the road.

Link

PassingCars

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1)

Execution:

Count all cars heading in one direction (west). Each car heading the other direction (east) passes all cars that went west so far. Note that east cars at the beginning of the list pass no cars! Also do not forget the upper limit!

Solution:
def solution(A):
    west_cars = 0
    cnt_passings = 0

    for idx in xrange(len(A)-1, -1, -1):
        if A[idx] == 0:
            cnt_passings += west_cars
            if cnt_passings > 1000000000:
                return -1
        else:
            west_cars += 1

    return cnt_passings

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
06/5/14

Codility ‘MaxCounters’ Solution

Short Problem Definition:

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

Link

MaxCounters

Complexity:

expected worst-case time complexity is O(N+M);

expected worst-case space complexity is O(N)

Execution:

The idea is to perform the specified operation as stated. It is not required to iterate over the whole array if a new value is set for all the values. Just save the value and check it when an increase on that position is performed.

Solution:
#include <algorithm>

vector<int> solution(int N, vector<int> &A) {
    vector<int> sol;
    int current_max = 0;
    int last_increase = 0;

    for(int i=0; i<N;i++){
        sol.push_back(0);
    }

    for(unsigned int i=0; i<A.size();i++){
        if (A[i] > N) {
            last_increase = current_max;
        } else {
            sol[A[i]-1] = max(sol[A[i]-1], last_increase);
            sol[A[i]-1]++;
            current_max = max(current_max, sol[A[i]-1]);
        }
    }

    for(int i=0; i<N;i++){
        sol[i] = max(sol[i], last_increase);
    }

    return sol;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
06/1/14

Codility ‘MissingInteger’ Solution

Short Problem Definition:

Find the minimal positive integer not occurring in a given sequence.

Link

MissingInteger

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

You only need to consider the first (N) positive integers. In this specification 0 does not count as a valid candidate! Any value that is below 1 or above N can be ignored.

Solution:
def solution(A):
    seen = [False] * len(A)
    for value in A:
        if 0 < value <= len(A):
            seen[value-1] = True

    for idx in xrange(len(seen)):
        if seen[idx] == False:
            return idx + 1

    return len(A)+1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin