Question: 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)?

Solution: Let us suppose
I- > 1 5 7 11
am -> 3 6 9 12
one -> 7 8 99

Sort all the entries - so u get
1 3 5 6 7 8 9 11 12 99 in o(n) time as the lists are already sorted

Now, we just have to come up with a window having 3 non-similar elements. As there can be max n-k (where k=no of term we are looking it, here 3), looking at those windows and determining the min window in o(n) time