[dogruck]

Confusing because the problem statement says you cannot assume anything about the data structure storing each set. To me, that implies it must be treated as a stream -- not an array with indexing.

But yeah, if they are arrays, you use binary search. Not obvious, but also straightforward if you are looking to beat O(k).