Cuando estaba estudiando el rendimiento de los algoritmos, me encontré con
este video de la entrevista simulada de Google . No solo da una idea de cómo se realizan las entrevistas en las grandes corporaciones tecnológicas, sino que también le permite comprender cómo se resuelven los problemas algorítmicos y de la manera más efectiva.
Este artículo es una especie de acompañamiento al video. En él, doy comentarios sobre todas las soluciones mostradas, más mi propia versión de la solución en JavaScript. También se discuten los matices de cada algoritmo.
Le recordamos: para todos los lectores de "Habr": un descuento de 10.000 rublos al registrarse en cualquier curso de Skillbox con el código de promoción "Habr".
Skillbox recomienda: Curso práctico "Mobile Developer PRO" .
Declaración del problema.
Se nos da una matriz ordenada y un valor específico. Luego, solicitan crear una función que devuelva verdadero o falso, dependiendo de si la suma de dos números de la matriz puede ser igual al valor dado.
En otras palabras, ¿hay dos enteros x e y en la matriz que, cuando se agregan, son iguales al valor especificado?
Ejemplo ASi nos dieran una matriz [1, 2, 4, 9] y un valor de 8, la función devolverá falso, porque no hay dos números de la matriz que puedan dar 8 en total.
Ejemplo BPero si es una matriz [1, 2, 4, 4] y el valor es 8, la función debería devolver verdadero, porque 4 + 4 = 8.
Solución 1. Fuerza brutaDificultad temporal: O (N²).
Complejidad espacial: O (1).El significado más obvio es usar 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 puede llamarse efectiva, ya que verifica cada suma posible de dos elementos en la matriz, y también compara cada par de índices dos veces. (Por ejemplo, cuando i = 1 y j = 2, esto es realmente lo mismo que comparar con i = 2 y j = 1, pero en esta solución probamos ambas opciones).
Como nuestra solución utiliza un par de bucles anidados, es cuadrática con una complejidad temporal de O (N²).
Solución 2. Búsqueda binaria (binaria)Dificultad temporal: O (Nlog (N)).
Complejidad espacial: O (1) .
Dado que las matrices están ordenadas, podemos buscar una solución utilizando la búsqueda binaria. Este es el algoritmo más eficiente para las matrices ordenadas. La búsqueda binaria en sí tiene un tiempo de ejecución O (log (N)). Sin embargo, aún necesita usar un bucle for para verificar cada elemento contra todos los demás valores.
Así es como se vería la solución. Para aclarar todo, utilizamos una función separada para controlar la búsqueda binaria. Además de la función removeIndex (), que devuelve la versión de la matriz menos el índice especificado.
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; };
El algoritmo comienza en el índice [0]. Luego crea una versión de la matriz, excluyendo el primer índice, y utiliza una búsqueda binaria para verificar si alguno de los valores restantes se pueden agregar a la matriz para obtener la cantidad deseada. Esta acción se realiza una vez para cada elemento de la matriz.
El ciclo for en sí tendrá una complejidad de tiempo lineal de O (N), pero dentro del ciclo for realizaremos una búsqueda binaria, que proporciona la complejidad de tiempo total de O (Nlog (N)). Esta solución es mejor que la anterior, pero todavía hay algo que mejorar.
Solución 3. Tiempo linealDificultad temporal: O (N).
Complejidad espacial: O (1).Ahora resolveremos el problema, recordando que la matriz está ordenada. La solución es tomar dos números: uno al principio y otro al final. Si el resultado difiere del requerido, entonces cambiamos los puntos de inicio y finalización.
Al final, cumplimos con el valor deseado y devolvemos verdadero, o los puntos inicial y final convergen y devuelven falso.
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; };
Ahora todo está bien, la solución parece ser óptima. Pero, ¿quién garantizará que se ordenó la matriz?
Entonces que?
A primera vista, podríamos ordenar primero la matriz y luego usar la solución anterior. Pero, ¿cómo afectará esto al tiempo de ejecución?
El mejor algoritmo es la clasificación rápida con complejidad de tiempo O (Nlog (N)). Si lo usamos en nuestra solución óptima, cambiará su rendimiento de O (N) a O (Nlog (N)). ¿Es posible encontrar una solución lineal con una matriz desordenada?
Decisión 4Dificultad temporal: O (N).
Complejidad espacial: O (N).Sí, existe una solución lineal, para esto necesita crear una nueva matriz que contenga una lista de coincidencias que estamos buscando. La compensación aquí es el uso más activo de la memoria: esta es la única solución en el artículo con una complejidad espacial superior a O (1).
Si el primer valor de esta matriz es 1 y el valor de búsqueda es 8, podemos agregar el valor 7 a la matriz de "valores de búsqueda".
Luego, procesando cada elemento de la matriz, podemos verificar la matriz de "valores de búsqueda" y ver si uno de ellos es igual a nuestro valor. En caso afirmativo, devuelva verdadero.
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 el ciclo for, que, como vimos anteriormente, tiene una complejidad lineal de tiempo O (N).
La segunda parte de iteración de nuestra función es Array.prototype.include (), un método de JavaScript que devolverá verdadero o falso dependiendo de si la matriz contiene el valor dado.
Para conocer la complejidad temporal de Array.prototype.includes (), podemos ver el polyfill proporcionado por MDN (y escrito en JavaScript), o usar un método en el código fuente de un motor de JavaScript como Google V8 (C ++).
Aquí, la parte iterativa de Array.prototype.include () es el ciclo while en el paso 7, que (casi) atraviesa la longitud completa de la matriz dada. Esto significa que su complejidad temporal también es lineal. Bueno, dado que siempre está un paso por detrás de nuestra matriz principal, la complejidad del tiempo es O (N + (N - 1)). Usando Big O Notation, lo simplificamos a O (N), porque es N el que tiene la mayor influencia al aumentar el tamaño de entrada.
En cuanto a la complejidad espacial, se necesita una matriz adicional, cuya longitud refleja la matriz original (menos uno, sí, pero esto puede ignorarse), lo que conduce a la complejidad espacial de O (N). Bueno, el mayor uso de memoria garantiza la máxima eficiencia del algoritmo.
Espero que este artículo le sea útil como archivo adjunto a una entrevista en video. Muestra que un problema simple puede resolverse de diferentes maneras con diferentes cantidades de recursos utilizados (tiempo, memoria).
Skillbox recomienda: