## brighama

BAN USER- 2of 2 votes

AnswersWhat is the difference between a computers heap and it's stack?

- brighama in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Computer Architecture & Low Level - 0of 0 votes

AnswersYou have a dictionary, D, that stores the positions of words in a document by mapping words (strings) to positions in the document (arrays of ints.)

- brighama in United States

You also have a list of words, L.

Your job is to find the shortest sequence of words in the document that contains all the words in L.

E.g., if the document is "a b a c d x b a", then

D["a"] = [0 2 7]

D["b"] = [1 6]

...

If we are given that L=["a", "c", "x"]

Then we should return the start and end point of the shortest sequence that contains all words in L, which is (2, 5)

...the simple way is O(n^2) where n is the number of words in the document

...the way I came up with is exponential in |L|

...the interviewer had a way that was O(n)| Report Duplicate | Flag | PURGE

Amazon Research Scientist Algorithm

Ok, I think I figured it out. Now I understand why the interviewer gave me the dictionary of word locations.

Example:

If the document is “a b c a b x a x” and the list of words L = [“a”, “b”, “x”]. Then the resulting word position arrays will be:

[0 3 6]

[1 4]

[5 7]

Now imagine that I tell you the right-most position of the optimal span is 7. Then the problem becomes trivial: for each of the three position arrays, just select the highest position that is less than or equal to 7 (in this case, 6, 4, and 7.)

So, given that it’s easy to find the shortest span IF we fix the right-most position, we just need to iterate through all possible right-most positions, find the best span for each, and select the smallest span.

If we use a little care, this can be done in O(sum of lengths of position arrays)

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Finding the most frequent item in a sorted list is O(n) in time and O(1) in space. (We just iterate through the list and keep track of the current most-frequent number & its frequency.)

- brighama April 10, 2013An in-order traversal of a BST will give a sorted list.

So, at worst we should have O(n) time and O(1) space...