While I was studying algorithm performance, I came across this . It not only provides insight into how interviews are conducted at major tech corporations, but also helps understand how algorithmic problems are solved, and in the most efficient way possible.
This article serves as a companion to the video. In it, I provide comments on all the solutions shown, plus my own version of the solution in JavaScript. The nuances of each algorithm are also discussed.
Reminder: for all readers of 'Habr' - a discount of 10,000 rubles when enrolling in any Skillbox course with the promo code 'Habr'.
Skillbox recommends: Practical Course .
Task Definition
We are given a sorted array and a specific value. We are then asked to create a function that returns true or false, depending on whether the sum of any two numbers from the array can equal the given value.
In other words, are there two integers x and y in the array that add up to the specified value?
Example A
If we are given the array [1, 2, 4, 9] and the value 8, the function will return false because no two numbers from the array can add up to 8.
Example B
But if it is the array [1, 2, 4, 4] and the value 8, the function should return true because 4 + 4 = 8.
Solution 1: Brute Force
Time complexity: O(NĀ²).
Space complexity: O(1).
The most obvious approach 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 considered efficient, as it checks every possible sum of two elements in the array, and compares each pair of indices twice. (For example, when i = 1 and j = 2 ā this is actually the same as comparing i = 2 and j = 1, but this solution tries both combinations).
Since our solution uses a pair of nested for loops, it is quadratic with a time complexity of O(NĀ²).
Solution 2: Binary Search
Time complexity: O(Nlog(N)).
Space complexity: O(1).
Since the arrays are sorted, we can look for a solution using binary search. This is the most efficient algorithm for sorted arrays. Binary search itself has a runtime of O(log(N)). However, we still need to use a for loop to check each element against all other values.
Here is how the solution might look. To make everything clear, we use a separate function for controlling binary search. We also use the removeIndex() function, which returns a version of the array minus the specified index.
const findSum = (arr, val) => {
for (let i = 0; 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]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};The algorithm starts with index [0]. It then creates a version of the array excluding the first index and uses binary search to check if any of the remaining values can be added to the array to achieve the desired sum. This action is performed once for each element in the array.
The for loop itself will have linear time complexity O(N), but inside the for loop, we perform a binary search, resulting in a total time complexity of O(N log(N)). This solution is better than the previous one, but there is still room for improvement.
Solution 3. Linear time
Time complexity: O(N).
Space complexity: O(1).
Now we will approach the problem knowing 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 value, we adjust the starting and ending points.
In the end, we either find the desired value and return true, or the starting and ending points converge and we return false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};Now everything seems fine, and the solution appears to be optimal. But who can guarantee that the array was sorted?
What then?
At first glance, we could simply sort the array first and then use the above solution. But how would that affect execution time?
The best algorithm is quicksort with a time complexity of O(N log(N)). If we use that in our optimal solution, it will change its performance from O(N) to O(N log(N)). Is it possible to find a linear solution with an unordered array?
Solution 4
Time complexity: O(N).
Space complexity: O(N).
Yes, a linear solution exists; to achieve this, we need to create a new array containing the list of matches we are looking for. The compromise here is a more active use of memory: this is the only solution in the article with a space complexity exceeding O(1).
If the first value of this array is 1 and the target value is 8, we can add the value 7 to the 'search values' array.
Then, by processing each element of the array, we can check the 'search values' array and see if any of them equals our value. If so, we 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 foundation of the solution is a for loop, which, as we saw above, has a linear time complexity of O(N).
The second iterative part of our function is Array.prototype.includes(), a JavaScript method that will return true or false depending on whether the array contains the specified value.
To determine the time complexity of Array.prototype.includes(), we can consider the polyfill provided by MDN (and written in JavaScript) or refer to the method in the source code of a JavaScript engine like 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.includes() is a while loop at step 7, which (almost) traverses the entire length of the given array. This means its time complexity is also linear. And 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 N has the most significant impact as the input size increases.
Regarding space complexity, an additional array is needed, the length of which reflects the original array (minus one, yes, but this can be ignored), resulting in a space complexity of O(N). The increased memory usage ensures optimal efficiency of the algorithm.
I hope the article will be useful for you as an appendix to the video interview. It shows that a simple task can be solved in several different ways with varying amounts of resources used (time, memory).
Skillbox recommends:
- Applied Online Course .
- Online Course .
- Practical Year Course .
Source: habr.com
