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:

class Solution { public int solution(String 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 Java 8

Time spent on task 17 minutes

Notes

not defined yet

Code: 13:47:21 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: 13:48:06 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7

import java.util.*;

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
    }
}

Code: 13:48:37 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

import java.util.*;

class Solution {
    public int solution(String S) {
        for (char i=0; i<S.length; i++) {
            S.charAt(i);
        }
    }
}

Code: 13:49:57 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

import java.util.*;

class Solution {
    public int solution(String S) {
        for (char i=0; i<S.length; i++) {
        S.charAt(i);
        }
    }
}

Code: 13:50:10 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

import java.util.*;

class Solution {
    public int solution(String S) {
        for (char i=0; i<S.length; i++) {
            char i = S.charAt(i);
        }
    }
}

Code: 13:50:21 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<
        for (char i=0; i<S.length; i++) {
            char i = S.charAt(i);
        }
    }
}

Code: 13:50:31 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        
        for (char i=0; i<S.length; i++) {
            char i = S.charAt(i);
        }
    }
}

Code: 13:50:44 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        
        for (char i=0; i<S.length; i++) {
            stack.push(S.charAt(i));
        }
    }
}

Code: 13:51:12 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            stack.push(S.charAt(i));
        }
    }
}

Code: 13:51:41 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if ()
            stack.push(S.charAt(i));
        }
    }
}

Code: 13:51:52 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i)
            stack.push(S.charAt(i));
        }
    }
}

Code: 13:52:11 UTC, java, autosave

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                
            }
        }
    }
}

Code: 13:52:21 UTC, java, autosave

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
               
            }
        }
    }
}

Code: 13:52:33 UTC, java, autosave

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                stack.pop();              
            }
        }
    }
}

Code: 13:54:44 UTC, java, autosave

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                stack.pop();    
            }
        }
    }
}

Code: 13:54:53 UTC, java, autosave

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                stack.peek();
            }
        }
    }
}

Code: 13:55:24 UTC, java, 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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return 0;
                } else {
                    .peek();   
                }
            }
        }
        
        
    }
}

Code: 13:55:39 UTC, java, 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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return 0;
                } else {
                    .peek();   
                }
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Code: 13:58:33 UTC, java, 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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return 0;
                } else {
                    sta.peek();   
                }
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Code: 13:58:43 UTC, java, 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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return 0;
                } else if () {
                    stack.pop();   
                }
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Code: 13:59:06 UTC, java, 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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return 0;
                } else {
                    stack.pop();   
                }
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Code: 13:59:38 UTC, java, 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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return 0;
                } else {
                    if (')' != stack.pop()) {
                        return 0;    
                    }
                }
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Code: 13:59:48 UTC, java, 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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else {
                if (stack.isEmpty() || ')' != stack.pop()) {
                    return 0;
                } else {
                    if () {
                        return 0;    
                    }
                }
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Code: 14:00:04 UTC, java, verify, result: Failed

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || ')' != stack.pop())
                return 0;
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Analysis

Compile error

Solution.java:14: error: illegal start of type
        return stack.isEmpty() ? 0 : 1;
        ^
Solution.java:14: error: ';' expected
        return stack.isEmpty() ? 0 : 1;
              ^
Solution.java:14: error: illegal start of type
        return stack.isEmpty() ? 0 : 1;
                    ^
Solution.java:14: error: ';' expected
        return stack.isEmpty() ? 0 : 1;
                              ^
Solution.java:16: error: class, interface, or enum expected
}
^
5 errors

Code: 14:00:40 UTC, java, autosave

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || ')' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Code: 14:00:42 UTC, java, verify, result: Failed

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (char i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || ')' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Analysis

Compile error

Solution.java:6: error: cannot find symbol
        for (char i=0; i<S.length; i++) {
                          ^
  symbol:   variable length
  location: variable S of type String
1 error

Code: 14:00:54 UTC, java, verify, result: Failed

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || ')' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Analysis

Compile error

Solution.java:6: error: cannot find symbol
        for (int i=0; i<S.length; i++) {
                         ^
  symbol:   variable length
  location: variable S of type String
1 error

Code: 14:01:13 UTC, java, autosave

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || ')' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Code: 14:01:13 UTC, java, verify, result: Failed

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || ')' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 0 : 1;
    }
}

Analysis

expand all Example tests

▶

example1
example test

✘

WRONG ANSWER
got 0 expected 1

0.008 s

WRONG ANSWER, got 0 expected 1

▶

example2
example test2

✔

0.008 s

Code: 14:02:55 UTC, java, autosave

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || ')' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 1 : 1;
    }
}

Code: 14:02:58 UTC, java, verify, result: Failed

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || ')' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}

Analysis

expand all Example tests

▶

example1
example test

✘

WRONG ANSWER
got 0 expected 1

0.004 s

WRONG ANSWER, got 0 expected 1

▶

example2
example test2

✔

0.004 s

Code: 14:03:04 UTC, java, verify, result: Failed

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || ')' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}

Analysis

expand all Example tests

▶

example1
example test

✘

WRONG ANSWER
got 0 expected 1

0.004 s

WRONG ANSWER, got 0 expected 1

▶

example2
example test2

✔

0.004 s

Code: 14:03:27 UTC, java, autosave

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || '(' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}

Code: 14:03:28 UTC, java, verify, result: Passed

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || '(' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}

Analysis

expand all Example tests

▶

example1
example test

✔

0.008 s

▶

example2
example test2

✔

0.004 s

Code: 14:03:33 UTC, java, verify, result: Passed

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || '(' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

▶

example2
example test2

✔

0.004 s

Code: 14:03:38 UTC, java, final, score: 100

show code in pop-up

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

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || '(' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example1
example test

✔

0.008 s

▶

example2
example test2

✔

0.004 s

expand all Correctness tests

▶

negative_match
invalid structure, but the number of parentheses matches

✔

0.004 s

▶

empty
empty string

✔

0.008 s

▶

simple_grouped
simple grouped positive and negative test, length=22

✔

0.008 s

0.004 s

▶

small_random

✔

0.004 s

expand all Performance tests

▶

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

✔

0.028 s

0.004 s

▶

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

✔

0.228 s

0.004 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.068 s

0.004 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

✔

1.260 s

0.004 s