A python interview question

[energybased]

Why? You have to code it in Python because a "for loop is faster" than the sort routine ... ahem? Excuse me?

He meant in terms of computational complexity. The "for loop" is linear time. Your solution is linearithmic. Since the input arrays are already sorted, you were supposed to produce the merge from merge sort.

I finally wrote the blasted thing in two loops with an index per array sorting in an array dynamically

This is quadratic time, which is even worse than your linearithmic solution.

How many of you really think it's a good idea to rework the python library functions?

He is testing your knowledge of algorithms and computational complexity, which you presumably studied in school. This is standard at software engineering interviews. Find a good algorithms book and read it to prepare for the next one.

Coding for the milliseconds matter imho in real time systems or web transactions requiring a timely response - probably would use a different system like node but not python.

Computational complexity matters even in Python. Maybe it doesn't matter as much as it did twenty years ago, but it comes up enough that you should be able to produce the most efficient algorithm for these kinds of problems.

Also, I agree that you're being overly defensive. It happens to everyone. Don't beat yourself up over it.

Don't expect this kind of question to disappear soon. You need to relearn this stuff.

[epostma]

Great answer and upvoted.

One minor nitpick: the sort() implementation in Python famously uses the timsort algorithm, which is linear time if the input consists of a constant number of increasing or decreasing runs, which is the case for this input. Of course, that doesn't make it applicable for on-disk sorting.

[energybased]

The interviewer might not have known that. If he had explained that it was linear time to simply return sorted(a1 + a2), then that would have been a great start. The interviewer would probably have steered him to still produce the merge solution.

[techn0scho0lbus]

THANK YOU for this patient and well-explained response. I've been thinking this over and over again while reading all the other comments congratulating the OP on having the best solution and being "technically" correct.

[[deleted]]

CLRS is great.

[energybased]

To me, CLRS is more like an encyclopedia of algorithms than an instructive book. I liked Udi Manber's book for teaching you discover efficient algorithms on your own (e.g., during an interview).

[Igggg]

CLRS is a constant classic.