Algoritmos para Desafio Internacional [1]: Sliding Window Approach

Publicado em: Dezembro 21, 2023 (Deevi)

Você pretende trabalhar para empresas internacionais? Você sabia que muitas empresas prezam mais por estrutura de dados à frameworks?

Sabendo disso, conhecer estratégias para aumentar a performance do seu código é indispensável. Aqui começamos uma saga em busca de algoritmos que podem ser úteis na realização de testes!

Window Sliding Technique

Conceito

O Window Sliding Technique é uma técnica computacional que podemos utilizar para redução de nested loops, fazendo com que tenhamos apenas um único loop, reduzindo assim, a complexidade algorítmica.

https://dev.to/mwong068/sliding-window-technique-in-ruby-3og4

O algoritmo é bem simples e pode ser utilizado em cenários específicos e comumente cobrados em entrevistas internacionais:

  1. A ideia é aplicar uma operação ou subalgoritmo em uma janela específica de dados com tamanho fixo, no nosso exemplo observa que: janela_especifica = 4 e tamanho_dados = 8
  2. Na primeira rodada: nosso sliding window irá pegar os valores [1,15,1,2] para realizar determinada operação. 
  3. Um outro ponto importante é observar que, ao andar (slide one element forward), temos apenas a inserção do número 6, ficando: [15,1,2,6]

Exercício: Digamos que foi solicitado que você desenvolver uma função para calcular o maior valor da soma de uma janela específica. Por exemplo:
Janela=3

Lista=[1,3,4,5,7]

Maior Janela=16 que é a soma de: [4,5,7]

Exemplo sem:

Resolvemos o problema, mas observe que esse algoritmo tem complexidade: 

Complexidade aproximada: O(n * janela)

Resultado aproximado: 4.12464141845s 

Exemplo com:

Complexidade aproximada: O(n)

Resultado aproximado: 1.168251037s

Exemplos de testes (Uso)

  • Hackerrank; 
  • Letcoode: https://leetcode.com/problems/count-sorted-vowel-strings/
  • Cálculos em “sublistas”

Lembre-se, basta aprender o conceito, saber como funciona para quando solicitado um cenário em que o Sliding Window Approach seja aplicável, saber implementar.

Referências