Test results - Codility

Tasks Details

easy

1. StrSymmetryPoint

Find a symmetry point of a string, if any.

Task Score

100%

Correctness

100%

Performance

100%

Write a function:

def solution(S)

that, given a string S, returns the index (counting from 0) of a character such that the part of the string to the left of that character is a reversal of the part of the string to its right. The function should return −1 if no such index exists.

Note: reversing an empty string (i.e. a string whose length is zero) gives an empty string.

For example, given a string:

"racecar"

the function should return 3, because the substring to the left of the character "e" at index 3 is "rac", and the one to the right is "car".

Given a string:

"x"

the function should return 0, because both substrings are empty.

Write an efficient algorithm for the following assumptions:

the length of string S is within the range [0..2,000,000].

Solution

Programming language used Python

Time spent on task 9 minutes

Notes

not defined yet

Task timeline

Code: 15:07:48 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: 15:08:05 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):
    
    if len(S)//2 == 0:
        return -1

Analysis

expand all Example tests

▶

example1
first example

✘

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.

▶

example2
second example

✘

WRONG ANSWER
got -1 expected 0

0.036 s

WRONG ANSWER, got -1 expected 0

Code: 15:08:26 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):
    
    if len(S)%2 == 0:
        return -1

Code: 15:08:32 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):
    
    if len(S)%2 == 1:
        return -1

Analysis

expand all Example tests

▶

example1
first example

✘

WRONG ANSWER
got -1 expected 3

0.036 s

WRONG ANSWER, got -1 expected 3

▶

example2
second example

✘

WRONG ANSWER
got -1 expected 0

0.036 s

WRONG ANSWER, got -1 expected 0

Code: 15:08:57 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

Code: 15:09:05 UTC, py, verify, result: Failed

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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

    print(mid)

Analysis

expand all Example tests

▶

example1
first example

✘

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
second example

✘

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: 15:09:21 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

Code: 15:14:17 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

Code: 15:14:49 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

    c

Code: 15:14:59 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

Code: 15:15: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

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

def solution(S):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

    start = 0
    end = -1

    while start < mid:

Code: 15:15:51 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

    start = 0
    end = -1

    while start < mid:
        if S[start] != S[end]:
            return

Code: 15:16:08 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

    start = 0
    end = -1

    while start < mid:
        if S[start] != S[end]:
            return -1
        start += 1 
        end -= 1

Code: 15:16:20 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

    start = 0
    end = -1

    while start < mid:
        if S[start] != S[end]:
            return -1
        start += 1 
        end -= 1

    return mid

Analysis

expand all Example tests

▶

example1
first example

✔

0.036 s

▶

example2
second example

✔

0.040 s

Code: 15:16:25 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

    start = 0
    end = -1

    while start < mid:
        if S[start] != S[end]:
            return -1
        start += 1 
        end -= 1

    return mid

Analysis

expand all Example tests

▶

example1
first example

✔

0.036 s

▶

example2
second example

✔

0.036 s

Code: 15:16:28 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):
    
    if len(S)%2 == 0:
        return -1

    mid = len(S)//2

    start = 0
    end = -1

    while start < mid:
        if S[start] != S[end]:
            return -1
        start += 1 
        end -= 1

    return mid

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(length(S))

expand all Example tests

▶

example1
first example

✔

0.036 s

▶

example2
second example

✔

0.036 s

expand all Correctness tests

▶

extreme_empty_or_one
empty or one character strings

✔

0.036 s

▶

symmetric
short symmetric strings

✔

0.036 s

▶

even
even length or symmetric strings

✔

0.036 s

▶

three_chars
3 characters (multiple runs)

✔

0.036 s

▶

letters_a
letters 'a' only

✔

0.036 s

▶

alphabet_symmetric
nontrivial symmetry, N = 51

✔

0.036 s

▶

nonsymmetric_inside
mismatch close to the middle, N = 43

✔

0.036 s

0.044 s

▶

nonsymmetric_outside
mismatch close to the ends, N = 43

✔

0.036 s

expand all Performance tests

▶

large_nonsymmetric
nonsymmetric string, N = 100k+ + [aba]

✔

0.044 s

0.036 s

▶

large_symmetric1
symmetric string, N=100k

✔

0.044 s

▶

large_symmetric2
symmetric string, N=200k

✔

0.052 s

▶

big_symmetric3
symmetric string, N=1M+

✔

0.120 s

▶

big_nonsymmetric
nonsymmetric string, N = ~1M

✔

0.120 s

0.040 s

0.036 s

▶

extreme_size
N = ~2M

✔

0.200 s

0.040 s

0.204 s

0.040 s

0.200 s