Test results - Codility

Tasks Details

medium

1. RectanglesStrip

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

Task Score

60%

Correctness

100%

Performance

27%

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:

func Solution(A []int, B []int) int

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 Go

Time spent on task 19 minutes

Notes

not defined yet

Code: 13:58:49 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: 13:59:03 UTC, go, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

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

func Solution(A []int, B []int) int {
    // write your code in Go 1.4
}

Code: 14:16:57 UTC, go, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

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

func Solution(A []int, B []int) int {
}

Code: 14:17:04 UTC, go, verify, result: Failed

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

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

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

func Solution(A []int, B []int) int {
    	s := make(map[int]bool)
	for _, v := range A {
		s[v] = true
	}
	for _, v := range B {
		s[v] = true
	}

	maxMatch := 0
	for n, _ := range s {
		match := 0
		for i, _ := range A {
			if A[i] == n || B[i] == n {
				match += 1
			}
		}
		maxMatch = max(maxMatch, match)
	}

	return maxMatch
}

Analysis

Compile error

# solution
workspace/src/solution/solution.go:27: undefined: max

Code: 14:17:25 UTC, go, 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 35 36 37 38

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func Solution(A []int, B []int) int {
    	s := make(map[int]bool)
	for _, v := range A {
		s[v] = true
	}
	for _, v := range B {
		s[v] = true
	}

	maxMatch := 0
	for n, _ := range s {
		match := 0
		for i, _ := range A {
			if A[i] == n || B[i] == n {
				match += 1
			}
		}
		maxMatch = max(maxMatch, match)
	}

	return maxMatch
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.001 s

▶

example2
Second example test.

✔

0.001 s

▶

example3
Third example test.

✔

0.001 s

Code: 14:17:29 UTC, go, 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 35 36 37 38

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func Solution(A []int, B []int) int {
    	s := make(map[int]bool)
	for _, v := range A {
		s[v] = true
	}
	for _, v := range B {
		s[v] = true
	}

	maxMatch := 0
	for n, _ := range s {
		match := 0
		for i, _ := range A {
			if A[i] == n || B[i] == n {
				match += 1
			}
		}
		maxMatch = max(maxMatch, match)
	}

	return maxMatch
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.001 s

▶

example2
Second example test.

✔

0.001 s

▶

example3
Third example test.

✔

0.001 s

Code: 14:17:32 UTC, go, final, score: 60

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 35 36 37 38

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func Solution(A []int, B []int) int {
    	s := make(map[int]bool)
	for _, v := range A {
		s[v] = true
	}
	for _, v := range B {
		s[v] = true
	}

	maxMatch := 0
	for n, _ := range s {
		match := 0
		for i, _ := range A {
			if A[i] == n || B[i] == n {
				match += 1
			}
		}
		maxMatch = max(maxMatch, match)
	}

	return maxMatch
}

Analysis summary

The following issues have been detected: timeout errors.

Analysis

Detected time complexity:

O(N**2)

expand all Example tests

▶

example1
First example test.

✔

0.001 s

▶

example2
Second example test.

✔

0.001 s

▶

example3
Third example test.

✔

0.001 s

expand all Correctness tests

▶

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

✔

0.001 s

▶

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

✔

0.001 s

▶

A_less_than_B
Array A contains shorter sides. N = 15.

✔

0.001 s

▶

A_greater_than_B
Array A contains longer sides. N = 15.

✔

0.001 s

▶

only_squares
All rectangles are squares. N = 15.

✔

0.001 s

▶

no_squares
Rectangles are not squares. N = 15.

✔

0.001 s

expand all Correctness/performance tests

▶

corners
N <= 2.

✔

0.001 s

▶

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

✔

0.001 s

▶

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

✔

0.001 s

▶

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

✔

0.001 s

▶

medium_A_greater_than_B
Array A contains longer sides. N = 200.

✔

0.001 s

▶

medium_only_squares
All rectangles are squares. N = 200.

✔

0.001 s

expand all Performance tests

▶

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

✘

TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.

6.000 s