Cache LRU

Solução 1 - Array mantendo a ordem de uso

Boa versão inicial porque deixa claro o gargalo das operações lineares.

export function runLRUCache(operations, values) {
  let capacity = 0
  const entries = []
  const output = []

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const args = values[index]

    if (operation === "LRUCache") {
      capacity = args[0]
      output.push(null)
      continue
    }

    if (operation === "get") {
      const key = args[0]
      const foundIndex = entries.findIndex(([entryKey]) => entryKey === key)

      if (foundIndex === -1) {
        output.push(-1)
        continue
      }

      const [entry] = entries.splice(foundIndex, 1)
      entries.push(entry)
      output.push(entry[1])
      continue
    }

    const [key, value] = args
    const foundIndex = entries.findIndex(([entryKey]) => entryKey === key)

    if (foundIndex !== -1) {
      entries.splice(foundIndex, 1)
    } else if (entries.length === capacity) {
      entries.shift()
    }

    entries.push([key, value])
    output.push(null)
  }

  return output
}

Funciona, mas não atende o O(1) pedido.

Solução 2 - Hash map + lista duplamente ligada

Agora cada estrutura faz a parte em que ela e boa.

export function runLRUCache(operations, values) {
  let capacity = 0
  const nodes = new Map<number, any>()
  const output = []

  const head = { key: 0, value: 0, prev: null, next: null }
  const tail = { key: 0, value: 0, prev: null, next: null }
  head.next = tail
  tail.prev = head

  function remove(node) {
    node.prev.next = node.next
    node.next.prev = node.prev
  }

  function append(node) {
    node.prev = tail.prev
    node.next = tail
    tail.prev.next = node
    tail.prev = node
  }

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const args = values[index]

    if (operation === "LRUCache") {
      capacity = args[0]
      output.push(null)
      continue
    }

    if (operation === "get") {
      const key = args[0]
      const node = nodes.get(key)

      if (!node) {
        output.push(-1)
        continue
      }

      remove(node)
      append(node)
      output.push(node.value)
      continue
    }

    const [key, value] = args

    if (nodes.has(key)) {
      const existing = nodes.get(key)
      existing.value = value
      remove(existing)
      append(existing)
      output.push(null)
      continue
    }

    const node = { key, value, prev: null, next: null }
    nodes.set(key, node)
    append(node)

    if (nodes.size > capacity) {
      const leastRecent = head.next
      remove(leastRecent)
      nodes.delete(leastRecent.key)
    }

    output.push(null)
  }

  return output
}

As invariantes importantes sao:

• head.next e sempre o menos recente
• tail.prev e sempre o mais recente
• o mapa sempre aponta para o no atual de cada chave

O que dizer na entrevista

Uma explicação curta e boa seria:

O problema pede busca por chave em O(1) e também atualizar a ordem de recencia em O(1). Só um array não fecha isso. Entao eu separo responsabilidades: hash map para achar o no da chave e lista duplamente ligada para remover, anexar no fim e expulsar o menos recente sem percorrer nada.

Isso mostra que você:

• entende por que a versão inicial falha
• justifica a composição de estruturas
• fala em invariantes em vez de só descrever ponteiros

Quando esse padrão aparece de novo

Esse padrão reaparece quando você precisa:

• combinar busca rápida com ordem mutavel
• projetar cache ou fila com politica de prioridade/recencia
• pensar em invariantes de estrutura, não só em algoritmos isolados

O ponto não e decorar esse problema.

O ponto e aprender quando um problema pede composição de estruturas.