Test results - Codility

Tasks Details

medium

1. RectanglesStrip

From a given set choose as many rectangles with a common side as possible.

Task Score

100%

Correctness

100%

Performance

100%

There are N rectangles numbered from 0 to N-1. The K-th rectangle has size A[K] × B[K].

We want to arrange as many rectangles as possible into a strip. The rectangles can be arranged into a strip if they all share a side of the same length (which becomes the height of the strip). Note that rectangles can be rotated.

Write a function:

def solution(A, B)

that, given two arrays A and B of N integers each, returns the maximum number of rectangles that can be arranged into a strip.

Examples:

1. Given A = [2, 3, 2, 3, 5] and B = [3, 4, 2, 4, 2], the function should return 3. Choosing the 0th, 2nd and 4th rectangles we can obtain the following strip of height 2 (note that the 0th rectangle was rotated):

(3 × 2), (2 × 2), (5 × 2)

We can also choose the 0th, 1st and 3rd rectangles to obtain a strip of height 3. Here we have rotated 1st and 3rd rectangles:

(2 × 3), (4 × 3), (4 × 3)

2. Given A = [2, 3, 1, 3] and B = [2, 3, 1, 3], the function should return 2. We can choose the 1st and 3rd rectangles:

(3 × 3), (3 × 3)

3. Given A = [2, 10, 4, 1, 4] and B = [4, 1, 2, 2, 5], the function should return 3. We can choose the 0th, 2nd and 4th rectangles to obtain a strip of height 4:

(2 × 4), (2 × 4), (5 × 4)

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

arrays A and B both consist of N integers;

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

Solution

Programming language used Python

Time spent on task 2 minutes

Notes

not defined yet

Code: 01:42:10 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A, int[] B) {
        // write your code in Java SE 8
    }
}

Code: 01:42:35 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B):
    # write your code in Python 3.6
    pass

Code: 01:43:43 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B):
    # write your code in Python 3
    pass

Code: 01:43:50 UTC, py, verify, result: Passed

show code in pop-up

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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B):
    count_height = {}
    max_count = 0
    i = 0
    while i < len(A):
        if A[i] == B[i] and A[i] not in count_height:
            count_height[A[i]] = 1
            if count_height[A[i]] > max_count:
                max_count = count_height[A[i]]
        elif A[i] == B[i] and A[i] in count_height:
            count_height[A[i]] += 1
            if count_height[A[i]] > max_count:
                max_count = count_height[A[i]]
        else:
            if A[i] not in count_height and B[i] not in count_height:
                count_height[A[i]] = 1
                count_height[B[i]] = 1
            elif A[i] not in count_height and B[i] in count_height:
                count_height[A[i]] = 1
                count_height[B[i]] += 1
            elif A[i] in count_height and B[i] not in count_height:
                count_height[A[i]] += 1
                count_height[B[i]] = 1
            elif A[i] in count_height and B[i] in count_height:
                count_height[A[i]] += 1
                count_height[B[i]] += 1
            if max(count_height[A[i]], count_height[B[i]]) > max_count:
                max_count = max(count_height[A[i]], count_height[B[i]])
        i += 1
    return max_count
    pass

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.036 s

▶

example2
Second example test.

✔

0.036 s

▶

example3
Third example test.

✔

0.036 s

Code: 01:43:57 UTC, py, verify, result: Passed

show code in pop-up

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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B):
    count_height = {}
    max_count = 0
    i = 0
    while i < len(A):
        if A[i] == B[i] and A[i] not in count_height:
            count_height[A[i]] = 1
            if count_height[A[i]] > max_count:
                max_count = count_height[A[i]]
        elif A[i] == B[i] and A[i] in count_height:
            count_height[A[i]] += 1
            if count_height[A[i]] > max_count:
                max_count = count_height[A[i]]
        else:
            if A[i] not in count_height and B[i] not in count_height:
                count_height[A[i]] = 1
                count_height[B[i]] = 1
            elif A[i] not in count_height and B[i] in count_height:
                count_height[A[i]] = 1
                count_height[B[i]] += 1
            elif A[i] in count_height and B[i] not in count_height:
                count_height[A[i]] += 1
                count_height[B[i]] = 1
            elif A[i] in count_height and B[i] in count_height:
                count_height[A[i]] += 1
                count_height[B[i]] += 1
            if max(count_height[A[i]], count_height[B[i]]) > max_count:
                max_count = max(count_height[A[i]], count_height[B[i]])
        i += 1
    return max_count
    pass

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.036 s

▶

example2
Second example test.

✔

0.036 s

▶

example3
Third example test.

✔

0.036 s

Code: 01:44:00 UTC, py, final, score: 100

show code in pop-up

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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B):
    count_height = {}
    max_count = 0
    i = 0
    while i < len(A):
        if A[i] == B[i] and A[i] not in count_height:
            count_height[A[i]] = 1
            if count_height[A[i]] > max_count:
                max_count = count_height[A[i]]
        elif A[i] == B[i] and A[i] in count_height:
            count_height[A[i]] += 1
            if count_height[A[i]] > max_count:
                max_count = count_height[A[i]]
        else:
            if A[i] not in count_height and B[i] not in count_height:
                count_height[A[i]] = 1
                count_height[B[i]] = 1
            elif A[i] not in count_height and B[i] in count_height:
                count_height[A[i]] = 1
                count_height[B[i]] += 1
            elif A[i] in count_height and B[i] not in count_height:
                count_height[A[i]] += 1
                count_height[B[i]] = 1
            elif A[i] in count_height and B[i] in count_height:
                count_height[A[i]] += 1
                count_height[B[i]] += 1
            if max(count_height[A[i]], count_height[B[i]]) > max_count:
                max_count = max(count_height[A[i]], count_height[B[i]])
        i += 1
    return max_count
    pass

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*log(N)) or O(N)

expand all Example tests

▶

example1
First example test.

✔

0.040 s

▶

example2
Second example test.

✔

0.040 s

▶

example3
Third example test.

✔

0.040 s

expand all Correctness tests

▶

common_side_from_A
No rotations needed. Common side can be chosen from A. N = 15.

✔

0.040 s

▶

common_side_from_B
No rotations needed. Common side can be chosen from B. N = 15.

✔

0.040 s

▶

A_less_than_B
Array A contains shorter sides. N = 15.

✔

0.040 s

▶

A_greater_than_B
Array A contains longer sides. N = 15.

✔

0.040 s

▶

only_squares
All rectangles are squares. N = 15.

✔

0.040 s

▶

no_squares
Rectangles are not squares. N = 15.

✔

0.040 s

expand all Correctness/performance tests

▶

corners
N <= 2.

✔

0.040 s

▶

medium_common_side_from_A
No rotations needed. Common side can be chosen from A. N = 200.

✔

0.040 s

▶

medium_common_side_from_B
No rotations needed. Common side can be chosen from B. N = 200.

✔

0.040 s

▶

medium_A_less_than_B
"Array A contains shorter sides. N = 200.

✔

0.040 s

0.044 s

▶

medium_A_greater_than_B
Array A contains longer sides. N = 200.

✔

0.040 s

▶

medium_only_squares
All rectangles are squares. N = 200.

✔

0.040 s

expand all Performance tests

▶

large_common_side_from_A
No rotations needed. Common side can be chosen from A. N = 100,000.

✔

0.380 s

0.376 s

▶

large_common_side_from_B
No rotations needed. Common side can be chosen from B. N = 100,000.

✔

0.368 s

0.376 s

0.372 s

▶

large_A_less_than_B
Array A contains shorter sides. N = 100,000. Points x 2.

✔

0.328 s

0.376 s

0.384 s

▶

large_A_greater_than_B
Array A contains longer sides. N = 100,000. Points x 2.

✔

0.368 s

0.384 s

0.364 s

0.376 s

▶

large_only_squares
All rectangles are squares. N = 100,000. Points x 2.

✔

0.376 s

0.380 s