coderbyte chall

lru_cache_algorithm.js

function LRUCache(strArr) {
  const CACHE_SIZE = 5


  const cache = []
  // // console.time('ARRAY_PERFORMANCE')
  // strArr.forEach(
  //   char => {
  //     const charIndex = cache.indexOf(char)
  //     if (charIndex === -1) {
  //       if (cache.length == CACHE_SIZE) {
  //         cache.shift()
  //       }
  //       cache.push(char)
  //     } else {
  //       cache.splice(charIndex, 1)
  //       cache.push(char)
  //     }
  //   }
  // )
  // // console.timeEnd('ARRAY_PERFORMANCE')
  // return cache.join('-')


  const cacheMap = new Map()
  // console.time('MAP_PERFORMANCE')
  strArr.forEach(
    char => {
      if (cacheMap.has(char)) {
        cacheMap.delete(char)
      } else if (cacheMap.size === CACHE_SIZE) {
        cacheMap.delete(cacheMap.keys().next().value)
      } 
      cacheMap.set(char, true)
    }
  )
  // console.timeEnd('MAP_PERFORMANCE')
  return Array.from(cacheMap.keys()).join('-')

}

// keep this function call here 
console.log(LRUCache(readline()));


/*

- constrain: input contain characters ranging from A to Z in some arbitrary order
- constrain: cache size = 5 elements
- [x] lru cache algo
- [ ] after lru algo, return the order of the cache with
the elements joined into a string, separated by a hyphen
*/

O problema do "LRU Cache" (Least Recently Used) envolve gerenciar uma estrutura de dados que armazena um número limitado de elementos, de forma que os itens menos utilizados recentemente sejam descartados quando necessário. A ideia é implementar um cache que armazena até um determinado número de itens e, quando o cache está cheio, descartar o item menos utilizado recentemente para liberar espaço para um novo.

Explicação do Algoritmo "LRU Cache"

1. Definição do Tamanho do Cache (CACHE_SIZE):

   • A constante CACHE_SIZE é definida como 5, indicando que o cache pode armazenar até 5 elementos. Este valor representa a capacidade máxima do cache.

2. Inicialização do cacheMap:

   • Um Map é criado para armazenar os elementos do cache. O Map é utilizado porque permite armazenar pares de chave-valor e mantém a ordem de inserção dos elementos, o que é importante para este algoritmo.

3. Iteração sobre strArr:

   • Para cada elemento char em strArr:
     • Verificação se o Elemento já está no Cache:
       • Se o elemento já estiver no cache (cacheMap.has(char)), significa que ele foi utilizado recentemente. Então, ele é removido (cacheMap.delete(char)) e reinserido no final (última posição), para indicar que foi o mais recentemente usado.
     • Verificação se o Cache está Cheio:
       • Se o cache já estiver cheio (cacheMap.size === CACHE_SIZE), o elemento menos recentemente utilizado (o primeiro elemento do Map) é removido. O método cacheMap.keys().next().value retorna a chave do primeiro elemento, que é então removido com cacheMap.delete(...).
     • Inserção do Novo Elemento no Cache:
       • O elemento atual char é inserido no cache (cacheMap.set(char, true)). Como resultado, ele se torna o mais recentemente utilizado.

4. Retorno dos Elementos do Cache:

   • Ao final da iteração, o algoritmo retorna as chaves presentes no cacheMap, unidas por um hífen (-). As chaves são convertidas para uma matriz e, em seguida, unidas (join) em uma string no formato desejado.

Funcionamento do LRU Cache

• O Map é utilizado porque mantém a ordem de inserção dos elementos, e a remoção e re-inserção de elementos atualiza essa ordem.
• Quando o cache está cheio e um novo elemento precisa ser adicionado, o algoritmo remove o primeiro elemento inserido, que é o menos recentemente utilizado.
• O algoritmo garante que o cache sempre contenha os elementos mais recentemente utilizados até o tamanho máximo especificado.

Complexidade do Algoritmo

• Tempo: As operações de inserção, exclusão e acesso no Map têm complexidade média de O(1), tornando o algoritmo eficiente para gerenciar o cache.
• Espaço: O espaço utilizado é proporcional ao tamanho máximo do cache, neste caso CACHE_SIZE, que é constante.