Minha pergunta favorita de entrevista de engenharia de software: cálculo da mediana

• Pequenos problemas de implementação em entrevistas técnicas podem ser mais eficazes do que quebra-cabeças, e o cálculo da mediana revela tanto a habilidade básica de programação quanto o senso de design
• Como é um problema que exige ordenação, ele leva naturalmente a uma discussão de API: se a função deve ordenar diretamente, se quem chama deve ordenar, e se é permitido modificar o array original
• A ramificação entre tamanhos ímpares e pares, o cálculo de índices e erros de off-by-one são bons para observar o processo de depuração do candidato
• Em um problema curto, dá para verificar a diferença entre mediana e média, a facilidade de escrever testes e até o conhecimento da biblioteca padrão statistics do Python
• A implementação de exemplo lança ValueError para uma lista vazia, faz uma ordenação por cópia com sorted() e retorna, para tamanho par, a média dos dois valores centrais; para tamanho ímpar, o valor central

---

Por que o problema da mediana é adequado para entrevistas

• Uma boa pergunta de entrevista técnica não deve ser um problema retorcido como um quebra-cabeça; ela deve permitir trazer temas mais profundos a partir de uma implementação intuitiva
• A pergunta “escreva uma função que receba um array de números e retorne a mediana” funciona bem como um sinal no estilo Fizz Buzz para verificar se o candidato realmente sabe programar
• Reduzir os valores de um array a um único resultado é uma competência básica, e o problema em si é pequeno o suficiente para facilitar a conversa e a depuração em conjunto

Pontos de decisão que aparecem durante a implementação

• Para calcular a mediana, primeiro é necessário ordenar
  • É preciso decidir se a função vai ordenar diretamente ou se quem chama deve passar um array já ordenado
  • Quando o array é passado por referência, permitir ou não alterar o original também faz parte do contrato da API
  • Essas escolhas também se conectam a discussões de desempenho
• O cálculo de índices tem armadilhas de off-by-one
  • Mais do que observar se há erro, é possível ver como a pessoa depura um problema pequeno
• A forma de retorno muda conforme o tamanho do array
  • Para tamanho par, retorna-se a média dos dois valores centrais
  • Para tamanho ímpar, retorna-se o valor central

Conversas que se expandem a partir de um problema curto

• A mediana pode levar a uma discussão estatística, por exemplo sobre por que ela pode ser uma escolha melhor do que a média na maioria dos casos
• Como as entradas e os valores esperados são simples, é fácil testar, e o candidato pode mostrar seu senso de testes
• Em Python, também há a oportunidade de demonstrar conhecimento da biblioteca padrão statistics

Escolhas da implementação Python de exemplo

• Uma lista vazia gera ValueError("median called with empty list")
• Usa sorted(numbers) para não ordenar diretamente a lista de entrada, diferentemente de numbers.sort()
• O tamanho é obtido com len(numbers), e o índice central é calculado com mid = length // 2
• Para tamanho par, retorna (numbers[mid - 1] + numbers[mid]) / 2.0; para tamanho ímpar, retorna numbers[mid]

[GN⁺]

Comentários no Lobste.rs

• Não entendi muito bem este texto. Parece que o autor não sabe que a mediana pode ser calculada em O(n). Referência: https://rcoh.me/posts/linear-time-median-finding/
  Portanto, a afirmação de que “os números precisam estar ordenados desde o início” está errada. Por esse motivo, também não acho que seja uma boa pergunta de entrevista. A solução ótima é um algoritmo complexo; é difícil esperar que alguém chegue a ela na hora, a menos que já a conheça de memória, e saber se o candidato a decorou também não ajuda muito na avaliação.
  No máximo, daria para pedir ao candidato uma solução ingênua: ordenar o array com uma função de biblioteca e retornar o valor do meio

  • Quase fiquei irritado, porque lembro de ter sido eliminado em uma entrevista por telefone depois de apresentar uma solução n*log(n) para esse problema
    Mais tarde, em uma aula de algoritmos, aprendi quickselect e pensei: “não é possível que esperassem que eu pensasse nisso na hora”. Bem, talvez eu simplesmente não fosse adequado para aquela vaga
  • Sou o autor. Se um candidato mencionar quickselect, eu ficaria bem impressionado. Mesmo assim, não acho que seja uma pergunta ruim. Há bastante assunto para discutir só com algoritmos intuitivos
    Sobre a ideia de esperar “uma solução ingênua que ordena o array com uma função de biblioteca e retorna o valor do meio”, eu não esperaria de um candidato um código melhor que o da biblioteca padrão do Python

• Como bônus, dá para saber na hora se alguém estudou algoritmos, ou pelo menos se se preparou para a entrevista. A pessoa vai sugerir usar quickselect: https://en.wikipedia.org/wiki/Quickselect

  • Fiquei surpreso por isso não ter sido mencionado. Se eu recebesse essa pergunta usando C++, acho que usaria nth_element
    E, se eu tivesse que escrever quickselect do zero, também conseguiria. Basicamente, é algo próximo de particionamento + busca binária
  • Na prática, não acho que seja assim. Essa pergunta parece ser um teste básico de “a pessoa realmente sabe programar?”, ou seja, “o screener fez o trabalho dele direito?”. Mesmo que eu conseguisse recitar quickselect de cabeça, acho que não faria isso perfeitamente, e escolheria a solução ingênua para não desperdiçar o tempo do entrevistador
  • O caso em que o tamanho do array é par é interessante. Dá para rodar o quickselect comum duas vezes para os dois índices centrais, ou ajustar o quickselect para essa tarefa. As duas abordagens podem acabar sendo praticamente a mesma coisa
  • Fiquei confuso porque havia o requisito de que a lista precisava estar ordenada. Intuitivamente, isso também não é necessário
  • Foi essa a resposta que recebi de um LLM, e ainda vinha com uma variante imutável que eu poderia escolher se quisesse

• O tipo int do Python não tem overflow, mas, se você estiver usando C, C++ ou Go, não teria que se preocupar também com overflow na soma no ramo de arrays de tamanho par?

  • Essa soma acontece em float, não em int. Ainda assim, existe a possibilidade de virar inf por overflow. Se os dois elementos do array forem sys.float_info.max, a resposta deveria ser sys.float_info.max, mas o resultado da soma vira inf, e dividir isso por 2 continua dando inf
    Você poderia tentar corrigir distribuindo a divisão por 2 sobre a soma, mas aí obteria respostas erradas com números subnormais. Parece que a maioria das pessoas assume que números grandes o suficiente para causar esse problema não aparecem no programa. O numpy também retorna inf aqui, com um aviso:

    >>> import sys  
    >>> import numpy  
    >>> numpy.median([sys.float_info.max, sys.float_info.max])  
    .../venv/lib64/python3.11/site-packages/numpy/_core/_methods.py:132: RuntimeWarning: overflow encountered in reduce  
      ret = umr_sum(arr, axis, dtype, out, keepdims, where=where)  
    np.float64(inf)  
    

• Na verdade, há várias formas de escolher a própria mediana. Há escolhas como usar interpolação linear, usar o limite superior ou usar o limite inferior
  E, quando se passa para quantis, dá para conversar por horas. Escolher um único valor e escolher vários de uma vez exigem abordagens diferentes

• Eu não uso perguntas de entrevista como a do texto original. Eu exijo suavidade, no sentido de que a dificuldade de resolver o problema deve variar de forma contínua conforme a capacidade e a experiência do candidato. Em especial, se saber da existência de uma função de biblioteca ou de algoritmos como quickselect ou radix sort muda drasticamente o resultado, não é um bom problema de avaliação
  Acaba testando se a pessoa conhece um artefato mágico específico, em vez de medir a experiência e a capacidade do candidato. Dá para compensar com perguntas de acompanhamento, mas é melhor propor desde o início um problema mais suave

  • Se puder compartilhar, eu ficaria muito curioso para ver exemplos concretos desse tipo de problema suave