Today's question is one I like to ask interns because it's a super simple algorithm that tests the candidates knowledge of basic programming concepts, and has some natural expansions in the edge cases and optimization. Those easy expansions help generate a good conversational flow in an interview setting and helps give a sense of the candidate's ability to not only solve the immediate problem, but see how they deal with complications or changing requirements. What this question ultimately drives toward is an implementation of the Array.concat method which handles all the different expansions, plus can merge multiple arrays together.
“Given two pre-sorted arrays of uniform type and equal length, merge them into a single sorted array.”
Sounds easy enough. Let's assume the following inputs...
const a = [1, 3, 5, 7, 7, 8, 8, 9, 9]; const b = [2, 4, 5, 6, 7, 8, 9, 10, 11];
It's pretty easy to see what we need to do here: curse over both arrays from left to right, building a new array based on comparing the correct indices as we go. Here's what that looks like
Here the first step is to find the max length of our result so we have a target to terminate the while loop further down. Then we just create two cursors (lastA and lastB) that track the current index of each array to compare in each iteration.
In the loop we simply compare the value of the each array at the corresponding cursor index and push the winner: in this case, the smaller value. The result is a nice linear algorithm.
Now for the first expansion:
“What if the input arrays are unequal length?”
The solution above breaks down when you have inputs like this:
const a = [1, 3, 5, 7, 7, 8, 8, 9, 9]; const b = [2, 4, 5, 6, 7];
And that's because we're missing bounds checks! We just need to check if our cursor position for either array exceeds the length of it's array and from there we just append the remainder of the larger array to the result. We could alternatively create a new set of three arrays: two of equal length, and one for the remainder of the larger of the two original arrays, but that increases the memory requirements.
A clever candidate will recognize the opportunity to use Function.Apply() for this. Here's what that looks like:
Pretty easy, right? Being familiar with how to use apply means we don't have to loop over the arrays again, and we can use the array function push to do all our work for us! This has the handy side-effect of also handling the case where one of our arrays is empty since the cursors start at 0, and one of the bounds conditions will pass in that case. By putting the bound checking first in the loop we can break our sooner and prevent dangling undefined's in our result array from the un-bound else statement.
This is already a little longer than I planned, but the next expansion would be to accommodate different datatypes being mixed and matched. That expansion is a lot more open ended because at that point we have to develop and agree on rules for ordering the mis-matched types. Do they interlace? Do we order types into chunks somehow?
You could also branch into dealing with unsorted arrays; do you sort as you go? Pre-sort the inputs? Or just toss everything into one big array and sort the result? Implementing the sort itself might be out of scope for a short interview, just because it's a separate algorithm, but if you have time it's definitely worth seeing which sorting scheme the candidate reaches for, and provides an "in" for a discussion about sorting algorithm trade-offs.