Mientras estudiaba el rendimiento de los algoritmos, encontré este . No solo proporciona una idea de cómo se llevan a cabo las entrevistas en grandes corporaciones tecnológicas, sino que también permite entender cómo se resuelven problemas algorítmicos de la manera más eficiente.
Este artículo es una especie de acompañamiento al video. En él, doy comentarios sobre todas las soluciones mostradas, además de mi propia versión de la solución en JavaScript. También se discuten los matices de cada algoritmo.
Recordamos: para todos los lectores de «Habr» — un descuento de 10,000 rublos al registrarse en cualquier curso de Skillbox usando el código promocional «Habr».
Skillbox recomienda: Curso práctico .
Planteamiento del problema
Se nos proporciona un arreglo ordenado y un valor específico. Luego se nos pide crear una función que devuelva true o false, dependiendo de si la suma de dos números del arreglo puede ser igual al valor dado.
En otras palabras, ¿existen en el arreglo dos números enteros x e y que sumen el valor indicado?
Ejemplo A
Si se nos da el arreglo [1, 2, 4, 9] y el valor 8, la función devolverá false, ya que ningún par de números del arreglo puede sumar 8.
Ejemplo B
Pero si el arreglo es [1, 2, 4, 4] y el valor es 8, la función debe devolver true, porque 4 + 4 = 8.
Solución 1. Fuerza bruta
Complejidad temporal: O(N²).
Complejidad espacial: O(1).
El enfoque más obvio es utilizar un par de bucles anidados.
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;
};Esta solución no se puede considerar eficiente, ya que verifica cada suma posible de dos elementos en el arreglo y, además, compara cada par de índices dos veces. (Por ejemplo, cuando i = 1 y j = 2 — esto es en realidad lo mismo que comparar con i = 2 y j = 1, pero en esta solución probamos ambas opciones).
Dado que nuestra solución utiliza un par de bucles anidados for, tiene una complejidad cuadrática con complejidad temporal O (N²).
Solución 2. Búsqueda binaria
Complejidad temporal: O(Nlog(N)).
Complejidad espacial: O(1).
Dado que los arreglos están ordenados, podemos buscar una solución utilizando búsqueda binaria. Este es el algoritmo más eficiente para arreglos ordenados. La búsqueda binaria en sí tiene un tiempo de ejecución de O (log (N)). Sin embargo, aún necesitamos usar un bucle for para verificar cada elemento con respecto a todos los demás valores.
Así es como puede verse la solución. Para que todo esté claro, utilizamos una función separada para controlar la búsqueda binaria. También utilizamos la función removeIndex(), que devuelve la versión del arreglo sin el índice especificado.
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;
};El algoritmo comienza con el índice [0]. Luego crea una versión del arreglo excluyendo el primer índice y utiliza la búsqueda binaria para verificar si se puede añadir algún valor restante en el arreglo para alcanzar la suma deseada. Esta acción se realiza una vez por cada elemento en el arreglo.
El bucle for en sí mismo tendrá una complejidad temporal lineal O(N), pero dentro del bucle for realizamos la búsqueda binaria, lo que le da una complejidad temporal total de O(N log(N)). Esta solución es mejor que la anterior, pero aún hay margen para mejorar.
Solución 3. Tiempo lineal
Complejidad temporal: O(N).
Complejidad espacial: O(1).
Ahora resolveremos el problema, recordando que el arreglo está ordenado. La solución consiste en tomar dos números: uno al principio y otro al final. Si el resultado no coincide con lo requerido, cambiamos el punto inicial y final.
Al final, o encontramos el valor deseado y devolvemos true, o los puntos inicial y final se cruzan y devolvemos 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;
};Ahora todo está bien, la solución parece óptima. Pero, ¿quién garantiza que el arreglo estaba ordenado?
¿Qué pasará entonces?
A primera vista, podríamos simplemente ordenar el arreglo primero y luego usar la solución anterior. Pero, ¿cómo afecta esto al tiempo de ejecución?
El mejor algoritmo es el Quick Sort con una complejidad temporal de O(N log(N)). Si lo utilizamos en nuestra solución óptima, cambiará su rendimiento de O(N) a O(N log(N)). ¿Es posible encontrar una solución lineal con un arreglo desordenado?
Solución 4
Complejidad temporal: O(N).
Complejidad espacial: O(N).
Sí, existe una solución lineal, para esto es necesario crear un nuevo arreglo que contenga la lista de coincidencias que estamos buscando. El compromiso aquí es un uso más activo de la memoria: esta es la única solución en el artículo con una complejidad espacial que supera O (1).
Si el primer valor de este arreglo es 1 y el valor buscado es 8, podemos añadir el valor 7 al arreglo de "valores de búsqueda".
Luego, al procesar cada elemento del arreglo, podemos verificar el arreglo de "valores de búsqueda" y ver si alguno de ellos es igual a nuestro valor. Si es así, devolvemos 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;
};La base de la solución es un ciclo for, que, como hemos visto anteriormente, tiene una complejidad temporal lineal O (N).
La segunda parte iterativa de nuestra función es Array.prototype.include (), un método de JavaScript que devolverá true o false dependiendo de si el arreglo contiene el valor dado.
Para determinar la complejidad temporal de Array.prototype.includes (), podemos considerar el polyfill proporcionado por MDN (y escrito en JavaScript), o utilizar el método en el código fuente del motor JavaScript, como 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;
}
});
}Aquí la parte iterativa de Array.prototype.include () es un ciclo while en el paso 7, el cual (casi) atraviesa toda la longitud de este arreglo dado. Esto significa que su complejidad temporal también es lineal. Además, como siempre está un paso detrás de nuestro arreglo principal, la complejidad temporal es O (N + (N - 1)). Al utilizar la Notación Big O, la simplificamos a O (N) — porque es N lo que tiene el mayor impacto a medida que aumenta el tamaño de la entrada.
En cuanto a la complejidad espacial, se requiere un arreglo adicional, cuya longitud refleja el arreglo original (menos uno, sí, pero esto se puede ignorar), lo que resulta en una complejidad espacial O (N). Así, el uso incrementado de memoria asegura la máxima eficiencia del algoritmo.
Espero que el artículo sea útil para ti como complemento a la videoentrevista. Muestra que un problema simple puede resolverse de varias formas diferentes con diferentes cantidades de recursos utilizados (tiempo, memoria).
Skillbox recomienda:
- Curso en línea aplicado .
- Curso en línea .
- Curso práctico de un año .
Fuente: habr.com
