En las entrevistas que suelen realizar para los puestos de desarrollador de software es muy común que nos pongan problemas para resolver compartiendo nuestra pantalla al entrevistador. Dichos problemas suelen tener diferentes complejidades pero podemos hacer uso de algunos patrones de código para resolverlos.

A continuación veremos uno conocido como el patrón Sliding Window (Ventana Deslizante) y veremos algunos ejemplos para entenderlo mejor. Dicho patrón nos podrá ayudar a resolver las clásicas preguntas o ejercicios de encontrar la cadena/subarreglo más largo o corto o a realizar el cálculo que se desea de un subarreglo.

Como primer resolveremos un problema que suele preguntarse o que solemos encontrar en plataformas como leetcode y HackerRank, el cuál es:

Dado un arreglo de enteros y un número que representa la longitud del subarreglo, encuentre la suma máxima del subconjunto contiguo de longitud.

Veamos como solucionar dicho problema haciendo algo llamado método por fuerza bruta:

// Brute Force Solution
function findMaxSubarraySum(nums, k) {
  let maxSum = -Infinity;

  if (nums.length < k) {
    return null;
  }

  for (let i = 0; i< nums.length - k + 1; i++) {
    let tempSum = 0;
    for (let j = i; j < i + k; j++){
      tempSum += nums[j];
      
    }
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

Si le pasamos el arreglo [1, 12, -5, -6, 50, 3] y k=4. la respuesta sería 51. Esto es debido a que la suma del subarreglo [12, -5, -6, 50] nos devuelve ese resultado y es el mayor de todas las combinaciones de subarreglos que se hacen.

La solución anterior es correcta, y seguramente es la primera que pasaría por nuestra mente tomando en cuenta los nervios de una entrevista, pero no es la mejor ya que su tiempo de complejidad es de O(n*k), donde n equivale al número de elementos en el arreglo y k al número de elementos que contiene el subarreglo, lo cuál quiere decir que mientras mas grande sea la longitud del  arreglo que le pasamos, al igual que el subarreglo, el tiempo en que nos devuelva la solución puede ser muy elevado. Si quieres saber mas sobre Big O puede ver los siguients links - Big O by HackerRank y Notación Asintótica.

Si analizamos bien podríamos decir que los subarreglos son ventanas y ésta se va moviendo como se aprecia en la siguiente imagen:

Imagen obtenida de la siguiente url

¿Cómo podríamos aprovechar lo anterior para resolver el ejercicio de una forma mas eficiente?

La solución es usar el patrón: Sliding Window

Para ello, podríamos reutilizar la variable tempSum en nuestra solución anterior e irle restando el elemento que se sale de la ventana al moverse, así como sumándole el nuevo elemento que entra y con ello podríamos obtener un tiempo de complejidad de O(n), donde n equivale al número de elementos en el arreglo.

Tomemos como ejemplo la imagen anterior, inicialmente se suman los valores en el subarreglo [1,3,2,8,-1] y se asigna a tempSum, cuando se mueve la ventana el primer elemento, 1, sale y entra el 4 por lo que a tempSum se le resta el valor 1 y se le suma el valor 4. Veamos el código para que quede más claro:

// Sliding Window
function findMaxSubarraySum(nums, k) {
  let maxSum = -Infinity;
  let tempSum = 0;
  let start = 0; // indice que ayudará a mover la ventana

  if (nums.length < k) {
    return null;
  }

  for (let end = 0; end < nums.length; end++) {
    tempSum += nums[end]; // suma al elemento que entra a la ventana

    if (end >= k - 1) {
      maxSum = Math.max(maxSum, tempSum);
      tempSum -= nums[start]; // se sustrae el elemento que sale
      start += 1; // desliza la ventana
    }
  }
  return maxSum;
}

Si analizamos el código, observaremos que ahora solamente se tiene un ciclo for y se cuenta con una variable llamada start la cual ayudará a ir moviendo la ventana hacia el último elemento, y cada que se realiza el movimiento se suma el valor del elemento que entra a la ventana y dentro del condicional if se realiza la resta del valor del elemento que sale de la ventana al mismo tiempo que se incrementa en uno la variable start.

Veamos otro ejemplo

Dada una cadena, encuentre la máxima longitud de una subcadena con todos los caracteres distintos, por ejemplo: Hola mundo -> Hola mund, aabcb -> abc.

La siguiente función hace uso de Sliding Window y devuelve un entero que representa la longitud máxima de la subcadena encontrada.

// Sliding Window O(n)
function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;
  
  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    if (seen[char]) {
      start = Math.max(start, seen[char]);
    }
    // index - beginning of substring + 1 (to include current in count)
    longest = Math.max(longest, i - start + 1);
    // store the index of the next char so as to not double count
    seen[char] = i + 1;
  }
  return longest;
}

Si le pasamos a la función la siguiente cadena findLongestSubstring('aabcb'), nos devolvería como resultado 3:

La longitud máxima de la ventana es de 3 caracteres [a,b,c]

Si analizamos la función anterior, veremos que la variable start ayuda a ir moviendo la ventana, representa desde que elemento se toma la ventana y longest representa la longitud de la ventana. Es importante señalar que en este caso se esta usando una estructura de datos de llave-valor (objetos en js o diccionarios en python) para ir almacenando los caracteres que se van sacando de la cadena con el fin de poder encontrar de forma constante los caracteres para verificar si se han repetido y ello no afecte a nuestro algoritmo.

¿Cómo identifico que en un problema dado podría utilizar o requerir de esta técnica?

  • La entrada debe ser una estructura de datos lineal tal como una lista ligada, arreglo o cadena.
  • El problema especifica encontrar la subcadena, subarreglo mas largo o corto o el valor deseado.
  • Existe una aparente solución ingenua o de fuerza bruta que se ejecuta en O (n^2), O (2^n) o alguna otra complejidad de tiempo superior.

Algunos de los problemas más comunes que suele preguntarse son:

  • Suma Máxuma de un subarreglo de longitud K (el que ya hemos resuelto)
  • La subcadema las larga con K caracteres distintos (el segundo ejemplo que resolvimos)
  • Anagramas

Se podría decir que existen dos tipos de ventanas, una de tamaño fijo y otra de tamaño dinámico, tal como hemos visto en los ejemplos. La ventana de tamaño fijo se puede usar para el problema en el que desea determinar si la cadena dada contiene una subcadena específica, ya que podemos encontrar fácilmente la longitud fija de la subcadena. Por otro lado, la dinámica se puede usar para encontrar la subcadena más larga o más corta de la cadena dada.

Lo sorprendente de los problemas de Sliding Window (ventana deslizante) es que la mayoría de las veces se pueden resolver en O(N) tiempo y O(1) complejidad de espacio.

Si tienes más ejemplos que puedan resolverse puedes añadirlo en los comentarios para compartirlo, y si ya tienes el código mucho mejor.

Hasta la próxima.