4 Ways to Solve a Google Interview Question, in JavaScript

Introduction

When I was first learning about the performance of algorithms, I stumbled across this video of a mock-interview at Google.

The video not only provides a useful insight into the interview process at larger tech firms, but it was also very helpful in advancing my understanding of how to tackle algorithmic problems in the most efficient way possible.

This article is intended to be a companion to Google’s video, providing a commentary on each possible solution given in the video, plus my own version of each solution in JavaScript.

We’ll also discuss the time and space complexity of each algorithm. Though you don’t need to understand what that means to follow along, those who are interested in finding out more might find my article on Big O Notation useful. Let’s dive in.

The Problem

We are given an ordered array and a value. We’re then asked to create a function which returns true or false, depending on whether any two integers in the array may be added together to equal the value.

In other words, are there any two integers, x and y, in our array that — when added — are equal to our specified value?

Example A

If we were given the array [1, 2, 4, 9] and the value 8, our function should return false, because no two values in the array may be added together to get 8.

Example B

But, if we were given the array [1, 2, 4, 4] and the value 8, our function should return true, because 4 + 4 = 8.

Solution 1: Brute Force

Time Complexity: O(N²) Space Complexity: O(1)

The most obvious solution is to iterate through every value twice, using a pair of nested for loops.

const findSum = (arr, val) => {
  for (let i = 0; i  arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] + arr[j] === val) {
        return true;
      };
    };
  };

  return false;
};

This solution is inefficient, as it checks every possible sum that can be made from two elements in the array, and it also compares each pair of indices twice. (For example, when i = 1 and j = 2, that is effectively the same as comparing with i = 2 and j = 1; in this solution, we try both variants).

Because our solution uses a pair of nested for loops, it is quadratic, with a time complexity of O(N²).

See the Pen Solution 1 - tested with Jasmine by Bret Cameron (@BretCameron) on CodePen.

Solution 2: Binary Search

Time Complexity: O(Nlog(N)) Space Complexity: O(N)

Since the arrays are ordered, we should be able to find a solution which uses binary search, the most efficient search algorithm for ordered arrays. By itself, binary search has a run-time of O(log(N)). However, we’ll still need to use a for loop, to check every element in the array against all the other values.

This is what our solution might look like. To keep things clean, we’re using a separate function to control the binary search. We’re also using a function removeIndex() that returns a version of the array, minus the given index.

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++) {
    if (binarySearch(removeIndex(arr, i), val - arr[i])) {
      return true;
    }
  }
  return false;
};
const removeIndex = (arr, i) => {
  return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
const binarySearch = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  let pivot = Math.floor(arr.length / 2);
  while (start < end) {
    if (val < arr[pivot]) {
      end = pivot - 1;
    } else if (val > arr[pivot]) {
      start = pivot + 1;
    }
    pivot = Math.floor((start + end) / 2);
    if (arr[pivot] === val) {
      return true;
    }
  }
  return false;
};

The algorithm starts with the first index [0]. It then creates a version of the array excluding the first index, and uses binary search to see if any of the remaining values can be added to it to form the desired sum. This happens once for every item in the array.

By itself, our for loop would have a linear time complexity of O(N), but within each for loop we are running a binary search, giving an overall time complexity of O(Nlog(N)). This is better than the last solution, but we can do better still.

See the Pen Solution 2 - tested with Jasmine by Bret Cameron (@BretCameron) on CodePen.

Solution 3: Linear Time

Time Complexity: O(N) Space Complexity: O(1)

For this problem, the best performance we can hope for is O(N). One way to achieve this, based on our knowledge that the array is sorted, is to take two points: one at the beginning of the array, and one at the end.

If we sum these points and the result is greater than our desired value, we’ll take the end point and move it down a place. Or, if we sum these points and the result is smaller than what we’re looking for, we’ll take the start point and move it up one place.

Eventually, we’ll either encounter the desired value and return true, or the start and end point will converge, and we’ll return false.

const findSum = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;

  while (start < end) {
    let sum = arr[start] + arr[end];

    if (sum > val) {
      end -= 1;
    } else if (sum < val) {
      start += 1;
    } else {
      return true;
    }
  }

  return false;
};

See the Pen Solution 3 - tested with Jasmine by Bret Cameron (@BretCameron) on CodePen.

This elegant solution has a time complexity of just O(N), and happens also to be much simpler to write than the previous solution.

But what if we couldn’t guarantee the array was ordered?

What If Our Input Array Was Unordered?

At first glance, we could simply order the array first and then use our best solution above. But how will that affect the runtime?

The best sorting algorithm for the job is the quicksort, and that has a time complexity of O(Nlog(N)). If we apply that to our fastest solution, it will alter its performance from O(N) to O(Nlog(N)).

Solution 4 — Linear Time and Space

Time Complexity: O(N) Space Complexity: O(N)

A linear solution is possible, and it involves creating a new Set which contains a list of the compliments we are looking for; the trade-off required to achieve this performance is greater use of memory.

If the first value of our given array is 1 and the value we are looking for is 8, we can add the value 7 to our Set of compliments or “search values”.

Then, as we go through each value in our given array, we can check the Set of compliments to see if one of them is equal to our value. If so, we can return true:

const findSum = (arr, val) => {
  let searchValues = new Set();
  searchValues.add(val - arr[0]);

  for (let i = 1, length = arr.length; i < length; i++) {
    let searchVal = val - arr[i];

    if (searchValues.has(arr[i])) {
      return true;
    } else {
      searchValues.add(searchVal);
    }
  }

  return false;
};

This solution can be refactored to fit on just a couple of lines:

const findSum = (arr, sum) =>
  arr.some(
    (
      (set) => (n) =>
        set.has(n) || !set.add(sum - n)
    )(new Set())
  );

At the core of this solution is a for loop — or, in the refactored version, array.some()— which have a linear time complexity of O(N). The set.has() method has a run-time complexity of just O(1), meaning that the overall time complexity of this function is linear.

As for the space complexity, we must create an additional array, whose length mirrors the original array (minus one, but this can be ignored), yielding a space complexity of O(N). It is this increased usage of memory which allows us to keep the run-time as efficient as possible:

See the Pen Solution 4 - tested with Jasmine by Bret Cameron (@BretCameron) on CodePen.

Conclusion

Overall, I hope you found this article a useful companion to Google’s mock-interview video. It demonstrates that a seemingly simple task can be solved in a number of ways, with different implications on run-time and memory-usage.

While the interview question and the four approaches to solving it are taken directly from Google’s video, all the code here is my own.

Lastly, If you’re interested in learning more about time and space complexity, see my article on Big O Notation. I also encourage you to try out your own functions in the CodePens provided for each solution. Happy coding!