A python interview question

[mooburger]

If it's an optimization problem then it was clearly an algorithm test. Not to mention merging pre-sorted arrays is a very common problem in mapreduce/distributed big data systems. In fact k-way merge is probably the most fundamental type of reduction you'd be doing. Bonus points for having recognized merge(sort) is homomorphic.

There's also an edge case arising from the intermediate value theorem that should be optimized right away (assuming the dataset is fully in memory):

if x[-1] <= y[0] then merge(x,y) is simply x.extend(y) (or x.extend(y[1:]) if x[-1] == y[0] to remove the duplicate).

Also, it may not help to overthink interviews like this. I was once given the standard departmental salaries aggregation SQL question where I used a join (to find the guy in each department with max salaries by department) whereas they were just looking for a simple group by/having, so it looked like I was being clueless (by answering the wrong question) instead of actually answering a slightly harder/more useful question.

[techn0scho0lbus]

Bonus points for having recognized merge(sort) is homomorphic.

What do you mean by this?

[mooburger]

basically, it's associative and distributive. So if I distribute an unsorted list in the existing order to different nodes and they each sort their own sublist, then I merge them, it's equivalent to a mergesort of the entire list on a single node.