# Check whether an array can be the result of merging two smaller arrays, maintaining order

Posted on

Problem

I’m prepping for a tech interview coming up and trying to have a better understanding of what I should look out for in writing code. Also, feel free to correct the terminology that I use as I want to be able to talk about my code clearly and succinctly.

One of the specifications for the tech interview process is that I use idiomatic JavaScript, according to the recruiter. I’m not familiar with that term and would appreciate any feedback on how to best write to that standard. Is there a specific standard that I should adhere to? Is that related to proper naming conventions?

Is there a better way for me to optimize time and space in my code?

When I assign values to variables within loops, are there rules that I should be aware of for when I shouldn’t? For example, the current element being iterated over assigned to currentH1 variable, in my mind, makes it more readable in understanding what’s happening as opposed to half1[h1Index], and I reuse it more than once. Plus, I believe this might make it more idiomatic but I’m not sure? Am I losing out on space complexity in any way? Or is there something that I may not be aware of by checking current against undefined instead of checking the current index against the size of the array?

When I assign values to variables outside of loops but within the function, are there space complexities that I should pay attention to or does garbage collection take care of this? Is this $$O(1)$$

$O\left(1\right)$

$O(1)$ space complexity as I’m just keeping track of the indices? Feel free to breakdown space complexity as I truly do want to have a more solid understanding of memory management.

I believe I’ve accounted for the edge cases that I can think of, but are there more that I should be aware of?

I placed the if condition for checking lengths at the top even before the index definitions because I figured that if they aren’t even the same size, why bother with doing anything else. Is that weird?

function isMergedArray(half1, half2, mergedArray) {
if ((half1.length + half2.length) != mergedArray.length ) {
return false;
}

let h1Index = half1.length - 1;
let h2Index = half2.length - 1;
let maIndex = mergedArray.length - 1;

while (maIndex >= 0) {
const currentH1 = half1[h1Index];
const currentH2 = half2[h2Index];
const currentMa = mergedArray[maIndex];

if (currentH1 != undefined && currentH1 === currentMa) {
h1Index--;
} else if (currentH2 != undefined && currentH2 === currentMa) {
h2Index--;
} else {
return false;
}

maIndex--;
}

return true;
}


Solution

Is there a specific standard that I should adhere to?

Pick one, and stick to it. I use this one: https://github.com/airbnb/javascript

One of the specifications for the tech interview process is that I use idiomatic JavaScript

I understand that as follow the community conventions for writing code. Using a common standard helps.

Is there a better way for me to optimize time and space in my code?

I does not get much better than this, though you could drop the use of currentH1, currentH2, and currentMa.

When I assign values to variables within loops, are there rules that I should be aware of for when I shouldn’t?

In my mind, if you are going to use the assigned value only once, then it does not make sense to assign it.

Is there something that I may not be aware of by checking current against undefined instead of checking the current index against the size of the array?

Absolutely, your code breaks in a test case where the array contains undefined as a value

When I assign values to variables outside of loops but within the function, are there space complexities that I should pay attention to or does garbage collection take care of this?

Nah

Is this O(1) space complexity as I’m just keeping track of the indices?

That is my understanding

I believe I’ve accounted for the edge cases that I can think of, but are there more that I should be aware of?

As I mentioned, dupe values across the two halfs. It changes the paradigm of the routine completely. Also, as mentioned before, an array with undefined as a value.

I placed the if condition for checking lengths at the top even before the index definitions because I figured that if they aren't even the same size, why bother with doing anything else. Is that weird?

Not at all, however I only do this in functions that are very frequently called.

Other than, I tried to write this ‘the proper way’ by checking from the first value to the last, and it looked worse.

From a naming convention, mergedArray is a bit of misnomer, you don’t whether it is a merged array.

It annoys me personally that you assign a value to currentH1 in a loop, but then declare it as const. It is not wrong technically, but it reads wrong to me.

I rewrote the code a bit with my comments in mind:

function isMergedArray(half1, half2, list) {
if ((half1.length + half2.length) != list.length ) {
return false;
}

let i = list.length - 1,
h1 = half1.length - 1,
h2 = half2.length - 1;

while (i >= 0) {

let currentElement = list[i];

if (h1 != -1 && half1[h1] === currentElement) {
h1--;
} else if (h2 != -1 && half2[h2] === currentElement) {
h2--;
} else {
return false;
}
i--;
}

return true;
}


I placed the if condition for checking lengths at the top even before the index definitions because I figured that if they aren’t even the same size, why bother with doing anything else. Is that weird?

No I don’t think that is weird. I would consider it a good optimization.

Personally I think the code is mostly fine, a good starting point would be to Google some examples on how to merge sub-arrays since that is fairly similar.

My one question would be why you started at the end of the array and merged them in descending order. That is kind of strange to me. I would do it in ascending order. I would also use a for loop instead of a while loop.