Test results - Codility

Tasks Details

hard

1. DoubleMedian

Given two slices of sorted arrays, find the median. Repeat for many such slices, return the median of the results.

100%

Not assessed

The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:

X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8

is 5; the median of the following sequence:

X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2

is 2; and the following sequence:

X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8

has two medians: 4 and 5.

Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.

Write a function:

def solution(A, B, P, Q, R, S)

that, given:

two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order

two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K

two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K

computes medians of K sequences of the form:

A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]

for 0 ≤ I < K, and returns the median of all such medians.

For example, given the following arrays:

A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3

the function should return 8, since:

the median of [10, 13, 5, 6, 8, 12, 13] equals 10,

the median of [4, 10, 5] equals 5,

the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and

the median of [10, 5, 8] equals 8.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000];

K is an integer within the range [1..10,000];

each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];

array A is sorted in non-decreasing order;

array B is sorted in non-decreasing order;

each element of arrays P and Q is an integer within the range [0..N-1];

each element of arrays R and S is an integer within the range [0..M-1];

P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;

K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.

Solution

Programming language used Python

Total time used 1 minutes

Effective time used 1 minutes

Notes

not defined yet

Task timeline

Code: 12:38:58 UTC, py, verify, result: Passed

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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

from bisect import bisect_left, bisect_right

class MedianFinder(object):

    def __init__(self, left, right, left_begin, left_end, right_begin, right_end):
        self.left = left
        self.right = right
        self.left_begin = left_begin
        self.left_end = left_end # end IS NON-INCLUSIVE!
        self.right_begin = right_begin
        self.right_end = right_end # end IS NON-INCLUSIVE!
        self.half_len = ((self.left_end - self.left_begin) + (self.right_end - self.right_begin)) // 2

    def find_median_in_left(self):
        # assume that median is in the left array
        self._possible_begin = self.left_begin
        self._possible_end = self.left_end # non-inclusive
        while self._possible_begin < self._possible_end:
            found = self._search_step()
            if found is not None:
                return found
        return None # median not found

    def _search_step(self):
        middle_index = (self._possible_begin + self._possible_end) // 2
        middle_value = self.left[middle_index]
        to_the_left_in_left = middle_index - self.left_begin
        to_the_left_in_right = self._lfind_in_right(middle_value) - self.right_begin
        to_the_left = to_the_left_in_left + to_the_left_in_right
        if to_the_left > self.half_len:
            # result is too big
            self._possible_end = middle_index
            return None
        to_the_right_in_left = (self.left_end - middle_index) - 1
        to_the_right_in_right = self.right_end - self._rfind_in_right(middle_value)
        to_the_right = to_the_right_in_left + to_the_right_in_right
        if to_the_right > self.half_len:
            # result is too small
            self._possible_begin = middle_index + 1
            return None
        return middle_value # it's the median!

    def _lfind_in_right(self, value):
        return bisect_left(self.right, value, lo=self.right_begin, hi=self.right_end)

    def _rfind_in_right(self, value):
        return bisect_right(self.right, value, lo=self.right_begin, hi=self.right_end)



def find_double_median(A, B, p, q, r, s):
    left_begin = p
    left_end = q + 1
    right_begin = r
    right_end = s + 1
    result = MedianFinder(A, B, left_begin, left_end, right_begin, right_end).find_median_in_left()
    if result is not None:
        return result
    return MedianFinder(B, A, right_begin, right_end, left_begin, left_end).find_median_in_left()



def simple_median(numbers):
    numbers.sort()
    return numbers[len(numbers) // 2]


def double_median(A, B, P, Q, R, S):
    medians = []
    for i in xrange(len(P)):
        medians.append(find_double_median(A, B, P[i], Q[i], R[i], S[i]))
    return simple_median(medians)

Analysis

▶

example
example from the problem statement

✔

▶

example_old

✔

Code: 12:39:03 UTC, py, verify, result: Passed

from bisect import bisect_left, bisect_right

class MedianFinder(object):

    def __init__(self, left, right, left_begin, left_end, right_begin, right_end):
        self.left = left
        self.right = right
        self.left_begin = left_begin
        self.left_end = left_end # end IS NON-INCLUSIVE!
        self.right_begin = right_begin
        self.right_end = right_end # end IS NON-INCLUSIVE!
        self.half_len = ((self.left_end - self.left_begin) + (self.right_end - self.right_begin)) // 2

    def find_median_in_left(self):
        # assume that median is in the left array
        self._possible_begin = self.left_begin
        self._possible_end = self.left_end # non-inclusive
        while self._possible_begin < self._possible_end:
            found = self._search_step()
            if found is not None:
                return found
        return None # median not found

    def _search_step(self):
        middle_index = (self._possible_begin + self._possible_end) // 2
        middle_value = self.left[middle_index]
        to_the_left_in_left = middle_index - self.left_begin
        to_the_left_in_right = self._lfind_in_right(middle_value) - self.right_begin
        to_the_left = to_the_left_in_left + to_the_left_in_right
        if to_the_left > self.half_len:
            # result is too big
            self._possible_end = middle_index
            return None
        to_the_right_in_left = (self.left_end - middle_index) - 1
        to_the_right_in_right = self.right_end - self._rfind_in_right(middle_value)
        to_the_right = to_the_right_in_left + to_the_right_in_right
        if to_the_right > self.half_len:
            # result is too small
            self._possible_begin = middle_index + 1
            return None
        return middle_value # it's the median!

    def _lfind_in_right(self, value):
        return bisect_left(self.right, value, lo=self.right_begin, hi=self.right_end)

    def _rfind_in_right(self, value):
        return bisect_right(self.right, value, lo=self.right_begin, hi=self.right_end)



def find_double_median(A, B, p, q, r, s):
    left_begin = p
    left_end = q + 1
    right_begin = r
    right_end = s + 1
    result = MedianFinder(A, B, left_begin, left_end, right_begin, right_end).find_median_in_left()
    if result is not None:
        return result
    return MedianFinder(B, A, right_begin, right_end, left_begin, left_end).find_median_in_left()



def simple_median(numbers):
    numbers.sort()
    return numbers[len(numbers) // 2]


def double_median(A, B, P, Q, R, S):
    medians = []
    for i in xrange(len(P)):
        medians.append(find_double_median(A, B, P[i], Q[i], R[i], S[i]))
    return simple_median(medians)

Analysis

▶

example
example from the problem statement

✔

▶

example_old

✔

Code: 12:39:05 UTC, py, final, score: 100

from bisect import bisect_left, bisect_right

class MedianFinder(object):

    def __init__(self, left, right, left_begin, left_end, right_begin, right_end):
        self.left = left
        self.right = right
        self.left_begin = left_begin
        self.left_end = left_end # end IS NON-INCLUSIVE!
        self.right_begin = right_begin
        self.right_end = right_end # end IS NON-INCLUSIVE!
        self.half_len = ((self.left_end - self.left_begin) + (self.right_end - self.right_begin)) // 2

    def find_median_in_left(self):
        # assume that median is in the left array
        self._possible_begin = self.left_begin
        self._possible_end = self.left_end # non-inclusive
        while self._possible_begin < self._possible_end:
            found = self._search_step()
            if found is not None:
                return found
        return None # median not found

    def _search_step(self):
        middle_index = (self._possible_begin + self._possible_end) // 2
        middle_value = self.left[middle_index]
        to_the_left_in_left = middle_index - self.left_begin
        to_the_left_in_right = self._lfind_in_right(middle_value) - self.right_begin
        to_the_left = to_the_left_in_left + to_the_left_in_right
        if to_the_left > self.half_len:
            # result is too big
            self._possible_end = middle_index
            return None
        to_the_right_in_left = (self.left_end - middle_index) - 1
        to_the_right_in_right = self.right_end - self._rfind_in_right(middle_value)
        to_the_right = to_the_right_in_left + to_the_right_in_right
        if to_the_right > self.half_len:
            # result is too small
            self._possible_begin = middle_index + 1
            return None
        return middle_value # it's the median!

    def _lfind_in_right(self, value):
        return bisect_left(self.right, value, lo=self.right_begin, hi=self.right_end)

    def _rfind_in_right(self, value):
        return bisect_right(self.right, value, lo=self.right_begin, hi=self.right_end)



def find_double_median(A, B, p, q, r, s):
    left_begin = p
    left_end = q + 1
    right_begin = r
    right_end = s + 1
    result = MedianFinder(A, B, left_begin, left_end, right_begin, right_end).find_median_in_left()
    if result is not None:
        return result
    return MedianFinder(B, A, right_begin, right_end, left_begin, left_end).find_median_in_left()



def simple_median(numbers):
    numbers.sort()
    return numbers[len(numbers) // 2]


def double_median(A, B, P, Q, R, S):
    medians = []
    for i in xrange(len(P)):
        medians.append(find_double_median(A, B, P[i], Q[i], R[i], S[i]))
    return simple_median(medians)

Analysis summary

Analysis

Detected time complexity:

O(K*(log(K)+log(N)+log(M)))

▶

example
example from the problem statement

✔

▶

example_old

✔

▶

simple

✔

▶

simple2a

✔

▶

simple2b

✔

▶

simple3

✔

▶

simple4

✔

▶

boundary_cases
various correctness tests

✔

▶

smaller_medium_1
performance test, size 5K

✔

▶

smaller_medium_2
performance test, size 7K

✔

▶

smaller_large0
performance test, size 10K

✔

▶

smaller_large1
performance test, size 14K

✔

▶

smaller_large2
performance test, size 20K

✔

▶

medium_0
performance test, size 32K

✔

▶

medium_1
performance test, size 50K

✔

▶

medium_2
performance test, size 70K

✔

▶

large0
performance test, size 100K

✔

▶

large1
performance test, size 140K

✔

▶

large2
performance test, size 200K

✔