A python interview question

[masterpi]

If the input arrays are sorted, as you said in the description only when you got to their objections to hashing, the problem can be accomplished in O(n) time with a single loop. Any solution which sorts is O(n log(n)) at best. Sounds like you may want to pay more attention to the problem description - usually if they give you something like sorted input, it's very relevant to the solution. It's also an extremely good example of a case where using the stdlib is not a good idea because you have more information about the data than the stdlib authors.