Mediana em fluxo de dados

Solução 1 - Array ordenado a cada inserção

Boa versão inicial porque deixa o objetivo da mediana bem visível.

export function runMedianFinder(operations, values) {
  const numbers = []
  const output = []

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

    if (operation === "MedianFinder") {
      output.push(null)
      continue
    }

    if (operation === "addNum") {
      numbers.push(args[0])
      numbers.sort((a, b) => a - b)
      output.push(null)
      continue
    }

    const middle = Math.floor(numbers.length / 2)

    if (numbers.length % 2 === 1) {
      output.push(numbers[middle])
    } else {
      output.push((numbers[middle - 1] + numbers[middle]) / 2)
    }
  }

  return output
}

Funciona, mas ordenar tudo de novo em cada inserção não escala bem.

Solução 2 - Dois heaps balanceados com inserção em O(log n)

Agora a estrutura mantem a resposta pronta sem reordenacao global.

class Heap {
  constructor(compare) {
    this.compare = compare
    this.data = []
  }

  peek() {
    return this.data[0] ?? null
  }

  size() {
    return this.data.length
  }

  push(value) {
    this.data.push(value)
    this.bubbleUp(this.data.length - 1)
  }

  pop() {
    if (this.data.length === 0) {
      return null
    }

    const top = this.data[0]
    const last = this.data.pop()

    if (this.data.length > 0) {
      this.data[0] = last
      this.bubbleDown(0)
    }

    return top
  }

  bubbleUp(index) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2)

      if (this.compare(this.data[index], this.data[parent]) >= 0) {
        break
      }

      ;[this.data[index], this.data[parent]] = [this.data[parent], this.data[index]]
      index = parent
    }
  }

  bubbleDown(index) {
    const length = this.data.length

    while (true) {
      let best = index
      const left = index * 2 + 1
      const right = index * 2 + 2

      if (left < length && this.compare(this.data[left], this.data[best]) < 0) {
        best = left
      }

      if (right < length && this.compare(this.data[right], this.data[best]) < 0) {
        best = right
      }

      if (best === index) {
        break
      }

      ;[this.data[index], this.data[best]] = [this.data[best], this.data[index]]
      index = best
    }
  }
}

export function runMedianFinder(operations, values) {
  const lower = new Heap((a, b) => b - a)
  const upper = new Heap((a, b) => a - b)
  const output = []

  function rebalance() {
    if (lower.size() > upper.size() + 1) {
      upper.push(lower.pop())
    } else if (upper.size() > lower.size()) {
      lower.push(upper.pop())
    }
  }

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

    if (operation === "MedianFinder") {
      output.push(null)
      continue
    }

    if (operation === "addNum") {
      const value = args[0]

      if (lower.peek() === null || value <= lower.peek()) {
        lower.push(value)
      } else {
        upper.push(value)
      }

      rebalance()
      output.push(null)
      continue
    }

    if (lower.size() === upper.size()) {
      output.push((lower.peek() + upper.peek()) / 2)
    } else {
      output.push(lower.peek())
    }
  }

  return output
}

O ponto forte aqui e pensar em metades balanceadas, não em lista global, enquanto cada inserção continua em O(log n).

O que dizer na entrevista

Uma explicação curta e boa seria:

A versão inicial ordena tudo de novo a cada inserção. A versão forte separa os numeros em duas metades: um heap máximo para a metade menor e um heap mínimo para a metade maior. Eu mantenho os dois heaps balanceados e garanto que tudo da esquerda e menor ou igual a tudo da direita. A mediana sai do topo deles, e cada inserção continua em O(log n).

Isso mostra que você:

• modelou a mediana como fronteira entre metades
• escolheu a estrutura certa para cada lado
• explicou por que rebalanceamento faz parte da regra

Quando esse padrão aparece de novo

Esse padrão reaparece quando você precisa:

• manter uma estatistica atualizada sem recomputar tudo
• dividir dados em metade de baixo e metade de cima
• usar heap quando o topo da estrutura importa mais que a ordenação completa
• desenhar estrutura que preserva invariantes apos cada operação

O ponto não e decorar essa estrutura.

O ponto e aprender a manter a resposta certa enquanto os dados continuam chegando.