Test results - Codility

Tasks Details

easy

1. StrSymmetryPoint

Find a symmetry point of a string, if any.

57%

100%

Write a function:

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

Time spent on task 16 minutes

Notes

not defined yet

Task timeline

Code: 06:38:06 UTC, swift4, verify, result: Passed

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

import Foundation
import Glibc

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

public func solution(_ S : inout String) -> Int {
    var tempLeft = ""
    var tempRight = String(S.reversed())
    
    for (idx, i) in S.enumerated() {
        tempRight.popLast()
        
        if tempLeft == tempRight {
            return idx
        }
        
        tempLeft += String(i)
    }
    
    return -1
}

Analysis

▶

example1
first example

✔

▶

example2
second example

✔

Code: 06:38:17 UTC, swift4, verify, result: Passed

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

import Foundation
import Glibc

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

public func solution(_ S : inout String) -> Int {
    var tempLeft = ""
    var tempRight = String(S.reversed())
    
    for (idx, i) in S.enumerated() {
        tempRight.popLast()
        
        if tempLeft == tempRight {
            return idx
        }
        
        tempLeft += String(i)
    }
    
    return -1
}

Analysis

▶

example1
first example

✔

▶

example2
second example

✔

Code: 06:38:23 UTC, swift4, final, score: 57

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

import Foundation
import Glibc

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

public func solution(_ S : inout String) -> Int {
    var tempLeft = ""
    var tempRight = String(S.reversed())
    
    for (idx, i) in S.enumerated() {
        tempRight.popLast()
        
        if tempLeft == tempRight {
            return idx
        }
        
        tempLeft += String(i)
    }
    
    return -1
}

Analysis summary

The following issues have been detected: timeout errors.

Analysis

Detected time complexity:

O(length(S)**2)

▶

example1
first example

✔

▶

example2
second example

✔

▶

extreme_empty_or_one
empty or one character strings

✔

▶

symmetric
short symmetric strings

✔

▶

even
even length or symmetric strings

✔

▶

three_chars
3 characters (multiple runs)

✔

▶

letters_a
letters 'a' only

✔

▶

alphabet_symmetric
nontrivial symmetry, N = 51

✔

▶

nonsymmetric_inside
mismatch close to the middle, N = 43

✔

▶

nonsymmetric_outside
mismatch close to the ends, N = 43

✔

▶

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

✘

TIMEOUT ERROR
running time: 1.232 sec., time limit: 0.100 sec.

▶

large_symmetric1
symmetric string, N=100k

✘

TIMEOUT ERROR
running time: 0.612 sec., time limit: 0.100 sec.

▶

large_symmetric2
symmetric string, N=200k

✘

TIMEOUT ERROR
running time: 2.368 sec., time limit: 0.128 sec.

▶

big_symmetric3
symmetric string, N=1M+

✘

TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.

▶

big_nonsymmetric
nonsymmetric string, N = ~1M

✘

TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.

▶

extreme_size
N = ~2M

✘

TIMEOUT ERROR
Killed. Hard limit reached: 7.000 sec.

7.000 s