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] - middle === 2) {
      return findMissingNum(arr, low, middle - 1);
    } else if (arr[middle] - middle === 1) {
      return findMissingNum(arr, middle + 1, high);
    }
  }
  return low + 1; // index of missing number + 1
}

Find the largest and smallest number in an unsorted array of integers

For this question, the author iterates through the array and checks each element. This is how I would write this algorithm:

function findMinMax(array) {
  let min = array[0];
  let max = array[0];
  for (let i = 1; i < array.length; i++) {
    min = Math.min(min, array[i]);
    max = Math.max(max, array[i]);
  }
  return [min, max];
}

There’s another approach, not necessarily better, where we can just apply Math.max and Math.mix to the entire array.

function findMinMax(array) {
  return [
    Math.min.apply(null, array), 
    Math.max.apply(null, array)
  ];
}

This will be much faster, but if the array becomes too big, it will fail with a “Maximum call stack size exceeded” because these are recursive operations. To handle larger arrays safely, we need to divide and conquer.

Divide and conquer means splitting the data into smaller chunk and repeating the operation over and over, so we’re going to split our array into sub arrays and find the min and max for the first chunk, and then the next, etc, etc. There are two types of divide and conquer algorithms, iterative and recursive.

Iterative:

function findMinMax(arr) {
  let queue = [];
  while (arr.length > 100000) {
    const chunk = arr.splice(0, 100000);
    queue = queue.concat([
      Math.min.apply(null, chunk),
      Math.max.apply(null, chunk),
    ]);
  }
  const remaining = queue.concat(arr.slice());
  return [Math.min.apply(null, remaining), Math.max.apply(null, remaining)];
}

Recursive:

function findMinMax(arr) {
  if (arr.length <= 100000) {
    return [Math.min.apply(null, arr), Math.max.apply(null, arr)];
  }
function minMax(arr1, arr2) {
    const union = arr1.concat(arr2);
    const min = Math.min.apply(null, union);
    const max = Math.max.apply(null, union);
    return [min, max];
  }
const middle = Math.floor(arr.length / 2);
  return minMax(
    findMinMax2(arr.slice(0, middle)),
    findMinMax2(arr.slice(middle))
  );
}

Unfortunately, they both come at a trade-off, they consume more memory and will be slower for larger arrays. If we’re sure the array will more often than not be larger than 100,000 then the first solution is the best, it runs in linear time without requiring any additional space. If most times the array is less than 100,000 items, then a divide and conquer will be faster. We’ll give a preference to the iterative version as the recursive version has a recursion within a recursion and we want to avoid overflowing the call stack.

There are other solutions as well, like a min-max heap, or a quick select which allow to retrieve very quickly the smallest and largest values or the n-th smallest/largest elements (quick select).

So this is seemingly and easy question, but with much more depth than appears at first glance.

Return an array showing the cumulative sum at each index of an array of integers

The author iterates over an array and for each element, adds it to its previous element and stores the result in a new array. Unfortunately, more space is needed, as a whole new array is created (O(n)) . There’s a more efficient way to do this by modifying the array in place (O(1)).

function cumulativeSum(array) {
  for (let i = 1; i < array.length; i++) {
    array[i] += array[i - 1];
  }
  return array;
}

Remove all duplicates from an array of integers

In their answer, the author makes the assumption that the array is sorted, and says to sort it if need be. They then use a stack and push on top of the stack the next element of the array if the last element on the stack is different from the array. That’s immediately an O(n log n) time complexity, and a O(n) space complexity. We can do this in constant O(1), with simpler logic. We’re going to create a Set from the array, as a Set can only hold unique elements, then convert the set back to an array.

• Quick es6 version

const uniques = (arr) => [...new Set(arr)];

• Longer form

function uniques(arr) {
  return Array.from(new Set(arr));
}

• Hashmap and filter instead of a Set O(n)

function uniques(arr) {
  const v = {};
  return arr.filter((n) => {
    if (v[n] === null) {
      return false;
    }
    v[n] = null;
    return true;
  });
}