La pregunta equivocada de entrevista sobre búsqueda binaria de Steve Ballmer

La pregunta equivocada de entrevista sobre búsqueda binaria de Steve Ballmer

• Steve Ballmer hacía preguntas tipo acertijo a los candidatos en entrevistas de Microsoft. Esta pregunta se basa en la búsqueda binaria y el valor esperado.
• Ballmer proponía el juego: "Estoy pensando en un número entre 1 y 100. Si aciertas, te doy dinero; si fallas, tú recibes dinero".
• Ballmer sostenía que no se debía aceptar este juego. Dio dos razones: primero, porque él podía elegir el número más difícil; segundo, porque si se elegía al azar, el valor esperado era negativo.

Estrategia de búsqueda binaria

• Si se sigue una estrategia de búsqueda binaria, Ballmer termina pagando $1 cuando elige cierto número específico.
• Por ejemplo, si Ballmer elige 59, se puede encontrar en 5 pasos con una estrategia de búsqueda binaria. Emily Chang en realidad estuvo muy cerca de acertar.

Cálculo del valor esperado

• Si Ballmer elige un número al azar, el valor esperado es de $0.20.
• Con un ejemplo de código se puede calcular cuántos intentos requiere cada valor y el valor esperado total.
• El valor esperado se calcula como 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100.

El error de Ballmer

• Es posible que Ballmer no haya incluido el caso de adivinar $0 en 6 intentos.
• Si Ballmer hubiera dicho "Estoy pensando en un número entre 1 y 100. Si aciertas, te doy dinero; si fallas, yo recibo dinero", entonces el valor esperado sería de -$0.49.

Comentarios

• Damian Cugley: Le intriga si otro algoritmo de adivinanza podría hacerlo mejor.
• royalroad: Lo que describió Ballmer es un juego de información incompleta, y para calcular el valor esperado óptimo habría que encontrar un equilibrio de Nash.
• espadrine: Es posible que Ballmer insinuara que podía cambiar el número secreto.

Resumen de GN⁺

• Este artículo ofrece un caso interesante sobre el algoritmo de búsqueda binaria y el cálculo del valor esperado.
• La propuesta de juego de Ballmer muestra cómo calcular el valor esperado mediante análisis matemático.
• Puede ayudar a entender y aplicar el algoritmo de búsqueda binaria.
• Otros proyectos con funciones similares incluyen "HackerRank" y "LeetCode".

[GN⁺]

Opiniones de Hacker News

• Experiencia entrevistando para un puesto senior en un dominio complejo (pagos)

  • Completó con éxito la entrevista basándose en más de 10 años de experiencia en el sector de pagos
  • En los puestos senior, las habilidades de comunicación interpersonal y manejo de conflictos son más importantes que el conocimiento especializado del tema
  • En la ronda final recibió una recomendación negativa por no tener suficiente experiencia en pagos en tiempo real
  • Se dio cuenta de que no quiere trabajar en un gran banco estadounidense

• Discusión sobre la elección de números de Ballmer

  • La persona entrevistada asume que Ballmer elige números al azar
  • Si se asume que Ballmer elige números de forma hostil, se podría escoger un valor inicial distinto para adivinar
  • Hay interés en analizar algoritmos que usan un desplazamiento aleatorio para evitar ataques adversariales mientras se conservan las ventajas de la búsqueda binaria

• Utilidad de la búsqueda binaria como herramienta para resolver problemas

  • Se dio cuenta de que la búsqueda binaria es útil para resolver problemas en sistemas complejos
  • Comparte un caso en el que resolvió un problema de una herramienta de renderizado de Figma mediante búsqueda binaria
  • Resolvió el problema eliminando elementos y comprobando su impacto

• Compartiendo un script de Python

  • Se proporciona un script de Python que simula un juego de adivinar números
  • Usa búsqueda binaria para adivinar el número objetivo y calcular el pago promedio

• El error de atribuir el éxito a la propia inteligencia

  • Se plantea una pregunta sobre el error de atribuir el propio éxito a la inteligencia y asumir que uno siempre tiene la razón
  • Se compara con el síndrome del impostor, pero en sentido contrario

• Pregunta sobre si es un juego justo

  • Se plantea si en la entrevista se jugará limpio y cómo podría comprobarse eso

• Curiosidad por la solución de equilibrio de Nash

  • Hay curiosidad sobre que quien adivina devuelva un número aleatorio cercano a la búsqueda binaria
  • También se pregunta si quien elige usa una distribución inicial uniforme o no uniforme

• Ballmer evita la pregunta

  • Al ver que Chang no piensa explícitamente en la búsqueda binaria ni en el valor esperado, Ballmer intenta esquivar la pregunta
  • Se discute por qué a los entrevistadores técnicos les gusta esta pregunta

• El propósito de la pregunta de entrevista

  • Se espera que la pregunta de entrevista muestre el proceso de resolución de problemas
  • Si se detecta un error en la pregunta, eso incluso puede llevar a una evaluación positiva

• Buscando a un programador y terminando por contratar a un matemático

  • Se menciona la situación en la que, al buscar un programador, se termina contratando a un matemático