Test results - Codility

Tasks Details

easy

1. Nesting

Determine whether a given string of parentheses (single type) is properly nested.

Task Score

100%

Correctness

100%

Performance

100%

A string S consisting of N characters is called properly nested if:

S is empty;

S has the form "(U)" where U is a properly nested string;

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

For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

def solution(S)

that, given a string S consisting of N characters, returns 1 if string 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..1,000,000];

string S is made only of the characters '(' and/or ')'.

Solution

Programming language used Python

Time spent on task 10 minutes

Notes

not defined yet

Code: 16:50:22 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: 16:50:46 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: 16:51:04 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

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

def solution(S):
    
    stack = []

Code: 16:51:18 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

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

def solution(S):
    
    
    stack = []

Code: 16:51:37 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

Code: 16:51:49 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):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if

Code: 16:52:10 UTC, py, autosave

show code in pop-up

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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():

Code: 16:52:44 UTC, py, autosave

show code in pop-up

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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack

Code: 16:52:55 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):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)

Code: 16:53:20 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):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif

Code: 16:53:39 UTC, py, autosave

show code in pop-up

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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s == nest[s]:
            stack.pop()

Code: 16:54: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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s == nest[s]:
            stack.pop()
    
    if len(s)

Code: 16:54:28 UTC, py, 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s == nest[s]:
            stack.pop()
    
    if not stack:
        return 1
    else:
        return 0

Analysis

expand all Example tests

▶

example1
example test

✘

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 12, in solution
    elif s == nest[s]:
KeyError: ')'

▶

example2
example test2

✘

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 12, in solution
    elif s == nest[s]:
KeyError: ')'

Code: 16:55:48 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s == nest[s]:
            
            stack.pop()
    
    if not stack:
        return 1
    else:
        return 0

Code: 16:55:50 UTC, py, 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s == nest[s]:
            print(s)
            stack.pop()
    
    if not stack:
        return 1
    else:
        return 0

Analysis

expand all Example tests

▶

example1
example test

✘

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 85, in main
    result = solution( S )
  File "/tmp/solution.py", line 12, in solution
    elif s == nest[s]:
KeyError: ')'

▶

example2
example test2

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.044 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 12, in solution
    elif s == nest[s]:
KeyError: ')'

Code: 16:56:50 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s == nest.k:
            print(s)
            stack.pop()
    
    if not stack:
        return 1
    else:
        return 0

Code: 16:56:59 UTC, py, 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            print(s)
            stack.pop()
    
    if not stack:
        return 1
    else:
        return 0

Analysis

expand all Example tests

▶

example1
example test

✔

0.036 s

stdout:

)
)
)
)
)

▶

example2
example test2

✘

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 14, in solution
    stack.pop()
IndexError: pop from empty list

stdout:

)
)

Code: 16:57:03 UTC, py, 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            stack.pop()
    
    if not stack:
        return 1
    else:
        return 0

Analysis

expand all Example tests

▶

example1
example test

✔

0.036 s

▶

example2
example test2

✘

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 85, in main
    result = solution( S )
  File "/tmp/solution.py", line 13, in solution
    stack.pop()
IndexError: pop from empty list

Code: 16:57:21 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):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            stack.pop()
        else:
            
    
    if not stack:
        return 1
    else:
        return 0

Code: 16:57:44 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):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                
        
    
    if not stack:
        return 1
    else:
        return 0

Code: 16:57:53 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

Analysis

expand all Example tests

▶

example1
example test

✔

0.036 s

▶

example2
example test2

✔

0.036 s

Code: 16:58:08 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

User test case 1:

['']

User test case 2:

['vv']

User test case 3:

[')(']

Analysis

expand all Example tests

▶

example1
example test

✔

0.036 s

▶

example2
example test2

✔

0.036 s

expand all User tests

▶

test_data1

✔

0.036 s

OK
function result: 1

▶

test_data2

✔

0.036 s

OK
function result: 1

▶

test_data3

✔

0.036 s

OK
function result: 0

Code: 16:58:42 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

Code: 16:58: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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

User test case 1:

['']

User test case 2:

['vv']

User test case 3:

[')(']

User test case 4:

[')']

User test case 5:

['(']

Analysis

expand all Example tests

▶

example1
example test

✔

0.036 s

▶

example2
example test2

✔

0.036 s

expand all User tests

▶

test_data1

✔

0.036 s

OK
function result: 1

▶

test_data2

✔

0.036 s

OK
function result: 1

▶

test_data3

✔

0.044 s

OK
function result: 0

▶

test_data4

✔

0.036 s

OK
function result: 0

▶

test_data5

✔

0.036 s

OK
function result: 0

Code: 16:59:02 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

User test case 1:

['']

User test case 2:

['vv']

User test case 3:

[')(']

User test case 4:

[')']

User test case 5:

['(']

User test case 6:

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

Analysis

expand all Example tests

▶

example1
example test

✔

0.036 s

▶

example2
example test2

✔

0.036 s

expand all User tests

▶

test_data1

✔

0.036 s

OK
function result: 1

▶

test_data2

✔

0.036 s

OK
function result: 1

▶

test_data3

✔

0.036 s

OK
function result: 0

▶

test_data4

✔

0.036 s

OK
function result: 0

▶

test_data5

✔

0.036 s

OK
function result: 0

▶

test_data6

✔

0.036 s

OK
function result: 0

Code: 16:59:12 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

Code: 16:59:19 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

User test case 1:

['']

User test case 2:

['vv']

User test case 3:

[')(']

User test case 4:

[')']

User test case 5:

['(']

User test case 6:

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

User test case 7:

['vv()vvvs(vv)']

Analysis

expand all Example tests

▶

example1
example test

✔

0.036 s

▶

example2
example test2

✔

0.036 s

expand all User tests

▶

test_data1

✔

0.036 s

OK
function result: 1

▶

test_data2

✔

0.036 s

OK
function result: 1

▶

test_data3

✔

0.036 s

OK
function result: 0

▶

test_data4

✔

0.036 s

OK
function result: 0

▶

test_data5

✔

0.036 s

OK
function result: 0

▶

test_data6

✔

0.036 s

OK
function result: 0

▶

test_data7

✔

0.036 s

OK
function result: 1

Code: 16:59:27 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

User test case 1:

['']

User test case 2:

['vv']

User test case 3:

[')(']

User test case 4:

[')']

User test case 5:

['(']

User test case 6:

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

User test case 7:

['vv()vvvs(vv))']

Analysis

expand all Example tests

▶

example1
example test

✔

0.036 s

▶

example2
example test2

✔

0.036 s

expand all User tests

▶

test_data1

✔

0.040 s

OK
function result: 1

▶

test_data2

✔

0.036 s

OK
function result: 1

▶

test_data3

✔

0.036 s

OK
function result: 0

▶

test_data4

✔

0.036 s

OK
function result: 0

▶

test_data5

✔

0.036 s

OK
function result: 0

▶

test_data6

✔

0.036 s

OK
function result: 0

▶

test_data7

✔

0.036 s

OK
function result: 0

Code: 16:59:35 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

User test case 1:

['']

User test case 2:

['vv']

User test case 3:

[')(']

User test case 4:

[')']

User test case 5:

['(']

User test case 6:

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

User test case 7:

['vv()vvvs(vv))']

Analysis

expand all Example tests

▶

example1
example test

✔

0.036 s

▶

example2
example test2

✔

0.036 s

expand all User tests

▶

test_data1

✔

0.036 s

OK
function result: 1

▶

test_data2

✔

0.036 s

OK
function result: 1

▶

test_data3

✔

0.036 s

OK
function result: 0

▶

test_data4

✔

0.036 s

OK
function result: 0

▶

test_data5

✔

0.036 s

OK
function result: 0

▶

test_data6

✔

0.036 s

OK
function result: 0

▶

test_data7

✔

0.036 s

OK
function result: 0

Code: 16:59:38 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

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

def solution(S):
    
    nest = {"(":")"}
    stack = []

    for s in S:
        if s in nest.keys():
            stack.append(s)
        elif s in nest.values():
            if stack:
                stack.pop()
            else:
                return 0        
    
    if not stack:
        return 1
    else:
        return 0

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example1
example test

✔

0.036 s

▶

example2
example test2

✔

0.036 s

expand all Correctness tests

▶

negative_match
invalid structure, but the number of parentheses matches

✔

0.036 s

▶

empty
empty string

✔

0.036 s

▶

simple_grouped
simple grouped positive and negative test, length=22

✔

0.036 s

▶

small_random

✔

0.036 s

expand all Performance tests

▶

large1
simple large positive and negative test, 10K or 10K+1 ('s followed by 10K )'s

✔

0.044 s

0.036 s

▶

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

✔

0.096 s

0.036 s

▶

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

✔

0.052 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=1 million

✔

0.344 s

0.036 s