A pergunta errada de entrevista sobre busca binária de Steve Ballmer

A pergunta errada de entrevista sobre busca binária de Steve Ballmer

• Steve Ballmer fazia perguntas-enigma a candidatos em entrevistas da Microsoft. Essa pergunta se baseava em busca binária e valor esperado.
• Ballmer propunha o seguinte jogo: "Estou pensando em um número entre 1 e 100. Se você acertar, eu te pago; se errar, você me paga".
• Ballmer afirmava que esse jogo não deveria ser aceito. Havia dois motivos: primeiro, porque ele poderia escolher o número mais difícil; segundo, porque, se o número fosse escolhido aleatoriamente, o valor esperado seria negativo.

Estratégia de busca binária

• Seguindo a estratégia de busca binária, Ballmer teria de pagar $1 ao escolher um número específico.
• Por exemplo, se Ballmer escolhesse 59, seria possível encontrá-lo em 5 etapas com a estratégia de busca binária. Emily Chang quase acertou de fato.

Cálculo do valor esperado

• Se Ballmer escolher o número aleatoriamente, o valor esperado é de $0.20.
• Com um exemplo de código, é possível calcular o número de tentativas para cada valor e o valor esperado total.
• O valor esperado é calculado como 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100.

O erro de Ballmer

• É possível que Ballmer não tenha incluído o caso de adivinhar $0 em 6 tentativas.
• Se Ballmer disse "Estou pensando em um número entre 1 e 100. Se você acertar, eu te pago; se errar, você me paga", então o valor esperado seria de -$0.49.

Comentários

• Damian Cugley: Fico me perguntando se algum outro algoritmo de adivinhação poderia ser melhor.
• royalroad: O que Ballmer descreveu é um jogo de informação incompleta, e para calcular o valor esperado ótimo seria preciso encontrar o equilíbrio de Nash.
• espadrine: É possível que Ballmer tenha insinuado que poderia mudar o número secreto.

Resumo do GN⁺

• Este texto oferece um caso interessante sobre o algoritmo de busca binária e o cálculo de valor esperado.
• A proposta de jogo de Ballmer mostra como calcular o valor esperado por meio de análise matemática.
• Pode ajudar a entender e aplicar o algoritmo de busca binária.
• Outros projetos com funcionalidades semelhantes incluem "HackerRank" e "LeetCode".

[GN⁺]

Comentários do Hacker News

• Experiência em entrevistas para cargos sênior em um domínio complexo (pagamentos)

  • Concluiu com sucesso entrevistas com base em mais de 10 anos de experiência na área de pagamentos
  • Em cargos sênior, habilidades de comunicação interpessoal e gestão de conflitos são mais importantes do que conhecimento especializado do tema
  • Na rodada final, recebeu uma recomendação negativa por não ter experiência suficiente com pagamentos em tempo real
  • Percebeu que não quer trabalhar em um grande banco americano

• Discussão sobre a escolha de números de Ballmer

  • O entrevistado assume que Ballmer escolhe números aleatoriamente
  • Se assumir que Ballmer escolhe números de forma hostil, pode escolher um valor inicial diferente para o primeiro palpite
  • Há interesse em analisar algoritmos que usam um deslocamento aleatório para evitar ataques adversariais mantendo as vantagens da busca binária

• Utilidade da busca binária como ferramenta para resolver problemas

  • Percebeu que a busca binária é útil para resolver problemas em sistemas complexos
  • Compartilhou um caso em que resolveu um problema na ferramenta de renderização do Figma por meio de busca binária
  • Resolveu o problema removendo elementos e verificando o impacto

• Compartilhamento de script em Python

  • Foi fornecido um script em Python que simula um jogo de adivinhação de números
  • O script usa busca binária para adivinhar o número-alvo e calcular o pagamento médio

• Erro de atribuir o sucesso à própria inteligência

  • Pergunta sobre o erro de atribuir o próprio sucesso à inteligência e assumir que está sempre certo
  • Comparado à síndrome do impostor no sentido oposto

• Pergunta sobre se o jogo é justo

  • Pergunta sobre se haveria jogo limpo na entrevista e como isso poderia ser verificado

• Curiosidade sobre a solução de equilíbrio de Nash

  • Curiosidade sobre o caso em que quem adivinha retorna números aleatórios próximos da busca binária
  • Dúvida sobre se quem escolhe usa uma distribuição inicial uniforme ou não uniforme

• Ballmer evitando a questão

  • Esforço de Ballmer para evitar a pergunta ao ver que Chang não estava pensando explicitamente em busca binária e valor esperado
  • Discussão sobre por que entrevistadores técnicos gostam dessa pergunta

• Objetivo da pergunta de entrevista

  • Espera-se que a pergunta de entrevista mostre o processo de resolução de problemas
  • Se encontrar um erro na pergunta, isso pode até render uma avaliação positiva

• Procurando um programador e acabando por contratar um matemático

  • Menção à situação em que, ao procurar um programador, acaba-se contratando um matemático