We solve the problem from a Google interview on JavaScript: 4 different ways

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

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

We remind: for all readers of "Habr" - a discount of 10,000 rubles when recording for any Skillbox course on the promotional code "Habr".
')
Skillbox recommends: Practical course "Mobile Developer PRO" .

Formulation of the problem

We are given an ordered array and a specific value. Then they are asked 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 specified value.

In other words, are there two integers x and y in the array, which 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 returns 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. Brutfors

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

The most obvious meaning is the use of 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 an array, and also compares each pair of indices twice. (For example, when i = 1 and j = 2 is actually the same thing 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 the time complexity O (N²).


Solution 2. Binary (binary) search

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

Since the arrays are ordered, we can search for a solution using binary search. This is the most efficient algorithm for ordered arrays. By itself, a binary search has an O (log (N)) execution time. However, you still need to use a for loop to check each element for 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 array version 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 with the index [0]. It then 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 O (N), but inside the for loop we perform a binary search, which gives the total time complexity 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 is different from the required, then change the starting and ending point.

In the end, we will either meet the desired value and return true, or the start and end points will 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 first simply sort the array, and then use the solution above. But how will this affect the execution time?

The best algorithm is quick sorting with time complexity O (Nlog (N)). 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

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

Yes, a linear solution exists, for this you need to create a new array containing the list of matches we are looking for. There is a trade-off in more active use of memory: this is the only solution in an article with spatial complexity greater than 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 “search values” array.

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 the 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 specified value.

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

 // https://tc39.imtqy.com/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 a while loop in step 7, which (almost) intersects the entire length of the given array. This means that its time 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 impact 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 spatial complexity O (N). Well, the increased memory usage ensures the maximum efficiency of the algorithm.


I hope the article will be useful for you as an application to the 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:

• Applied online course "Python Data Analyst" .
  
• Online course "Profession frontend developer" .
• Practical annual course "PHP developer from 0 to PRO" .