March 15, 2019 at 17:29

Solving a task from a Google interview on JavaScript: 4 different ways

Original author: Bret Cameron
  • Transfer


When I was studying the performance of algorithms, I came across this video from Google’s mock interview . It not only gives an idea of ​​how interviews are held in large technology corporations, but also allows you to understand how algorithmic problems are solved, and most efficiently.

This article is a kind of accompaniment to the video. In it, I give comments on all the solutions shown, plus my own version of the solution in JavaScript. The nuances of each algorithm are also discussed.

We remind you: for all readers of “Habr” - a discount of 10,000 rubles when registering for any Skillbox course using the “Habr” promo code.

Skillbox recommends: Practical course "Mobile Developer PRO" .

Formulation of the problem


We are given an ordered array and a specific value. Then they ask to create a function that returns true or false, depending on whether the sum of any two numbers from the array can be equal to the given value.

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

Example A

If we were given an array [1, 2, 4, 9] and a value of 8, the function will return false, because no two numbers from the array can give 8 in total.

Example B

But if it is an array [1, 2, 4, 4] and the value is 8, the function should return true, because 4 + 4 = 8.

Solution 1. Bruteforce

Temporary complexity: O (N²).
Spatial complexity: O (1).

The most obvious meaning is to use a pair of nested 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 cannot be called effective, since it checks every possible sum of two elements in the array, and also compares each pair of indices twice. (For example, when i = 1 and j = 2 - this is actually the same as comparing with i = 2 and j = 1, but in this solution we try both options).

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


Solution 2. Binary (binary) search

Temporary complexity: O (Nlog (N)).
Spatial complexity: O (1) .

Since arrays are ordered, we can search for a solution using binary search. This is the most efficient algorithm for ordered arrays. The binary search itself has an O (log (N)) runtime. However, you still need to use a for loop to check each element against all other values.

Here is what the solution might look like. To make everything clear, we use a separate function to control the binary search. As well as the removeIndex () function, which returns the version of the array minus the specified 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 at index [0]. Then it creates a version of the array, excluding the first index, and uses a binary search to check if any of the remaining values ​​can be added to the array to get the desired amount. This action is performed once for each element in the array.

The for loop itself will have a linear time complexity of O (N), but inside the for loop we do a binary search, which gives the total time complexity of O (Nlog (N)). This solution is better than the previous one, but there is still something to improve.


Solution 3. Linear time.

Time complexity: O (N).
Spatial complexity: O (1).

Now we will solve the problem, remembering that the array is sorted. The solution is to take two numbers: one at the beginning and one at the end. If the result differs from the required one, then we change the start and end points.

In the end, we either meet the desired value and return true, or the start and end points converge and 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;
};


Now everything is fine, the solution seems to be optimal. But who will guarantee that the array was ordered?

What then?


At first glance, we could just sort the array first, and then use the solution above. But how will this affect runtime?

The best algorithm is fast sorting with O (Nlog (N)) time complexity. If we use it in our optimal solution, it will change its performance from O (N) to O (Nlog (N)). Is it possible to find a linear solution with an unordered array?

Solution 4

Temporary complexity: O (N).
Spatial complexity: O (N).

Yes, a linear solution exists, for this you need to create a new array containing a list of matches that we are looking for. The tradeoff here is more active use of memory: this is the only solution in the article with spatial complexity exceeding O (1).

If the first value of this array is 1 and the search value is 8, we can add the value 7 to the array of “search values”.

Then, processing each element of the array, we can check the array of “search values” and see if one of them is equal to our value. If yes, return true.

const findSum = (arr, val) => {
  let searchValues = [val - arr[0]];
  for (let i = 1; i < arr.length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.includes(arr[i])) {
      return true;
    } else {
      searchValues.push(searchVal);
    }
  };
  return false;
};

The basis of the solution is the for loop, which, as we saw above, has linear time complexity O (N).

The second iteration part of our function is Array.prototype.include (), a JavaScript method that will return true or false depending on whether the array contains the given value.

To find out the time complexity of Array.prototype.includes (), we can look at the polyfill provided by MDN (and written in JavaScript), or use a method in the source code of a JavaScript engine such as Google V8 (C ++).

// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
  Object.defineProperty(Array.prototype, 'includes', {
    value: function(valueToFind, fromIndex) {
      if (this == null) {
        throw new TypeError('"this" is null or not defined');
      }
      // 1. Let O be ? ToObject(this value).
      var o = Object(this);
      // 2. Let len be ? ToLength(? Get(O, "length")).
      var len = o.length >>> 0;
      // 3. If len is 0, return false.
      if (len === 0) {
        return false;
      }
      // 4. Let n be ? ToInteger(fromIndex).
      //    (If fromIndex is undefined, this step produces the value 0.)
      var n = fromIndex | 0;
      // 5. If n ≥ 0, then
      //  a. Let k be n.
      // 6. Else n < 0,
      //  a. Let k be len + n.
      //  b. If k < 0, let k be 0.
      var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
      function sameValueZero(x, y) {
        return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
      }
      // 7. Repeat, while k < len
      while (k < len) {
        // a. Let elementK be the result of ? Get(O, ! ToString(k)).
        // b. If SameValueZero(valueToFind, elementK) is true, return true.
        if (sameValueZero(o[k], valueToFind)) {
          return true;
        }
        // c. Increase k by 1.
        k++;
      }
      // 8. Return false
      return false;
    }
  });
}

Here, the iterative part of Array.prototype.include () is the while loop in step 7, which (almost) traverses the entire length of the given array. This means that its temporal complexity is also linear. Well, since it is always one step behind our main array, the time complexity is O (N + (N - 1)). Using Big O Notation, we simplify it to O (N) - because it is N that has the greatest influence with increasing input size.

As for spatial complexity, an additional array is needed, the length of which reflects the original array (minus one, yes, but this can be ignored), which leads to the spatial complexity of O (N). Well, increased memory usage ensures maximum algorithm efficiency.


I hope this article will be useful to you as an attachment to a video interview. It shows that a simple problem can be solved in several different ways with different amounts of resources used (time, memory).

Skillbox recommends:

Tags:

Also popular now: