9
\$\begingroup\$

I recently applied for a job as a Python coder but was rejected.

This was the problem:

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

Assuming they were looking for expert Python programmers, what could I have done better?

# Tested with Python 2.7
import unittest

# Runtime: O(n)

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

    # 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.")

    arr_len = len(int_arr)
    if arr_len < 3: 
        return False

    # Loop through elements
    for i in range(arr_len-2):
        if int_arr[i] == 1 and \
            int_arr[i+1] == 3 and \
            int_arr[i+2] == 4 : 
            return True
    return False


class TestMethodDoesSeqAppear(unittest.TestCase):
    def test_only_single_seq(self):
        #Single time
        assert doesSeqAppear([1,3,4]) == True

    def test_multiple_seq(self):
        #multiple
        assert doesSeqAppear([2,2,1,3,4,2,1,3,4]) == True


    def test_neg_seq(self):
        #multiple
        assert doesSeqAppear([9,-1,1,3,4,-4,4]) == True

    def test_only_empty_seq(self):
        #empty
        assert doesSeqAppear([]) == False
    def test_only_single_elem_seq(self):
        #Single element
        assert doesSeqAppear([1]) == False

    def test_input_is_none(self):
        self.assertRaises(TypeError, doesSeqAppear, None)

    def test_raises_type_error(self):
        self.assertRaises(TypeError, doesSeqAppear, "string")

    def test_raises_value_error(self):
        self.assertRaises(ValueError, doesSeqAppear, [1,2,'a', 'b'])

if __name__ == '__main__':
    unittest.main()

#
\$\endgroup\$
  • 5
    \$\begingroup\$ Well for one, Python lists can have multiple types of values, are you sure they required each array to have all ints. For example: ['a','b','c',1,3,4] seems like a valid sequence that would return false in your implementation \$\endgroup\$ – Navidad20 Dec 14 '16 at 14:36
  • \$\begingroup\$ Maybe you should have used xrange? ;) \$\endgroup\$ – Tamoghna Chowdhury Dec 14 '16 at 14:38
  • 1
    \$\begingroup\$ Also, they asked about an array. Maybe you should have used a numpy.array instead of a list? With NumPy arrays, this could be done in 2 function calls. \$\endgroup\$ – Tamoghna Chowdhury Dec 14 '16 at 14:43
  • 3
    \$\begingroup\$ As I said in another comment, there are so many unknown points in this question that I think the main reason for rejection may actually be him making assumptions instead of asking questions. \$\endgroup\$ – ChatterOne Dec 14 '16 at 15:18
  • \$\begingroup\$ Why not just str([1,3,4])[1:-1] in str([array])? \$\endgroup\$ – Samuel Shifterovich Dec 14 '16 at 21:41
10
\$\begingroup\$

By PEP 8, doesSeqAppear should be does_seq_appear. You used the right naming convention for your unit tests, though. Personally, I would prefer def contains_seq(arr, seq=[1, 3, 4]).

Your arr_len < 3 test is superfluous and should therefore be eliminated. Don't write a special case when the regular case works correctly and just as quickly.

Your all(isinstance(item, int) for item in int_arr) check was not specified in the problem, and is therefore harmful. The question does not say that doesSeqAppear([3.1, 1, 3, 4]) should return False, nor does it say that it should fail with an exception. In fact, by my interpretation, it does contain the magic sequence and should therefore return True. In any case, you have wasted a complete iteration of the list just to perform a check that wasn't asked for.

Checking isinstance(int_arr, list) is un-Pythonic, since is the norm in Python. In any case, the code would likely fail naturally if it is not a list.

After cutting all that excess, you should drop the # Loop through elements comment as well.

\$\endgroup\$
  • \$\begingroup\$ I wouldn't say the arr_len < 3 test is superfluous. It is preventing an index error. \$\endgroup\$ – Casey Kuball Dec 14 '16 at 21:02
  • 1
    \$\begingroup\$ @Darthfett: I don't think it prevents any errors. If the length is less than 3, the for loop will execute 0 iterations. \$\endgroup\$ – user2357112 supports Monica Dec 14 '16 at 21:04
  • \$\begingroup\$ @user2357112 oops, you are correct. :) \$\endgroup\$ – Casey Kuball Dec 14 '16 at 21:05
  • \$\begingroup\$ If dropping the arr_len < 3 check, it would be appropriate to specify why it still works without it, since it takes a moment to figure that out. \$\endgroup\$ – jpmc26 Dec 15 '16 at 0:23
9
\$\begingroup\$

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…).
\$\endgroup\$
  • \$\begingroup\$ Something like tuplewise might be a more evocative name than lookup. (I had the same idea though.) \$\endgroup\$ – David Z Dec 14 '16 at 18:51
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How performant is it? Someone could throw a huge byte array at your method (like a file looking for a particular sequence) and this would duplicate it in memory 3 or 4 times, no? \$\endgroup\$ – Nate Diamond Dec 15 '16 at 18:01
  • \$\begingroup\$ @NateDiamond At worst, it could be five times through the list. However, the time it takes would be the same as a single loop with five instructions per element, unless going through the loop once is easier on the cache, easier for all the popular Python implementations to optimize, or is faster for some other reason. Yes, it would temporarily either triple or quadruple the memory usage. This all probably doesn't matter though. Design is about trade offs, but whether this is performant enough can't be determined with the given problem. Linear speed and memory usage isn't a bad starting place. \$\endgroup\$ – Drew Dec 16 '16 at 7:13
  • \$\begingroup\$ Fair enough, but if I were asking this in an interview, the first question that would pop into my head (assuming you didn't) is "Why didn't you ask how big the sequence could be?". I would then probably say "So what if this is trying to parse a 500mb file?" Net-net, anyone using this should realize the downsides to this approach in case they want to reuse it. Further, you claimed the given answer is much too long, yet the approach has certain benefits in this regard. They should probably be mentioned. \$\endgroup\$ – Nate Diamond Dec 16 '16 at 18:12
  • 1
    \$\begingroup\$ @NateDiamond Thanks for your input. I've included a discussion about efficiency in my answer. \$\endgroup\$ – Drew Dec 19 '16 at 11:05
4
\$\begingroup\$

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 other 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))
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "Subsequence" has a very specific technical meaning, and it is the wrong term to use here. \$\endgroup\$ – 200_success Dec 15 '16 at 2:36
  • 1
    \$\begingroup\$ @200_success Hmm, you're right. Naming things is hard. \$\endgroup\$ – brian_o Dec 15 '16 at 5:15

protected by Community Jan 16 at 6:18

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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