Estou retomando o estudo sobre algoritmos e estrutura de dados e semana passada eu resolvi um desafio de código que já foi cobrado pela TwitchTV e por outras Big Tech’s, como Amazon e Google.
A questão resolvida foi a “LRU Cache”, como o nome já diz, o objetivo é implementar uma cache LRU (Least Recently Used). A ideia básica por trás do LRU é manter os itens mais usados recentemente na cache, enquanto remove os menos usados quando a cache fica cheia. Quando você precisa adicionar um novo item à cache e ela está cheia, você remove o item que foi acessado há mais tempo (menos recentemente usado) para liberar espaço para o novo item.
No entanto, o desafio propõe a implementação das funções de recuperação e adição de itens na cache com uma complexidade de tempo constante, O(1). Por essa razão, optei pela utilização de um mapa e uma lista duplamente encadeada.
O mapa possibilita o acesso direto a um nó específico da cache, eliminando a necessidade de percorrer toda a lista para localizá-lo. Por outro lado, a lista duplamente encadeada facilita a ordenação dos elementos com base em seu uso recente, permitindo assim uma gestão eficiente dos itens mais e menos recentemente usados.
De tanto rabiscar para fixar bem o conteúdo eu acabei gravando um vídeo sobre isso e gostei do resultado, então decidi postar. Se você quiser dar uma olhada no passo a passo e qual foi minha estratégia para resolver vou deixar o link aqui:
SOLANDO UM DESAFIO DE CÓDIGO DA TWITCHTV