Short Problem Definition:

A non-empty zero-indexed array A consisting of N integers is given. Two integers P and Q are called adjacent in array A if there exists an index 0 ≤ K < N−1 such that:

• P = A[K] and Q = A[K+1], or
• Q = A[K] and P = A[K+1].

A non-empty zero-indexed sequence B consisting of M integers is called adjacent in array A if the following conditions hold:

• B[0] = A[0];
• B[M−1] = A[N−1];
• B[K] and B[K+1] are adjacent in A for 0 ≤ K < M−1.

Link

ShortestAdjSeq

Complexity:

time complexity is O(NlogN)

space complexity is O(N)

Execution:

This is a graph problem, the shortest adjacent sequence is basically a shortest path in a bidirectional graph.

To calculate the shortest path I am using Breath-first-search or Dijkstra’s algorithm.

I don’t agree with the problem specification of one of the extreme cases such as [1,2,1]. I believe that the shortest path is 3, since the beginning and end are not adjacent. But it seems that Codility expects 1.

Solution:

from collections import defaultdict

def bfs_shortest_path(paths, start, end):
    q = [(start, 1)]

    visited_paths = set()
    visited_paths.add(start)

    while q:
        key, distance = q.pop(0)
        new_distance = distance + 1
        for path in paths[key]:
            if path == end:
                return new_distance
            elif path not in visited_paths:
                visited_paths.add(path)
                q.append((path, new_distance))


def solution(A):
    if len(A) <= 2:
        return len(A)

    # I dont agree with this edge case based on the problem statement
    if A[0] == A[-1]:
        return 1

    paths = defaultdict(set)

    paths[A[0]].add(A[1])
    paths[A[-1]].add(A[-2])

    for i in range(1, len(A)-1):
        paths[A[i]].add(A[i-1])
        paths[A[i]].add(A[i+1])

    return bfs_shortest_path(paths, A[0], A[-1])

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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