Beware of “Algorithm Interview” articles

I received an email digest from a popular blogging platform which included after the first few serious and news worthy links some more click-baity content. The article that caught my eye is titled something along the lines of “Questions and Answers to Algorithm Interviews”. In my experience, with few exceptions, articles under the general theme of interview questions are not very good, they’re watered down versions of the real thing, but they must draw clicks because every blog has one. So an article like that surrounded by click-bait must surely fit that description. However, since this is an email digest, perhaps I was too quick to judge, and I decided to click on the link. It was unfortunately as I expected.

So here’s my take on some of the questions that article covered.

Find the missing number in a given integer array of 1 to 100

The author’s solution that I won’t post here because it’s wrong, fails if the missing number is 1

Possible solutions are:

• Linear solution O(n)

We know that the sequence is numbered 1...100 so that means that for each number n, then n === i+1 , so let’s look for the first number does not match this condition:

function findMissingNum(arr) {
  let i = 0;
  while (arr[i] === ++i);
  return i;
}

• Alternative O(n)

Gauss’ formula tells us that the sum of the first n integers is n (n+1) / 2

So we know that the sum of the numbers from 1 to 100 is 5050. We can subtract all the numbers in the array from 5050 and the result is the missing term. While this works, it still visits every number, where the previous solution stops when it finds the missing term.

function findMissingNum(arr) {
  return arr.reduce((acc, v) => acc - v, 5050);
};

• Optimal solution: Binary search O(log n)

We know something very important about our array, it is sorted, so we can use a binary search. if arr[i] — i === 1then the missing number is to the right of i in the second half of the array, if arr[i] — i ===2 then the missing number is to the left of i, in the first half of the array. Think of a binary search as looking for a word in a dictionary.

function findMissingNum(arr, low = 0, high = arr.length - 1) {
  const middle = Math.floor((low + high) / 2);
  if (low <= high) {
    if (arr[middle] …