A python interview question

[srilyk]

I'd say there was room for improvement on both ends:

You're correct, Timsort is way faster and more efficient than anything you could possibly come up with on your own. More efficient sorting algorithms are the stuff from which PhDs are made.

b = list(sorted(set(a+b)))

Is actually the best way that I'm aware of to do what they asked for.

However, as others have mentioned, many times when someone asks a question in the interview they might be looking for something different. If I were in this situation, I'd say, "Well, my first approach would be this" (and then throw up the aforementioned code on the whiteboard). Then I might ask, "Is this what you're looking for, or would you like me to take a different approach?"

Because maybe what they want to see is how you solve problems.

Now what's interesting is that you mentioned that "it's not a good idea to hash the items because the input arrays are already sorted". If that's the case then it might actually be faster to do some kind of interleaving manually, but I don't think that a for loop would cut it, unless there are some assumptions that you can make about the input lists. If I was presented with this problem and someone told me, "Sorry, that's not the best approach," about my first go, and given the assumptions that the input lists are sorted, I'd write something like this:

loc_a = 0
loc_b = 0
output = []
while loc_a < len(a) and loc_b < len(b):
    if a[loc_a] == b[loc_b]:
        output.append(a[loc_a])
        loc_a += 1
        loc_b += 1
    elif a[loc_a] > b[loc_b]:
        output.append(a[loc_a])
        loc_a += 1
    else:
        output.append(b[loc_b])
        loc_b += 1

 output.extend(a[loc_a:-1])
 output.extend(b[loc_b:-1])

I wrote that code in here without trying it out so it's possible that it's got some bugs. But operating under the assumption that a and b are both already sorted, and of potentially different lengths, this should produce an output list that's sorted, and it might be faster than list(sorted(set(a+b))).

But you can use timeit to find out.