Test results - Codility

Tasks Details

easy

1. Brackets

Determine whether a given string of parentheses (multiple types) is properly nested.

Task Score

100%

Correctness

100%

Performance

100%

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

S is empty;

S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;

S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

def solution(S)

that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.

For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..200,000];

string S is made only of the following characters: '(', '{', '[', ']', '}' and/or ')'.

Solution

Programming language used Python

Total time used 17 minutes

Effective time used 17 minutes

Notes

not defined yet

Task timeline

Code: 08:32:46 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(String S) {
        // write your code in Java SE 8
    }
}

Code: 08:32:54 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(S):
    # write your code in Python 3.6
    pass

Code: 08:33:03 UTC, py, autosave

show code in pop-up

1 2 3 4 5

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

def solution(S):

Code: 08:39:59 UTC, py, autosave

show code in pop-up

1 2 3 4 5

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

def solution(S):
    s

Code: 08:40:18 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(S):
    stack = [0]*len(S)

Code: 08:40:47 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7

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

def solution(S):
    stack = [0]*len(S)
    for i in xrange(len(S))
        print(i)

Code: 08:40:50 UTC, py, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7

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

def solution(S):
    stack = [0]*len(S)
    for i in xrange(len(S))
        print(i)

Analysis

expand all Example tests

▶

example1
example test 1

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Traceback (most recent call last):
  File "exec.py", line 123, in <module>
    main()
  File "exec.py", line 64, in main
    sol = __import__('solution')
  File "/tmp/solution.py", line 6
    for i in xrange(len(S))
                          ^
SyntaxError: invalid syntax

▶

example2
example test 2

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.040 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Traceback (most recent call last):
  File "exec.py", line 123, in <module>
    main()
  File "exec.py", line 64, in main
    sol = __import__('solution')
  File "/tmp/solution.py", line 6
    for i in xrange(len(S))
                          ^
SyntaxError: invalid syntax

Code: 08:40:57 UTC, py, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7

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

def solution(S):
    stack = [0]*len(S)
    for i in xrange(len(S)):
        print(i)

Analysis

expand all Example tests

▶

example1
example test 1

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Traceback (most recent call last):
  File "exec.py", line 123, in <module>
    main()
  File "exec.py", line 85, in main
    result = solution( S )
  File "/tmp/solution.py", line 6, in solution
    for i in xrange(len(S)):
NameError: name 'xrange' is not defined

▶

example2
example test 2

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Traceback (most recent call last):
  File "exec.py", line 123, in <module>
    main()
  File "exec.py", line 85, in main
    result = solution( S )
  File "/tmp/solution.py", line 6, in solution
    for i in xrange(len(S)):
NameError: name 'xrange' is not defined

Code: 08:41:34 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7

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

def solution(S):
    stack = [0]*len(S)
    for i in range(len(S)):
        print(i)

Code: 08:41:36 UTC, py, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7

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

def solution(S):
    stack = [0]*len(S)
    for i in range(len(S)):
        print(i)

Analysis

expand all Example tests

▶

example1
example test 1

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, int expected, <class 'NoneType'> found.

stdout:

▶

example2
example test 2

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, int expected, <class 'NoneType'> found.

stdout:

Code: 08:41:50 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

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

def solution(S):
    
    stack = [0]*len(S)
    
    for i in range(len(S)):

Code: 08:42:05 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

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

def solution(S):
    
    stack = [0]*len(S)
    
    for i in range(len(S)):
        if S[i] is ""

Code: 08:42:16 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

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

def solution(S):
    
    stack = [0]*len(S)
    
    for i in range(len(S)):
        if S[i] is "("

Code: 08:42:26 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

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

def solution(S):
    
    stack = [0]*len(S)
    
    for i in range(len(S)):
        if S[i] is "(" or

Code: 08:42:56 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            st

Code: 08:43:25 UTC, py, autosave

show code in pop-up

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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1

Code: 08:43:36 UTC, py, autosave

show code in pop-up

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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else

Code: 08:44:07 UTC, py, autosave

show code in pop-up

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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else:
            if S[i] is ")" and stack[-1]

Code: 08:44:20 UTC, py, autosave

show code in pop-up

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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else:
            if S[i] is ")" and stack[size-1] is ""

Code: 08:44:34 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size 
            if S[i] is ")" and stack[size-1] is ""

Code: 08:44:47 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0
                return 
            if S[i] is ")" and stack[size-1] is ""

Code: 08:44:57 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            if S[i] is ")" and stack[size-1] is ""

Code: 08:45:07 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is ""

Code: 08:45:18 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "("
                size -=1

Code: 08:45:28 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif

Code: 08:45:40 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is

Code: 08:46:11 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "{" and stack[size-1]

Code: 08:46:24 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "}" and stack[size-1] is ""

Code: 08:46:54 UTC, py, autosave

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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "}" and stack[size-1] is "{":
                size -=1
            elif S[i] is "]" and stack[size-1] is

Code: 08:47:10 UTC, py, autosave

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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "}" and stack[size-1] is "{":
                size -=1
            elif S[i] is "]" and stack[size-1] is "[":
                size -=1

Code: 08:47:41 UTC, py, autosave

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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "}" and stack[size-1] is "{":
                size -=1
            elif S[i] is "]" and stack[size-1] is "[":
                size -=1
    
    if size is 0
        return 1
    
    return

Code: 08:47:47 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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "}" and stack[size-1] is "{":
                size -=1
            elif S[i] is "]" and stack[size-1] is "[":
                size -=1
    
    if size is 0:
        return 1
    
    return 0

Analysis

expand all Example tests

▶

example1
example test 1

✔

0.036 s

▶

example2
example test 2

✔

0.036 s

Code: 08:48:17 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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "}" and stack[size-1] is "{":
                size -=1
            elif S[i] is "]" and stack[size-1] is "[":
                size -=1
    
    if size is 0:
        return 1
    
    return 0

User test case 1:

((()()()))

Analysis

expand all Example tests

▶

example1
example test 1

✔

0.036 s

▶

example2
example test 2

✔

0.036 s

expand all User tests

▶

test_data1

✘

RUNTIME ERROR
invalid input, unexpected '(', expecting string

0.001 s

RUNTIME ERROR, invalid input, unexpected '(', expecting string

Code: 08:48:30 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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "}" and stack[size-1] is "{":
                size -=1
            elif S[i] is "]" and stack[size-1] is "[":
                size -=1
    
    if size is 0:
        return 1
    
    return 0

User test case 1:

['((()()()))']

Analysis

expand all Example tests

▶

example1
example test 1

✔

0.048 s

▶

example2
example test 2

✔

0.056 s

expand all User tests

▶

test_data1

✔

0.048 s

OK
function result: 1

Code: 08:48:48 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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "}" and stack[size-1] is "{":
                size -=1
            elif S[i] is "]" and stack[size-1] is "[":
                size -=1
    
    if size is 0:
        return 1
    
    return 0

User test case 1:

['((()()()))']

Analysis

expand all Example tests

▶

example1
example test 1

✔

0.036 s

▶

example2
example test 2

✔

0.036 s

expand all User tests

▶

test_data1

✔

0.036 s

OK
function result: 1

Code: 08:48:50 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

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

def solution(S):
    
    stack = [0]*len(S)
    size = 0
    
    for i in range(len(S)):
        if S[i] is "(" or S[i] is "{" or S[i] is "[":
            stack[size] = S[i]
            size += 1
        else: 
            if size is 0:
                return 0
            elif S[i] is ")" and stack[size-1] is "(":
                size -=1
            elif S[i] is "}" and stack[size-1] is "{":
                size -=1
            elif S[i] is "]" and stack[size-1] is "[":
                size -=1
    
    if size is 0:
        return 1
    
    return 0

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example1
example test 1

✔

0.036 s

▶

example2
example test 2

✔

0.036 s

expand all Correctness tests

▶

negative_match
invalid structures

✔

0.036 s

▶

empty
empty string

✔

0.036 s

▶

simple_grouped
simple grouped positive and negative test, length=22

✔

0.036 s

expand all Performance tests

▶

large1
simple large positive test, 100K ('s followed by 100K )'s + )(

✔

0.088 s

0.036 s

0.040 s

▶

large2
simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()

✔

0.040 s

0.036 s

▶

large_full_ternary_tree
tree of the form T=(TTT) and depth 11, length=177K+

✔

0.080 s

▶

multiple_full_binary_trees
sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+

✔

0.048 s

0.068 s

0.048 s

0.036 s

▶

broad_tree_with_deep_paths
string of the form [TTT...T] of 300 T's, each T being '{{{...}}}' nested 200-fold, length=120K+

✔

0.068 s