06/10/14

# Codility ‘PassingCars’ Solution

##### Short Problem Definition:

Count the number of passing cars on the road.

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.

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.

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.

06/1/14

# Codility ‘MissingInteger’ Solution

##### Short Problem Definition:

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

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.