Short Problem Definition:

Rotate an array to the right by a given number of steps.

Link

Cyclic Rotation

Complexity:

expected worst-case time complexity is O(N)

Execution:

There are multiple solutions to this problem. I picked the one that does not create a copy of the array.

Solution:

def reverse(arr, i, j):
    for idx in xrange((j - i + 1) / 2):
        arr[i+idx], arr[j-idx] = arr[j-idx], arr[i+idx]

def solution(A, K):
    l = len(A)
    if l == 0:
        return []
        
    K = K%l
    
    reverse(A, l - K, l -1)
    reverse(A, 0, l - K -1)
    reverse(A, 0, l - 1)

    return A

Short Problem Definition:

Compute the total length covered by 1-dimensional segments.

Link

SqlSegmentSum

Complexity:

time complexity

space complexity

Execution:

I first create a numbers table from 1 to 1.000.000, this could be done just once when creating the DB. In this challenge it adds a flat 0.3sec runtime to all testcases.

In the second step I simply unique join the segments and number tables.

Solution:

-- create numbers utility structure, very basic integer primary key column n
create table numbers(n integer not null, primary key(n asc));
-- insert generated sequential integers
insert into numbers(n)
select rowid
from (

-- build 1,000,000 rows using Cartesian product
select 1
from (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) a, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) b, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) c, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) d, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) e, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) f

) derived;

select count(distinct n) from numbers inner join segments
on numbers.n between segments.l+1 and segments.r

Short Problem Definition:

Simulate a cannon shooting and heaps of falling cannonballs

Link

Cannon Balls

Complexity:

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

expected worst-case space complexity is O(H+M)

Execution:

The obvious brute force solution would be to check the minimum index that is high enough to block the shot. This would result in a N*M runtime. Based on observation we can see that the hit location can be precomputed and it changes only with small steps.

• -1 in the hit_location means, that the ball either ricochets or flies above the highest peak
• anything that hits the 0th index also does nothing

Solution:

def solution(A, B):
    highest_ball = max(B)
    hit_location = [-1] * (highest_ball+1)
    ricochet = A[0]
    
    for idx, a in enumerate(A):
        lvl = min(a, highest_ball)
        while hit_location[lvl] == -1 and lvl > ricochet:
            hit_location[lvl] = idx
            lvl -= 1
            
    # print hit_location

    for ball in B:
        hits_at = hit_location[ball]
        # print "ball", ball, "hits at", hits_at
        if hits_at <= 0:
            continue
        A[hits_at-1] += 1
        hit_location[A[hits_at-1]] = min(hit_location[A[hits_at-1]], hits_at-1)
        
        
    return A

Short Problem Definition:

Compute intersections between sequence of discs.

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.

Link

Number of Disc Intersections

Complexity:

expected worst-case time complexity is O(N*log(N))

expected worst-case space complexity is O(N)

Execution:

In my mind this problem is very similar to the Codility Fish. You keep count of how many not-yet-ended disks there are. Every beginning has to cross all not-yet-ended disks. The best explanation on the web was written by Luca. His solution is much better than my C-style double-checked while loop. I therefore created a mixture of both 🙂

• Keep in mind that any pair of circles can intersect only once.
• If 1+ beginnings have the same point as 1+ endings. You first have to process the beginnings. The old and new ones have per definition a meeting point.

Solution:

def solution(A):
    circle_endpoints = []
    for i, a in enumerate(A):
        circle_endpoints += [(i-a, True), (i+a, False)]

    circle_endpoints.sort(key=lambda x: (x[0], not x[1]))

    intersections, active_circles = 0, 0

    for _, is_beginning in circle_endpoints:
        if is_beginning:
            intersections += active_circles
            active_circles += 1
        else:
            active_circles -= 1
        if intersections > 10E6:
            return -1

    return intersections

Short Problem Definition:

Given a table A of N integers from 0 to N-1 calculate the smallest such index P, that that {A[0],…,A[N-1]} = {A[0],…,A[P]}.

Link

PrefixSet

Complexity:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)

Execution:

Based on the number of elements that can occur in N, you either mark the occurrences in a boolean array, or put them in a set. The last occurrence of an element that was not seen before is the result.

Solution:

def solution(A):
    seen = set()
    smallest_prefix_idx = 0
    
    for idx in xrange(len(A)):
        if A[idx] not in seen:
            seen.add(A[idx])
            smallest_prefix_idx = idx
            
    return smallest_prefix_idx

Short Problem Definition:

Find a maximal set of non((-))overlapping segments.

Link

MaxNonoverlappingSegments

Complexity:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)

Execution:

This can be solved by using greedy search. The beginning of the next segment must come strictly after its predecessor.

Solution:

def solution(A, B):
    if len(A) < 1:
        return 0
    
    cnt = 1
    prev_end = B[0]
    
    for idx in xrange(1, len(A)):
        if A[idx] > prev_end:
            cnt += 1
            prev_end = B[idx]
    
    return cnt

Short Problem Definition:

Find a maximum sum of a compact subsequence of array elements.

Link

MaxSliceSum

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

The only difference to the example given by Codility is the minimal slice length, which is 1.

Solution:

def solution(A):
    max_ending = max_slice = -1000000
    for a in A:
        max_ending = max(a, max_ending +a)
        max_slice = max(max_slice, max_ending)
        
    return max_slice

Short Problem Definition:

Calculate the number of elements of an array that are not divisors of each element.

Link

CountNonDivisible

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

Using the Sieve of Eratosthenes, you generate divisors for all input elements of A. If a given number x is a divisor of element (x*N == element), then N also is a divisor. (N = element//x). After all divisors are computed, we simply subtract those (multiplied by their counts or 0) from the total number of elements in A.

Solution:

def solution(A):
 
    A_max = max(A)
 
    count = {}
    for element in A:
        if element not in count:
            count[element] = 1
        else:
            count[element] += 1
 
    divisors = {}
    for element in A:
        divisors[element] = set([1, element])
 
    # start the Sieve of Eratosthenes
    divisor = 2
    while divisor*divisor <= A_max:
        element_candidate = divisor
        while element_candidate  <= A_max:
            if element_candidate in divisors and not divisor in divisors[element_candidate]:
                divisors[element_candidate].add(divisor)
                divisors[element_candidate].add(element_candidate//divisor)
            element_candidate += divisor
        divisor += 1
 
    result = [0] * len(A)
    for idx, element in enumerate(A):
        result[idx] = (len(A)-sum([count.get(divisor,0) for divisor in divisors[element]]))
 
    return result

Short Problem Definition:

Find the minimal average of any slice containing at least two elements.

Link

MinAvgTwoSlice

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

Every slice must be of size two or three. Slices of bigger sizes are created from such smaller slices. Therefore should any bigger slice have an optimal value, all sub-slices must be the same, for this case to hold true. Should this not be true, one of the sub-slices must be the optimal slice. The others being bigger. Therefore we check all possible slices of size 2/3 and return the smallest one. The first such slice is the correct one, do not use <=!

For other languages use BigInts or equal. This line (A[idx] + A[idx+1] + A[idx+2])/3.0 can easily overflow!

You can read the formal proof by Minh Tran Dao here.

Solution:

def solution(A):
    min_idx = 0
    min_value = 10001

    for idx in xrange(0, len(A)-1):
        if (A[idx] + A[idx+1])/2.0 < min_value:
            min_idx = idx
            min_value = (A[idx] + A[idx+1])/2.0
        if idx < len(A)-2 and (A[idx] + A[idx+1] + A[idx+2])/3.0 < min_value:
            min_idx = idx
            min_value = (A[idx] + A[idx+1] + A[idx+2])/3.0

    return min_idx