# Google Foobar Challenge: Spy Snippets in Python [closed]

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)

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("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')


## closed as off-topic by 200_successJul 31 '16 at 16:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – 200_success
If this question can be reworded to fit the rules in the help center, please edit the question.

• Please include the problem statement in the question. Are you sure your code is working correct? If the judge says it isn't, I tend to believe the judge. Broken code is off-topic for Code Review, please take a look at the help center. – Mast Jul 30 '16 at 22:38

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

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]])


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.