You are given a list of phrases and an object that provides one word at a time from a stream of words with the following API (the stream has been normalized where all characters are lower case and punctuation has been removed):
stream.next_word() -> string (next word in stream)
stream.end() -> bool (true or false whether there are any more words in the stream)Example input:
phrases = ['a cat', 'through the grass', 'i saw a cat running']
stream = 'i was walking through the park and saw a cat running through the grass then i saw a cat running from the bushes'Output should be the following, presumbly in O(n) time:
'a cat'
'through the grass'
'a cat'
'i saw a cat running'I wasn't able to provide an optimized solution during the interview but afterwards after reflecting on the question, I think a possible solution to the problem could be done using a Trie to store words and phrases and as you receive each word from the stream you could print out the phrases according to whether the word is marked as a phrase in the Trie.
A code sample:
class Stream:
def __init__(self, stream):
self.stream = stream.split()
self.index = 0
def next_word(self):
self.index += 1
return self.stream[self.index - 1]
def end(self):
return self.index == len(self.stream)
class TrieNode:
def __init__(self):
self.phrase = False
self.words = {}
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, phrase):
current = self.root
phrase = phrase.split()
for word in phrase:
if word not in current.words:
current.words[word] = TrieNode()
current = current.words[word]
current.phrase = True
class Solution:
def print_phrases(self, phrases, stream):
trie = Trie()
for p in phrases:
trie.insert(p)
trie_node = trie.root
start_node = trie_node
res = []
while not stream.end():
word = stream.next_word()
if word in trie_node.words:
trie_node = trie_node.words[word]
res.append(word)
if trie_node.phrase:
tmp = []
current = start_node
for w in res[1:]:
if w in current.words:
current = current.words[w]
tmp.append(w)
if current.phrase:
print(' '.join(tmp))
tmp = []
current = start_node
print(' '.join(res))
res = []
trie_node = start_node
elif word not in trie_node.words:
trie_node = start_node
res = []
if __name__ == '__main__':
so = Solution()
phrases = ['a cat', 'through the grass', 'i saw a cat running']
_stream = 'i was walking through the park and saw a cat running through the grass then i saw a cat running from the bushes'
stream = Stream(_stream)
so.print_phrases(phrases, stream)Not sure if this is the best way to approach this problem, so any suggestions would be appreciated. This question was asked during the bar-raiser round where the interviewer was on a team that wasn't a part of the team I was interviewing for and he had lots of experience.