Interview Questions

From careercup.com:

• Given a document and a query of K words, how do u find the smallest window that covers all the words at least once in that document? (given you know the inverted lists of all K words, that is, for each word, you have a list of all its occurrrences). This one is really hard. Could someone propose an algorithm in O(n)?

Answer: Use two pointers, one is the left of the range, one is the right of the range. For each word w_i we also keep a left and right pointer. Both initialize to the head of occurrence list (0).
Initially left is at the leftest word occurrence.
(Loop)
(AdvanceRight) Advance right by advancing the leftest of the right pointers in the occurrence list.
if reached the right end, break the main loop

Keep an array of counters for each word to count how many times w_i occurs in the range.
Advance right until all words are included.
Record range(left,right)
(AdvanceLeft)
Advance the left pointer and decrement the corresponding counter whenever left pointer moves pass word w_i
Repeat until at least one word doesn't occur in the range

Record range( left-1, right) if it's the current optimal

Go back to Loop

• Find the median of 2 sorted arrays