Sliding Window Technique
La más famosa, y más usada, pregunta en una entrevista de programación
Introducción
En muchos ejercicios de programación (véase en Leetcode, o en entrevistas reales) nos encontramos que tenemos que manejar un array o LinkedLists. Se nos pregunta habitualmente sobre encontrar o calcular algo en un subarray de éste. Parece fácil, y de hecho lo es, pero seguro que la siguiente pregunta del entrevistador (lo digo por experiencia) será: ¿Y no conoces alguna manera ara bajar la complejidad temporal?
Pues aquí cuento cómo resolver este tipiquísimo ejercicio, y también cómo mejorar el performance.
El problema
El enunciado al que nos enfrentamos es sencillo y directo. Puede ser algo así:
Given an array, find the average of each subarray of ‘K’ contiguous elements in it.Vamos a ver dicho problema con un ejemplo real:
Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5Chupado, no? Debemos encontrar la media de todos los subarrays consecutivos de tamaño 5. Vamos allá.
Para los primeros 5 números (índices del 0 al 4), la media es: (1 + 3 + 2 + 6 -1)/5 → 2.2
Para los siguientes 5 números consecutivos (índices del 1 al 5), la media es: (3 + 2 + 6 -1 + 4)/5 → 2.8
Para los siguientes 5 (índices del 2 al 6), sería (2 + 6 + 1 + 4 + 1)/5 → 2.4
Lo habéis pillado no? El resultado final sería tal que así:
Output: [2.2, 2.8, 2.4, 3.6, 2.8]La solución
Aplicando Brute Force
La solución más sencilla y directa sería calcular la suma de cada 5 elementos consecutivos durante todo el array y luego dividirlo entre 5. Los resultados los vamos guardando en un array y listo. Veámoslo en Código:
Bonito, no? Evidentemente, nos dará el resultado esperado. Sin embargo…
Time Complexity: Siempre que en un problema de este tipo veamos que hay un bucle for anidado a otro bucle for, podemos sospechar que el código es mejorable en términos de complejidad temporal. En nuestro caso en particular, podemos ver que la complejidad temporal es O(N * K), donde N es el número de elementos del array de entrada.
Así que, aquí está la temida pregunta de nuestro entrevistador: ¿Hay alguna solución más óptima? Por supuesto, sino no hubiera hecho este post :-P
Sliding Window al rescate
Si analizamos bien el flujo del código, veremos que hay una ineficiencia clara. Por cada subarray consecutivo, hay ciertas operaciones (en nuestro caso, la suma de 4 elementos) que se repiten.
La solución, pues, es bastante clara. Debemos encontrar una manera para llegar al mismo resultado, pero evitando repetir la parte ya calculada.
En nuestro caso, vemos que la solución puede consistir simplemente en ver el grupo de la subarray como una “ ventana deslizante”, y ver que al recorrer el array, habrá elementos que entren, y elementos que salgan.
Como simplemente estamos calculando una media, nos bastará con sumar el número que entra en la ventana o subarray, y restar el número saliente. De esta manera, nunca repetimos la parte de en medio, y el algoritmo pasa a tener una complejidad temporal de O(N). Veámoslo en código:
Y ya lo tendríamos!
En el primer bucle for, hemos sumado los primeros K - 1 elementos, para dejar la primera parte de la ventana lista.
En el segundo bucle for, recorremos el array restante “deslizando la ventana”. Vamos añadiendo el último elemento a la suma, calculando la media, y después restando el primer elemento de la ventana.
Much cuidado con las confusiones que pueden surgir debido a que el valor K es un valor con índice 1, mientras que los índices del array siempre empezarán por 0!
Y ya estaría! Si os gusta el contenido de este estilo, tenéis algún resultado mejor, o os gustaría que hiciera más posts acerca de patrones de código vistos en entrevistas de programación, házmelo saber en los comentarios!
Salu2!