¡Se trata de patrones!

Una vez que aprendes los patrones, ¡todo empieza a parecer un poco más fácil! Si eres como yo, probablemente no te gusten las entrevistas técnicas y no te culpo: pueden ser difíciles.

Los problemas de matriz son algunos de los más comunes que encontrará en las entrevistas. Estos problemas a menudo implican trabajar con matrices naturales:

const arr = [1, 2, 3, 4, 5];

Y problemas de cadenas, que son esencialmente matrices de caracteres:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

Uno de los patrones más comunes para resolver problemas de matrices es la ventana deslizante.

Patrón de ventana corrediza

El patrón de ventana deslizante implica dos punteros que se mueven en la misma dirección, como una ventana que se desliza a través de la matriz.

Cuando usarlo

Utilice el patrón de ventana deslizante cuando necesite encontrar una submatriz o subcadena que satisfaga una determinada condición, como ser la mínima, máxima, más larga o más corto.

Regla 1: Si necesita encontrar una submatriz o una subcadena y la estructura de datos es una matriz o una cadena, considere usar el patrón de ventana deslizante.

Ejemplo sencillo

Aquí hay un ejemplo básico para presentar el concepto de punteros en una ventana deslizante:

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l   1;  // Right pointer

    while (r 



Tenga en cuenta que los punteros izquierdo (L) y derecho (R) no tienen que moverse al mismo tiempo, pero deben moverse en la misma dirección.



El puntero derecho nunca será más bajo que el puntero izquierdo.

Exploremos este concepto con un problema de entrevista real.


  
  
  Problema del mundo real: subcadena más larga sin caracteres repetidos


Problema: Dada una cadena s, encuentre la longitud de la subcadena más larga sin caracteres repetidos.

Palabras clave: sub-cadena, más larga (máxima)


function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right = left) {
            left = hash[str[right]]   1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left   1);
    }

    return longest;
}




No te preocupes si esto parece complicado: lo analizaremos poco a poco.


let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5




El núcleo de este problema es encontrar la subcadena más larga sin caracteres repetidos.


  
  
  Ventana inicial: tamaño 0


Al principio, los punteros izquierdo (L) y derecho (R) están en el mismo lugar:


let left = 0;

for (let right = 0; right 





h e l l o w o r l d 
^
^
L
R




Y tenemos un hash (objeto) vacío:


let hash = {};




¿Qué tienen de bueno los objetos? Almacenan claves únicas, que es exactamente lo que necesitamos para resolver este problema. Usaremos hash para rastrear todos los personajes que hemos visitado y verificar si hemos visto el personaje actual antes (para detectar duplicados).

Al observar la cadena, podemos ver visualmente que world es la subcadena más larga sin caracteres repetidos:


h e l l o w o r l d 
          ^        ^   
          L        R




Esto tiene una longitud de 5. Entonces, ¿cómo llegamos allí?

Vamos a desglosarlo paso a paso:


  
  
  Estado inicial




hash = {}

h e l l o w o r l d 
^
^
L
R





  
  
  Iteración 1:


En cada iteración, agregamos el carácter debajo del puntero R al mapa hash e incrementamos:


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);




Actualmente, no hay caracteres repetidos en nuestra ventana (h y e):


hash = {h: 0}
h e l l o w o r l d 
^ ^
L R





  
  
  Iteración 2:




hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R




Ahora tenemos una nueva ventana: hel.


  
  
  Iteración 3:




hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R




Aquí es donde se pone interesante: ya tenemos l en nuestro hash y R apunta a otra l en la cadena. Aquí es donde entra nuestra declaración if:


if (hash[str[right]] !== undefined)




Si nuestro hash contiene la letra a la que apunta R, ¡hemos encontrado un duplicado! La ventana anterior (hel) es la más larga hasta ahora.

 Entonces, ¿qué hacemos a continuación? Reducimos la ventana desde la izquierda moviendo el puntero L hacia arriba ya que ya procesamos la subcadena izquierda. ¿Pero hasta dónde avanzamos L?


left = hash[str[right]]   1;




Movemos L justo después del duplicado:


hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R




Aún agregamos nuestro duplicado al hash, por lo que L ahora tendrá un índice de 3.


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);





  
  
  Nuevo estado: iteración 4




hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R





  
  
  Iteraciones 4 a 6




hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R




Cuando R apunta a otro duplicado (o), movemos L justo después de la primera o:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R




Continuamos hasta encontrar otra l duplicada:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R




¡Pero observe que está fuera de la ventana actual! comenzando desde w, 


  
  
  Regla 3: ignorar el sub-x procesado


Todo lo que esté fuera de la ventana actual es irrelevante: ya lo hemos procesado. El código clave para gestionar esto es:


if (hash[str[right]] !== undefined && hash[str[right]] >= left)




Esta condición garantiza que solo nos preocupamos por los caracteres dentro de la ventana actual, filtrando cualquier ruido.


hash[str[right]] >= left




Nos centramos en cualquier cosa más grande o igual al puntero izquierdo


  
  
  Iteración final:




hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R




Sé que esto fue detallado, pero dividir los problemas en patrones o reglas más pequeños es la forma más fácil de dominarlos.


  
  
  En resumen:

• Regla 1: Las palabras clave del problema (por ejemplo, máximo, mínimo) son pistas. Este problema consiste en encontrar la subcadena más larga sin caracteres repetidos.
• Regla 2: Si necesita encontrar elementos únicos o que no se repitan, piense en mapas hash.
• Regla 3: Céntrate en la ventana actual; cualquier cosa fuera de ella es irrelevante.

Consejos adicionales:

• Desglosa el problema y hazlo detallado usando un pequeño subconjunto.
• Al maximizar la ventana actual, piense en cómo hacerla lo más larga posible. Por el contrario, al minimizar, piense en cómo hacerlo lo más pequeño posible.

Para resumir, ¡aquí tienes un pequeño desafío que puedes probar! Publicaré mi solución en los comentarios; es una excelente manera de practicar.

Problema 2: suma mayor o igual al objetivo

Dada una matriz, encuentre la submatriz más pequeña con una suma igual o mayor que el objetivo (mi solución será el primer comentario).

/**
 * 
 * @param {Array} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

Recuerde, como todo en programación, ¡la repetición es clave! Los problemas con las ventanas deslizantes surgen todo el tiempo, así que no dudes en buscar más ejemplos en Google y seguir practicando.

Seré breve, pero estad atentos: el próximo artículo profundizará en el patrón de dos punteros y la recursividad (preparación para problemas de árboles). ¡Va a ser un poco más desafiante!

Si quieres más contenido exclusivo, puedes seguirme en Twitter o Ko-fi. ¡Estaré publicando algunas cosas adicionales allí!

Recursos:

Manual de entrevistas técnicas

matrices de código leet 101