When I was studying the performance of algorithms, I came across this . It not only gives an idea of how interviews are conducted in large technology corporations, but also allows you to understand how algorithmic tasks are solved, and as efficiently as possible.
This article is a kind of accompaniment to the video. In it, I comment on all the solutions shown, plus my own JavaScript version of the solution. The nuances of each algorithm are also discussed.
We remind you: for all readers of "Habr" - a discount of 10 rubles when enrolling in any Skillbox course using the "Habr" promotional code.
Skillbox recommends: Practical course .
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 given value.
In other words, are there two integers x and y in the array that, when added together, are equal to the specified value?
Example A
If we are given an array [1, 2, 4, 9] and the value is 8, the function will return false because no two numbers in the array can add up to 8.
Example B
But if it's an array [1, 2, 4, 4] and the value is 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 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 is not efficient, as it checks every possible sum of two elements in the array, and also compares each index pair twice. (For example, when i = 1 and j = 2 is actually the same as comparing with i = 2 and j = 1, but in this solution we try both options).
Because our solution uses a couple of nested for loops, it is quadratic with O(N²) time complexity.
Solution 2: Binary (Binary) Search
Time complexity: O(Nlog(N)).
Space 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, binary search has a runtime of O(log(N)). However, you still need to use a for loop to check each element against all other values.
Here's what the solution might look like. To be 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 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 from index [0]. It then creates a version of the array, excluding the first index, and uses a binary search to see if any of the remaining values can be added to the array to get the desired sum. This action is performed once for each element in the array.
By itself, the for loop will have a linear time complexity of O(N), but inside the for loop, we are doing a binary search, giving an overall time complexity of O(Nlog(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 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 change the start and end points.
Eventually, 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 have just sorted the array first and then used the solution above. But how will this affect the execution time?
The best algorithm is quicksort with O(Nlog(N)) time complexity. If we use it in our optimal solution, it changes 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).
Space complexity: O(N).
Yes, there is a linear solution, for this we need to create a new array containing the list of matches we are looking for. The trade-off here is more memory usage: this is the only solution in the article with a space complexity greater than O(1).
If the first value of the given array is 1 and the lookup 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 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 a linear time complexity of 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 figure out the time complexity of Array.prototype.includes(), we can consider a polyfill provided by MDN (and written in JavaScript) or use a method in the source code of a JavaScript engine such as Google's 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 iteration part of Array.prototype.include() is the while loop in step 7 that (almost) traverses 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 influence when increasing the input size.
In terms of space complexity, an additional array is needed whose length reflects the original array (minus one, yes, but that can be ignored), resulting in O(N) space complexity. Well, the increased memory usage ensures the maximum efficiency of the algorithm.
I hope the article will be useful for you as an attachment 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 .
- Online course .
- Practical year course .
Source: habr.com