10
\$\begingroup\$

I got asked this question before in an interview.

For example, find_all_indexes('ababc', 'abc') returns 2. This Python function should find the index of first occurrence pattern. I also wrote a function that returns a list of starting indexes of all occurrences of the pattern in a text.

I have the following implementation that handles most of the cases:

def find_all_indexes(text, pattern):
    indexes = []
    text_index = 0
    while text_index != len(text):
        if pattern == '':
            indexes.append(text_index)
        else:
            for i in range(len(pattern)):
                if text_index + i < len(text):
                    if text[text_index + i] != pattern[i]:
                        break
                    if i == len(pattern) - 1:
                        indexes.append(text_index)
        text_index += 1
    return indexes

def test_string_algorithms(text, pattern):
    indexes = find_all_indexes(text, pattern)
    print('find_all_indexes({!r}, {!r}) => {}'.format(text, pattern, indexes))

def main():
    test_string_algorithms(text, pattern)
    print('Usage: {} text pattern'.format(script))
    print("find_all_indexes('abra cadabra', 'abra') => [0, 8]")

if __name__ == '__main__':
    main()

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

The pytest output:

pytest test.py
======================= test session starts ========================
platform darwin -- Python 2.7.12, pytest-3.0.5, py-1.4.32, pluggy-0.4.0

collected 3 items 

test.py .........

===================== 3 passed in 0.07 seconds
\$\endgroup\$
  • 1
    \$\begingroup\$ (Welcome to CR!) Do you want opinions with respect to "interview setting" or "best code ever"? First thing I notice: neither comments nor doc strings. \$\endgroup\$ – greybeard Oct 31 '17 at 9:39
  • \$\begingroup\$ The explanation is pretty confusing (at least from my point of view). It seems like we have a find_all_indexes function returning an integer and another function which does return all indices... \$\endgroup\$ – SylvainD Dec 27 '17 at 16:44
8
+50
\$\begingroup\$

The code looks correct but overly complicated for the naïve algorithm used.

For a first refactor, you could pull out the special case pattern == ''. (We might pull it back in later).

Then

            for i in range(len(pattern)):
                if text_index + i < len(text):
                    if text[text_index + i] != pattern[i]:
                        break
                    if i == len(pattern) - 1:
                        indexes.append(text_index)

is just a substring equality check. There are two things to note here:

  1. Since it fails when text_index + len(pattern) > len(text) the outer loop runs too far.
  2. This could be written as if text[text_index:text_index+len(pattern)] == pattern: indexes.append(text_index).

Thirdly, the outer while loop could be written as a for in range, which is more Pythonic.

Putting those together, we have

def find_all_indexes(text, pattern):
    if pattern == '':
        return range(len(text) + 1)

    indexes = []
    for text_index in range(len(text) - len(pattern) + 1):
        if text[text_index : text_index + len(pattern)] == pattern:
            indexes.append(text_index)
    return indexes

But then the Pythonic way to write a for if append loop like that is a comprehension:

def find_all_indexes(text, pattern):
    if pattern == '':
        return range(len(text) + 1)

    return [text_index for text_index in range(len(text) - len(pattern) + 1)
            if text[text_index : text_index + len(pattern)] == pattern]

And now the special case is really a microoptimisation, and could possibly be removed to leave a one-liner.


However, that's not the final word. Naïve string search is asymptotically inferior to techniques such as Knuth-Morris-Pratt string search. You probably shouldn't roll your own KMP routine, but you could use string.find to get the benefit. So a better implementation would be a loop around string.find.

\$\endgroup\$
  • \$\begingroup\$ (Boohoo. This leaves out substituting for:…else: for for:…if iteration_variable >= upper_limit - step:.) \$\endgroup\$ – greybeard Nov 5 '17 at 22:42
  • \$\begingroup\$ @greybeard, you've lost me. The only instance of >= I can find anywhere on this page is in your comment. \$\endgroup\$ – Peter Taylor Dec 13 '17 at 8:16
  • \$\begingroup\$ For all I can tell five weeks later and counting, I tried to jest about your diligent stepwise improvement: after correcting the outer loop range, the inner loop could be for i in range(len(pattern)): if text[text_index + i] != pattern[i]: break else: indexes.append(text_index). \$\endgroup\$ – greybeard Dec 27 '17 at 8:09
  • \$\begingroup\$ A couple of remarks: [+] To me, the assumption that the input and pattern are members of <class 'str'> is not warranted by the specification for the function. [+] It possible to simplify if pattern == '': to if pattern:. [+] The behavior when !pattern is undefined as are many other behaviors such as when pattern is an integer. \$\endgroup\$ – ben rudgers Dec 27 '17 at 17:34
3
\$\begingroup\$

Remarks on the specification

Though the example pattern uses strings as the argument, the possibility of other input types such as lists is left open. This suggests further development of the test suite to cover a variety of cases. In the context of a technical interview, an example test case using lists may be enough to suggest the candidate has thought about the problem as generalized pattern matching.

General Notes on the code

Naming: indexes is a good name. text is not for because it biases the approach to pattern matching toward only strings.

Variables: Declaring more names such as text_len = len(text) might make the code easier to read and understand. It tells the reader that the length of text is important and it un-nests trivial code from within the more complex and important logic. Sometimes that reader is you.

Code shape: One of the benefits of Python's semantic indentation is that it provides visual evidence of logical complexity by pushing code to the right as it becomes more convoluted. Deep indentation suggests refactoring (no matter how wide the programmer's monitor is). Think of deep indentation as a Python code smell. The deeper the indentation the harder it is for the reader to maintain the context of its execution.

Comments: Please. Most code is not self explanatory to someone reading it six weeks from now. That someone could be you. Comments are a way to root out assumptions implicit in the code. For example if pattern == '': implies that the input is a string. Without the assumption it can be if pattern:.

Main: A great idea. Providing well formatted text makes working in the interpreter much better.

Using Python features

Though I like C, I usually prefer Python. The code looks a lot like C. Python makes it easy to write code that looks like C. That doesn't mean code that looks like C is a good thing.

  • Python has slices. Unfortunately, C does not. Slices will simplify the Python code. Slices will make the logic less complex.

  • Python has documentation strings. docstrings provide high level access to the descriptions of the code you write. See remarks on commenting above.

Alternative Implementation

It is worth noting that this implementation was written at leisure. There was not the pressure of a technical interview. It was not written while the primary concern was getting a job. There was time to drink coffee and think. There was time to take a walk and think. There was time to refactor in my favorite editor.

1:  def find_all_indexes(source, pattern):
2:     output = []
3:     length_source = len(source)
4:     length_pattern = len(pattern)
5:     for i in range(length_source):
6:         if source[i] == pattern[0] and source[i:i+length_pattern] == pattern:
7:             output.append(i)
8:         if i + length_pattern > length_source:
9:             break
10:    return output

1: The name source is as type agnostic as pattern. I would have used input but it is the name of a built in Python function. This can affect syntax highlighting in the editor.

2: I don't believe in self documenting code, but calling the output output is an exception.

6: The and short circuits. The slice covers all the logic of what to do when pattern[0] is matched in the source.

8: This bit of cleverness is why the absence of comments makes code harder to understand.

Remarks: The code does not have a code path for a null/false pattern. Based on the specification, I consider it undefined behavior. There are some things I like about C. Practically speaking, in the context of an interview, "What happens with null pattern?" might be an interesting request for more information...then again, what happens if the pattern is not iterable suggests that treating it as undefined behavior might be reasonable in the context of a technical interview.

\$\endgroup\$

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.