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)
Reppennyruddie, Cloud Support Associate at Accenture
Training Coordinator focuses on transaction quality, efficiency, and facility management. develops effective training for the programme “ mantra for attract girl ...
Repbarrondanielle057, Android test engineer at A9
My name is Danielle and I am working as a Contract manager. I love this job.and nowadays I am ...
Repelmothure, Backend Developer at ABC TECH SUPPORT
Social work is a practice-based profession that promotes social change, development, cohesion and the empowerment of people and communities. Social ...
Rep
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...