very easy. I hope I will have such easy questions in my interview.

You can do it in one scan of K arrays, O(KN). Each array records the integer positions of every occurrence of a word.

By the way, I heard this was (also) an MS interview problem?

Suppose N(i) gives the occurrence count of i-th word, i going from 1 to K words.
The total number of possible window sizes is the product P(N(i) for i= 1..K).
Go through each of the possible windows and find the one(s) where the difference
of the largest offset and smallest offset is the lowest.
So the algorithm depends on the number of times the K words occur, and not the document size. It can stop once it finds a window size that equals K, or continue to find other windows of the same size.

Example: Suppose the document is Z A Y B C X Z D E F Y G, and you want to find smallest window of XYZ. The inverted index list is X = {5}, Y = {2, 10}, Z = {0, 6}
The total number of windows is the product 1 x 2 x 2 = 4. They are (5, 2, 0)-> size 6,
(5, 2, 6) -> size 5, (5, 10, 0) -> size 6, (5, 10, 6) -> size 6. The smallest window is (5, 2, 6) i.e. from 2 (Y) to 6 (Z) -> "Y B C X Z". I think this is correct.:-,

That solution takes O(<Avg. Occurances>^K)...cleanly in the NP arena. Probably not a workable solution. What optimizations can you make?

One optimization I can think of but not sure is as follows:
For K words, the minimum window size is K. So find the shortest occurrence list, then
for each offsets O, look for offsets in others words (K - 1) to be within 0 - K < N < O + K. That is a 2K window size. If you find an occurrence of all the words in that window,
then eliminate the rest, and find the set with lowest window size. So in the
above example, K = 3, X is the shortest occurring word. For O = 5, find offsets of Y and Z between 2 (5 - 3) and 8 (5 + 3). The only set, in this example, is Y = 2, and Z = 6. So the answer is X = 5, Y = 2, Z = 6, with window size of 5, which is K + 2. If no offsets are found in the range, increase the bound to O - 2K < N < O + 2K..and so on.

for given ex:
w1: 1, 1000, 2500
w2: 400, 1001, 2000
w3: 500, 1002, 1500

keep 2 arrays negdev (negative deviation from base) and posdev(positive deviation from base) of size 3 (same as size of base array) along with base array which is same as w1:
base=[1, 1000,2500] same as w1 ()
negdev=[0,0,0] and posdev=[0,0,0] (zero initialization)
now calculate both arrays traversing through the k array of occurances of given words , here w1,w2 and w3
negdev(i)= maximum negative deviation from base[i] to find all k words
posdev(i)= maximum positive deviation from base[i] to find all k words
so after traversal we get
posdev=[499,2,0]
and negdev=[0,0,1000]
now calculate range array range(i)=posdev(i)+negdev(i)
so range=[499,2,1000]
so minvalue of range will be the answer.
time complexity : O(n)
space complexity: 2 arrays of size of w1 (if you want to minimize this, then instead of taking w1 as base first find base in set of k array , word which has minimum occurances)

can be solved in O(nlogK).

Use dynamic programming, and it can be solved with O(nk) time and O(k) space.

here is my take and quite certain its not accomplished in O(nlogn) but worth a shot.

create a kxk graph where the edges signify the minimum distance from each word to the other. ( this part needs the optimization)

once the graph is generated, compute the minimum spanning tree and the resultant tree will be your desired positions.

what now needs to be done is figure out how to efficiently generate the KxK graph.

cheers

let me try to explain this.

you have a list of words and the list of distance from start.

abc - 2 , 3 , 15, 19 , 24
def - 4 , 5, 10 , 28
ghi - 12,33,55

random values
etc.

these are distances from the start. let each word represent a node. let each node have an edge to each other node. the number of edges from one node to another node will be more than 1 (because of multiple occurrence of the words in the text).

compute the difference for each word distance with regard to every other word distance and this difference will be the distance on the edge for that word (for optimality we can take the minimum distance for two words and just add one edge between them) .

as a result you have a graph where all nodes are connected with each other with the relative distance. with this we have the information on how close the words are to each other.

now to find the smallest window, we need to find the edges that would connect all the nodes(words) such that the weight of the edges will be the smallest. this translates as finding an mst for the graph.

Here is a solution I have come up with:

Let a1, a2, a3 and so on be the array that holds the position of occurrence of each word.
k1, k2, k3 and so on be the pointers to the start of each array.
Initialize the minimum_window = N, where N is the number of words in the input
Follow the steps until the pointer reach the end of each array.
1. Compute the value: largest-smallest+1 for each pointer. This is the current window. If this value is less than the minimum_window then update the minimum window and temp_result = current positions of the pointers.
2. Check if all the pointers pointing to the last position in respective array. If yes, minimum_window is the smallest window and If not , increment the pointer with the minimum value.

Result: current positions of the pointers in the temp_result and size is minimum_window.

This is for generating a snippet of a document.

As all the inverted lists are sorted, lets suppose there are k of them.
Now build a min-heap with the first index of all the k lists and also keep track of the max element. Now check the value of max - min and store it.
Now keep reading the indexes from each list, and check if its index > min value, then insert it into the heap and pop the min element. Keep doing this till you exhaust elements in one of the lists.

Imagine the entries in the lists as points in 2-D planes, where Y axis = the word and X axis = position . Imagine the posting lists for I am one

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 shouldn't take more than o(n) time

Does this seem too easy? Am I missing something?