saga
BAN USERWe need to store pointers of the node in original list in a heap (along with its order of appearance).
Now simply create nodes (no links) for all the elements of first list and store them in another heap (with same order of oppearance)
Traverse each node of first list and look up for index of the node-addresses it is linked to. Do similar linking for second set of nodes.
We need to start with a windows with K 0's. Move one-by-one to the right. Keep expanding that windows till you get another '0' ( K+1 0's). Now you shed all left elements, till one '0' is dropped to reach K 0's, to get new windows with K 0's. Now keep sliding this window till you reach end of the array and print the smallest window. will get back with code.
- saga January 26, 2012I agree with eugene. But, apart from stack based solution, showing the understanding that recursion uses system stack will convince the interviewer on the candidates understanding of the concepts.. If any complexity, the solution metioned by 'sun', below, works.. :-)
- saga January 12, 2012
One pass approach is inefficient.. think of large scale.. million/billion list entries.. it gets stumped as it will traverse N+2N/3 times.
- saga June 11, 2012