He estado en ambos lados de la mesa de entrevistas técnicas, sobre todo del lado del candidato. La técnica de ventana deslizante aparece constantemente, y separa a los candidatos que han internalizado un patrón de los que intentan derivar la solución desde cero bajo presión. Los primeros terminan antes y explican su razonamiento. Los segundos se quedan sin tiempo. Así es como puedes llegar a ser de los primeros.
Qué es realmente el patrón
La ventana deslizante es una optimización para problemas que involucran secuencias contiguas: subarrays o substrings. El enfoque ingenuo para la mayoría de estos problemas es un bucle anidado que reexamina elementos superpuestos en cada iteración, dando O(n al cuadrado). La ventana deslizante evita esto manteniendo un rango con dos punteros y actualizando el estado incrementalmente a medida que el rango se mueve. La mayoría de los problemas se reducen a O(n).
Hay dos variantes. Ventanas de tamaño fijo: la longitud de la ventana te es dada. Ventanas dinámicas: expandes y contraes según una restricción. Identificar con cuál variante estás tratando es la primera decisión en cualquier problema de entrevista que encaje en este patrón.
Cuándo recurrir a este patrón
- El problema involucra un subarray o substring contiguo
- Te piden encontrar un máximo, mínimo o agregado sobre todas las ventanas de un tamaño dado
- Buscas el substring más largo o más corto que satisfaga una restricción
- La solución de fuerza bruta tiene bucles anidados iterando sobre el mismo array o string
- El problema menciona una 'ventana', 'rango' o elementos 'consecutivos'
Ventana fija: Suma máxima de subarray de tamaño K
Este es el punto de entrada del patrón. Dado un array de enteros y un número k, encuentra la suma máxima de cualquier subarray contiguo de longitud k. El enfoque ingenuo suma k elementos por cada posición de inicio: O(n por k). La ventana deslizante agrega el elemento entrante y elimina el saliente, manteniendo una suma corrida: O(n).
function maxSumSubarray(nums: number[], k: number): number {
if (nums.length < k) return 0;
// Build the first window
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += nums[i];
}
let maxSum = windowSum;
// Slide the window: add incoming, subtract outgoing
for (let i = k; i < nums.length; i++) {
windowSum += nums[i] - nums[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (indices 2-4: 5+1+3)
console.log(maxSumSubarray([2, 3, 4, 1, 5], 2)); // 7 (3+4)La operación clave es windowSum += nums[i] - nums[i - k]. No estás recalculando desde cero. Estás deslizando: agregas el nuevo elemento derecho, eliminas el viejo elemento izquierdo. Esa sola línea es toda la idea de la ventana fija.
Una línea de ese código es una decisión, no un detalle. Devolver 0 cuando el arreglo es más corto que k entrega un valor que una ventana real también podría producir, así que quien llama no puede distinguir 'no hay ventana válida' de 'la mejor ventana suma cero'. Devuelvo 0 acá para mantener el ejemplo corto. En una entrevista, dilo en voz alta y elige a propósito: lanzar un error con entrada inválida, devolver null, o preguntarle al entrevistador cuál debería ser el contrato. Notar que un valor centinela choca con una respuesta legítima es justo el tipo de cosa que están escuchando.
Ventana dinámica: Substring más largo sin caracteres repetidos
Las ventanas dinámicas requieren decidir cuándo contraer. En este problema la restricción es unicidad: cada carácter en la ventana debe aparecer una sola vez. Expande el puntero derecho libremente. Cuando un duplicado entra en la ventana, avanza el puntero izquierdo hasta que el duplicado desaparezca.
function lengthOfLongestUniqueSubstring(s: string): number {
const lastSeen = new Map<string, number>();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
// If we've seen this char and it's inside the current window, jump left past it
if (lastSeen.has(char) && lastSeen.get(char)! >= left) {
left = lastSeen.get(char)! + 1;
}
lastSeen.set(char, right);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
console.log(lengthOfLongestUniqueSubstring('abcabcbb')); // 3 (abc)
console.log(lengthOfLongestUniqueSubstring('pwwkew')); // 3 (wke)Guardar el último índice visto en lugar de borrar entradas del map permite que left salte directo a la posición correcta en vez de avanzar carácter por carácter. Sé preciso sobre qué te da eso, porque un entrevistador lo va a verificar. Ambas versiones son O(n). En la versión que avanza de a un carácter, el puntero left igual se mueve como mucho n veces en todo el bucle, así que el trabajo total es lineal en los dos casos. El salto ahorra operaciones de map y un factor constante, no una clase de complejidad.
La plantilla reutilizable
La mayoría de los problemas de ventana dinámica siguen la misma estructura. Internalizar esta plantilla significa que dedicarás el tiempo de la entrevista a la lógica específica del problema, no al andamiaje que ya has resuelto antes.
function dynamicWindowTemplate(input: string | number[]): number {
let left = 0;
let result = 0;
const windowState = new Map<string | number, number>();
for (let right = 0; right < input.length; right++) {
const incoming = input[right];
// 1. Add incoming element to window state
windowState.set(incoming, (windowState.get(incoming) ?? 0) + 1);
// 2. Shrink window while constraint is violated
while (/* window constraint violated */ false) {
const outgoing = input[left];
const count = windowState.get(outgoing)! - 1;
if (count === 0) {
windowState.delete(outgoing);
} else {
windowState.set(outgoing, count);
}
left++;
}
// 3. Update result with current valid window
result = Math.max(result, right - left + 1);
}
return result;
}Reconocer el patrón en una entrevista
- ¿El problema dice 'subarray', 'substring' o 'contiguo'? La ventana deslizante es el patrón candidato.
- ¿Te dan k? Ventana fija. ¿Hay una restricción que satisfacer? Ventana dinámica.
- ¿La solución de fuerza bruta requiere bucles anidados sobre los mismos datos? Estás ante O(n al cuadrado) y la ventana deslizante lo resolverá.
- ¿Puedes describir el problema como: encontrar el rango óptimo que satisfaga alguna condición? Ese es un problema de ventana deslizante.
En una entrevista en pizarra, nombrar el patrón en voz alta antes de escribir código señala reconocimiento de patrones. Esa es una de las señales más valoradas que un entrevistador busca.
Practica los problemas de suma máxima con ventana fija y substring único más largo con ventana dinámica hasta que se sientan mecánicos. Esos dos cubren las dos variantes estructurales. Cada otro problema de ventana deslizante que encuentres en una entrevista es una variación de uno de ellos. Una vez que la plantilla está internalizada, el tiempo de la entrevista se dedica a la lógica específica de la restricción, que es la parte que realmente evalúa la capacidad de resolver problemas.
Referencias
- LeetCode. Problemas de ventana deslizante. https://leetcode.com/tag/sliding-window/
- GeeksforGeeks. Técnica de ventana deslizante. https://www.geeksforgeeks.org/window-sliding-technique/
- MDN Web Docs. JavaScript Array. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array