Google Foobar Challenge: Spy Snippets in Python [closed]

Question

I am getting all the answers correct. But still the solution is not accepted as only 4/5 tests cases are passed.

I have not posted the whole problem statement but the problem is similar to this.

I want to know if there are any more optimizations possible.

import sys


class Queue(object):
    input_array = []

    def __init__(self, input_array=None):
        if not input_array:
            self.input_array = []
        else:
            self.input_array = input_array

    def enqueue(self, element):
        self.input_array.append(element)

    def dequeue(self):
        return self.input_array.pop(0)

    def first(self):
        return self.input_array[0]

    def last(self):
        return self.input_array[-1]

    def size(self):
        return len(self.input_array)

    def get_queue(self):
        return self.input_array

    def get_queue_after_first(self):
        return self.input_array[1:]

    def __str__(self):
        return "Current Queue: {0}".format(self.input_array)


def answer(document, searchTerms):
    no_of_search_terms = 0
    count = dict()
    for searchTerm in searchTerms:
        if searchTerm in count:
            count[searchTerm] += 1
        else:
            no_of_search_terms += 1
            count.update({searchTerm: 1})

    q = Queue()
    len_q = Queue()
    smallest_snippet_size = sys.maxint
    offsets = tuple()
    tokens = document.split()

    for position, token in enumerate(tokens, start=1):
        if count.get(token, 0):
            q.enqueue(token)
            len_q.enqueue(position)
            while q.first() in q.get_queue_after_first():
                q.dequeue()
                len_q.dequeue()
            current_block_len = len_q.last() - len_q.first() + 1
            if (q.size() >= no_of_search_terms) and (current_block_len < smallest_snippet_size):
                smallest_snippet_size = current_block_len
                offsets = (len_q.first() - 1, len_q.last())

    return " ".join(tokens[offsets[0]: offsets[1]])


if __name__ == '__main__':
    assert (answer("world there hello hello where world", ["hello", "world"]) == 'world there hello')
    assert (answer("many google employees can program", ["google", "program"]) == 'google employees can program')
    assert (answer("some tesla cars can autopilot", ["tesla", "autopilot"]) == 'tesla cars can autopilot')
    assert (answer("a b c d a", ["c", "d", "a"]) == 'c d a')
    assert (answer("the cats run very fast in the rain", ["cats", "run", "rain"]) == 'cats run very fast in the rain')
    assert (answer("the cats run very fast in the rain run cats", ["cats", "run", "rain"]) == 'rain run cats')
    assert (answer("hello", ["hello"]) == 'hello')

Answer 1

Why use two Queues, when you could just queue a tuple (or even better, a collections.namedtuple)? The only place which might prevent this is here:

while q.first() in q.get_queue_after_first():

But this can be written as:

while any(q.first() == el[0] for el in q.get_queue_after_first()):

in is already O(n), so this should not even have worse runtime (also, any uses short-circuit evaluation).

Whenever you have to do a list.pop(0) you probably want collections.deque, which does deque.popleft in O(1) instead of O(n) for a list.

Actually I don't see a point in having the Queue class at all. All its functions are single line and it is very well known and pythonic that you get the first element with l[0] and the last with l[-1].

Also, I second the use of collections.Counter. In addition, collections.Counter will never have a count of zero for a key (unless modified to be so, of course), so if count.get(token, 0): is more readable as if token in count:

PEP8 recommends using lower_case for variable names, so I would rename searchTerms to search_terms.

Resulting code:

import sys
from collections import namedtuple, deque, Counter

Item = namedtuple("Item", "token position")

def answer(document, search_terms):
    count = Counter(search_terms)
    no_of_search_terms = len(count)

    queue = deque()
    smallest_snippet_size = sys.maxint
    offsets = tuple()
    tokens = document.split()

    for position, token in enumerate(tokens, start=1):
        if token in count:
            queue.append(Item(token, position))
            while any(queue[0].token == el.token for el in queue[1:]):
                queue.popleft()
            current_block_len = queue[-1].position - queue[0].position + 1
            if (len(queue) >= no_of_search_terms) and (current_block_len < smallest_snippet_size):
                smallest_snippet_size = current_block_len
                offsets = (queue[0].position - 1, queue[-1].position)

    return " ".join(tokens[offsets[0]: offsets[1]])

Answer 2

Class attribute

Having input_array = [] defined at class level does not add anything except confusion.

Counter

I think that this:

no_of_search_terms = 0
count = dict()
for searchTerm in searchTerms:
    if searchTerm in count:
        count[searchTerm] += 1
    else:
        no_of_search_terms += 1
        count.update({searchTerm: 1})

could be done in a clearer and more efficient way using: collections.Counter.