[throwaway32198]

This seems to be a rather easy, no ? All you need to do is to keep the top-2 elements in every window (okay I guess that part can be done with queue), and update it as you move it to the right. This is trivially linear time since you only look at elements once.

Nah this is cool.

What you need to watch out for is obscure badly worded nonsense. I once had a interview where I was asked to "design a protocol". The guys asking the question were so vague that it essentially turned into a game where I was constantly throwing predicates at them to find out what they meant. In the end it turned out they wanted me to use a predefined alphabet S without an end symbol, and lift it to one with an end symbol. Obviously, the cartesian product of S does the trick. All I got out of the interviewers though was some verbose non-sense about the grand design of computing. What a waste of time that was (and what a relief to not get that job!).