3
\$\begingroup\$

Please review my strstr implementation in terms of time/space efficiency and overall readability. I am preparing for a coding assessment coming up as I am looking to pivot my career from Physics to Computer Science. This is an exercise from the interview practice questions on CodeSignal. My implementation successfully passes all 14 tests but I get the following error when I submit my answer:

Tests passed: 21/27. Execution time limit exceeded on test 22: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input.

"""strstr().

Given two strings, text and pattern, return an integer indicating the index
in the text of the first occurrence of the pattern.
"""


def strstr(text, pattern):
    """Needle in haystack O(|text|) time? and O(?) space.

    Return an integer indicating the first occurrence of pattern in the text,
    or -1 if the pattern is not part of the text.
    """
    lookup = set([pattern])
    len_text = len(text)
    len_pattern = len(pattern)
    for index in range(len_text-len_pattern+1):
        if text[index:index+len_pattern] in lookup:
            return index
    return -1


def tests():
    """Sample Tests."""
    samples = [("CodesignalIsAwesome", "IA", -1),
               ("CodesignalIsAwesome", "IsA", 10),
               ("a", "a", 0),
               ("a", "A", -1),
               ("sst", "st", 1),
               ("lrnkbldxguzgcseccinlizyogwqzlifxcthdgmanjztlt", "an", 38)]
    for text, pattern, answer in samples:
        if strstr(text, pattern) != answer:
            print(f"text: {text}, pattern: {pattern}, aswer: {answer}")


if __name__ == "__main__":
    tests()

Edit: Avoid using built-in functions to solve this challenge. Implement them yourself, since this is what you would be asked to do during a real interview.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Can't you use text.find(pattern)? \$\endgroup\$ – Marc Dec 19 '20 at 6:25
  • \$\begingroup\$ @Marc I am not familiar with that method but the goal is to come up with our own efficient implementation: Avoid using built-in functions to solve this challenge. Implement them yourself, since this is what you would be asked to do during a real interview. \$\endgroup\$ – Gonzo Dec 20 '20 at 0:01
  • \$\begingroup\$ Got it, FYI str.find. \$\endgroup\$ – Marc Dec 20 '20 at 3:41
0
\$\begingroup\$

As someone trying to pivot from physics to Computer Science, I think this solution is good, many CS graduates might not come up with a better solution first up.

Let's get some optimizations unrelated to cyclomatic complexity out of the way.

You added the pattern to a set. The lookup is constant O(1), I don't see a need to do that and you can save on a high constant.

Let's take a closer look at

    for index in range(len_text-len_pattern+1):
        if text[index:index+len_pattern] in lookup:

specifically text[index:index+len_pattern], this creates a copy of the string for the range index:len_pattern. This is an implementation detail of Python, one can just as easily imagine an optimization that does not create a copy.

This question and its response might help explain this better.

You might be able to optimize away the object creation, again this unrelated to cyclomatic complexity.

premature optimization is evil - the intent above is more of a code review. Addressing you question below.


The runtime complexity of the loop is the equivalent of creating a copy of the pattern times the len of text

if m is len(text) and n is len(pattern) the for loop is O(n*m) in every iteration.

Typically in questions like these, there is an insight that is not always obvious that drives the solution resulting in a lower cyclomatic complexity. In this instance it is that the algorithm can be implemented in a single pass O(n) by keeping track of indexes across both the text and the pattern

def strstr(text, pattern):
     
    t = 0
    len_text = len(text)
    len_pattern = len(pattern)
    i = 0
    for i in range(len_text + 1):
        if (t == len_pattern or i == len_text):
            break
        if (text[i] == pattern[t]):
            t += 1
        elif (text[i] == pattern[0]):
            t = 1
        else:
            t = 0

    if (t < len_pattern):
        return -1
    else:
        return i - t
    
def tests():
    """Sample Tests."""
    samples = [("CodesignalIsAwesome", "IA", -1),
               ("CodesignalIsAwesome", "IsA", 10),
               ("a", "a", 0),
               ("a", "A", -1),
               ("sst", "st", 1),
               ("lrnkbldxguzgcseccinlizyogwqzlifxcthdgmanjztlt", "an", 38),
               ("abcd" * 300000 + "abcde", "abcde", 1200000),]
    for text, pattern, answer in samples:
        actual = strstr(text, pattern)
        if actual != answer:
            print(f"FAILED : pattern: {pattern}, actual: {actual}, expected: {answer}")
        else:
            print(f"SUCCESS: pattern: {pattern}, actual: {actual} matched expected")

I added an additional text case to demonstrate the runtime, testing this with time module in python, the clock time of the implementation is a few milli seconds compared to the clock time of the O(n*m) algorithm which on my machine is aboue 21 seconds.

\$\endgroup\$
2
  • \$\begingroup\$ Yours fails for example strstr('aaab', 'aab'), returns -1. Also, are you saying that yours has lower cyclomatic complexity? And "O(n*m) in every iteration" is misleading. \$\endgroup\$ – Kelly Bundy Dec 19 '20 at 20:34
  • \$\begingroup\$ I think expanding on a solution that linearly keeps track of substring match should be feasible, I'll be open to you expanding on the solution \$\endgroup\$ – Bhaskar Dec 19 '20 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.