4 Ways to Solve a Google Interview Question in JavaScript

A companion to Google’s official mock-interview video for developers.

Image Credit: Ekaphon maneechot/Shutterstock

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;
};