Patrón 1: La ventana deslizante — Triunfando en la entrevista de código
La ventana deslizante es un patrón muy empleado en problemas en los que se usan arreglos(o listas enlazadas). Debido a que usaremos Python 🐍 nosotros hablaremos de listas.
¿Qué es una lista 📝?
Una lista es una secuencia ordenada de elementos la cual puedes cambiar o modificar. Para crear una lista en Python utilizamos corchetes [ ] .
Usamos listas cuando queremos mantener ciertos valores que se relacionan unidos y también para poder preservar su orden, por ejemplo:
lista_de_compras = ['leche', 'harina', 'huevo']
animales_marinos = ['delfin', 'tiburon', 'calamar']
dias_de_la_semana = ['lunes', 'martes', 'miercoles', ... ]
calificaciones = [10.0, 7.8, 6.5, 8.0, 9.2]A cada elemento de la lista le corresponde un número llamado índice, que empieza en 0.
Accedemos al elemento que queramos poniendo su indice entre corchetes.
leche = lista_de_compras[0]
harina = lista_de_compras[1]
huevo = lista_de_compras[2]¿Cómo identificar un problema que usa la ventana deslizante 🤓?
Podemos identificar este patrón cuando el problema nos pide encontrar o calcular algo en todas las sublistas contiguas de un tamaño determinado.
Para que quede más claro pondremos un problema de ejemplo:
Dada una lista de calificaciones, encuentra el promedio de todas las sublistas contiguas de tamaño “k”Usando entradas reales:
calificaciones = [10.0, 7.8, 6.5, 8.0, 9.2]
k = 3Nos piden calcular el promedio de calificaciones para todas las sublistas de tamaño 3. Así que vamos a resolverlo 👊
Paso 1: Dividir nuestra lista en sublistas
Paso 2: Calcular el promedio para cada sublista
- Sublista 1: (10.0 + 7.8 + 6.5) / 3=> 8.1
- Sublista 1: (7.8 + 6.5 + 8.0) / 3=> 7.43
- Sublista 1: (6.5 + 8.0 + 9.2) / 3=> 7.9
Resultado
Promedios: [8.1, 7.43, 7.9]Una solución de fuerza bruta(no usa el patrón de ventana deslizante) sería:
El problema con esta solución es que para cada sublista consecutiva los elementos que se repiten en ambas listas serán evaluados dos veces. 😣
Como puedes ver, para nuestras sublistas 1 y 2, los elementos repetidos y que serán sumados dos veces son 7.8 y 6.5. Pero debe de haber una manera de reutilizar la suma utilizada por ambos elementos, ¿no? 🤔
La ventana deslizante
Una manera más eficiente de resolver este problema sería imaginarnos cada sublista como una ventana deslizante. Lo que significa que cuando pasamos a la siguiente sublista, deslizamos nuestra ventana un elemento, lo que nos evita tener que recorrer toda la sublista de nuevo para encontrar la suma. 🤯
La solución programada en python 🎉:
Explicación del código 🚀
for fin_ventana in range(len(calificaciones)):
suma_ventana += calificaciones[fin_ventana]Sumamos los primeros k elementos y almacenamos la suma en la variable suma_ventana. En las primeras 3 iteraciones tendríamos 10.0 + 7.8 + 6.5 y nuestra variable suma_ventana = 24.3.
if fin_ventana >= k — 1:
resultado.append(suma_ventana / k)Aquí llegamos al fin de nuestra ventana, por lo que guardamos el promedio en nuestra variable resultado.
suma_ventana -= calificaciones[inicio_ventana]
inicio_ventana += 1A nuestra suma_ventana le restamos el primer valor de la ventana actual (10.0) y deslizamos nuestra ventana. Ahora el inicio de la ventana será 7.8 y el fin será 8.0.
En el resto de iteraciones la ventana seguirá deslizándose y seguiremos modificando el valor de suma_ventana restando la calificación que salió de la ventana y sumando la que acaba de entrar. ¡Y listo! 🤩
La práctica lo es todo
¡La única forma de perfeccionar cualquier habilidad es practicando! En el siguiente repositorio encontrarás una lista de problemas que te sugiero resolver.
Te recomiendo que le dediques 20–25 minutos a resolver cada uno. Si no lo logras resolver en este tiempo, puedes irte al branch soluciones donde encontrarás el problema resuelto, trata de entenderlo por a lo mucho 15 minutos para pasar al siguiente problema y al día siguiente o después de un tiempo considerable intentarlo de nuevo.
¿Tienes alguna duda, sugerencia u opinión? ¡No olvides dejarla en los comentarios!
Mis artículos son gratuitos pero siempre puedes apoyarme dejando apretado el botón de aplauso y regalarme 50 👏, eso me motiva a seguir escribiendo.
Puedes seguir la charla en Twitter, Github, LinkedIn, Instagram o mandarme un correo a alexmaguey1@gmail.com
¡Gracias por leer y hasta la próxima!
