Python code to check if an array has a sequence (1,3,4)

Per the problem definition, I would expect a function thas is able to check any sequence in an array. Not necessarily (1, 3, 4) which was given as an example. In this case, the sequence should also be a parameter of the function, giving the signature:

def has_sequence(array, sequence):

Next, I would rely on Python iterations to "check" if array is a list, or at least an iterable. As there is no obvious reasons, to me, that has_sequence('once upon a time', 'e u') should fail. It seems like a valid usecase.

Following, I would use a variation of the itertools recipe pairwise to group elements of array in tuples of the same length than sequence:

import itertools


def lookup(iterable, length):
    tees = itertools.tee(iterable, length)
    for i, t in enumerate(tees):
        for _ in xrange(i):
            next(t, None)
    return itertools.izip(*tees)


def has_sequence(array, sequence):
    # Convert to tuple for easy testing later
    sequence = tuple(sequence)
    return any(group == sequence for group in lookup(array, len(sequence)))

Now, other things that could have been done better:

• # Tested with Python 2.7 can be replaced by #!/usr/bin/env python2
• if int_arr[i] == 1 and int_arr[i+1] == 3 and int_arr[i+2] == 4 : can be replaced by if int_arr[i:i+3] == [1, 3, 4]: removing the need for the ugly \
• assert in unit tests should be replaced by self.assertTrue(…) or self.assertFalse(…)
• you should be more consistent in your usage of whitespace (putting one after each comma, none before any colon…).

I think your answer is much too long. Here's mine:

def check_for_1_3_4(seq):
    return (1, 3, 4) in zip(seq, seq[1:], seq[2:])

Here are some tests:

>>> check_for_1_3_4([1, 3, 4, 5, 6, 7])
True
>>> check_for_1_3_4([5, 6, 7, 1, 3, 4])
True
>>> check_for_1_3_4([5, 6, 1, 3, 4, 7, 8])
True
>>> check_for_1_3_4([1, 3])
False
>>> check_for_1_3_4([])
False
>>> 

My code may seem terse, but it's still readable for anyone who understands slicing and zip. I expect Python experts to at least know about slicing.

Unfortunately for me, my answer is less efficient than yours. It could triple the amount of memory used! By using generators a more efficient but more complicated solution can be created. Instead of creating copies of the sequence, this new code uses only the original sequence, but the logic is nearly the same.

import itertools

def check_for_1_3_4(seq):
    return (1, 3, 4) in itertools.izip(seq,
                                       itertools.islice(seq, 1, None),
                                       itertools.islice(seq, 2, None))

The tests still pass.

I wouldn't expect most Python programmers to be familiar with itertools, but I was under the impression that Python experts do know it.

KIS[S]

def sequence_contains_sequence(haystack_seq, needle_seq):
    for i in range(0, len(haystack_seq) - len(needle_seq) + 1):
        if needle_seq == haystack_seq[i:i+len(needle_seq)]:
            return True
    return False

We can't know why your interviewer rejected your application, but these types of questions are often starting points for conversation--not finished product endpoints. If you write the simplest, most straightforward code you can, you and your interviewer can then talk about things like expansion, generalization, and performance.

Your interviewer knows that asking you to change your function interface is more problematic because you'll also have to change all your [unasked for] unit tests. This slows down the process and might make the interviewer worry that you'll pollute their codebase with a lot of brittle code.

Assumptions

You made a lot of assumptions with this code, which you either did not mention during the interview or you incorrectly assumed to be true of the question. In order words, you were over thinking the problem.

#check if input is a list
if not isinstance(int_arr, list):
    raise TypeError("Input shall be of type array.")

You should not care about the instance type. The type could easily have been a user defined type which behaves like a list or even another python built in. For example, python has both deque and array, and they both behave like a list, supporting the same operations as a list.

# check all elements are of type int
if not all(isinstance(item, int) for item in int_arr) :
    raise ValueError("All elements in array shall be of type int.")

This is not necessarily true because lists or collections in general, in python can contain many different types. So insisting that the list contains only integers is just imposing a requirement which did not exist in the first place.

In closing, I would advice that you adhere to the KISS principle in future interviews and to ask questions or state your assumptions before diving into the code. Even if it doesn't sound like an assumption to you, make sure they know what is going on in your head either as you're coding or before you write your code. It might sound silly to say "Ok I will also make sure that I have been given a list", but you will be saving yourself a lot of grief when they reply, "Don't worry about that, just assume it's a list".

Check if array contains the sequence (1,3,4)

def check_sequence(arr):
    return any((arr[i], arr[i + 1], arr[i + 2]) == (1,3,4) for i in range(len(arr) - 2))

This optimization allows you to reduce the number of times checking an element. It also eliminates the need to make a new iterator which you had created with range

# Loop through elements
index = 0
while index < (arr_len-2):
    if int_arr[index] != 1:
        index += 1
        continue
    if int_arr[index+1] != 3:
        index += 1
        continue
    if int_arr[index+2] != 4:
        index += 1 
        continue
    return True
return False