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.
text.find(pattern)
? \$\endgroup\$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\$