find_index for first occurrence of pattern in text This is an implementation of find_index for a pattern in text. I got asked this coding question in a coding interview.

This Python function returns the starting index of the first occurrence of pattern in text and returns None if no index is found. For example, find_index('ababc', 'abc') returns 2 and find_index('abc', 'z') returns None.

I have the following implementation that handles most of the cases and I think the worst case running time is \$O(m*n)\$.

def find_index(text, pattern):
    assert isinstance(text, str), 'text is not a string: {}'.format(text)
    assert isinstance(pattern, str), 'pattern is not a string: {}'.format(text)
    #if it's empty string, return 0
    if pattern == '':
        return 0
    text_index = 0
    while text_index != len(text):
        for i in range(len(pattern)):
            if text_index + i &lt; len(text):
                if text[text_index + i] != pattern[i]:
                    break
                if i == len(pattern) - 1:
                    return text_index
        text_index += 1


I am not sure if I exhausted all of the edge cases, but I ran the following unit test, and it passed all tests.

import unittest

class StringsTest(unittest.TestCase):
   def test_find_index_with_matching_patterns(self):
        assert find_index('abc', '') == 0  # all strings contain empty string
        assert find_index('abc', 'a') == 0  # single letters are easy
        assert find_index('abc', 'b') == 1
        assert find_index('abc', 'c') == 2
        assert find_index('abc', 'ab') == 0  # multiple letters are harder
        assert find_index('abc', 'bc') == 1
        assert find_index('abc', 'abc') == 0  # all strings contain themselves
        assert find_index('aaa', 'a') == 0  # multiple occurrences
        assert find_index('aaa', 'aa') == 0  # overlapping pattern
        assert find_index('thisisabsolutelycrazy', 't') == 0

    def test_find_index_with_non_matching_patterns(self):
        # Negative test cases (counterexamples) with non-matching patterns
        assert find_index('abc', 'z') is None  # remember to test other letters
        assert find_index('abc', 'ac') is None  # important to test close cases
        assert find_index('abc', 'az') is None  # first letter, but not last
        assert find_index('abc', 'abz') is None  # first 2 letters, but not last

if __name__ == '__main__':
    unittest.main()
Python is a duck typed language, so it's not considered normal to assert instance types. Instead simply assume that the user passed a string, and let the program fail if the input can't be processed sensibly.

You calculate the length of text and pattern potentially many times during a run. Unless you plan on modifying them during the run you can save the results to a variable and reuse that.

You can get rid of if text_index + i &lt; len(text) by changing your while statement to take into account the length of the pattern.

Apropos runtime: I'm purposefully not commenting on more advanced algorithms for text searching, mainly because I don't memorize things I have literally never had to use.