Mi pregunta favorita de entrevista de ingeniería de software: calcular la mediana

• Los pequeños problemas de implementación en entrevistas técnicas pueden ser más efectivos que los acertijos, y calcular la mediana deja ver tanto habilidades básicas de programación como criterio de diseño
• Como es un problema que requiere ordenamiento, lleva naturalmente a discutir la API: si la función debe ordenar por sí misma, si quien la llama debe pasar los datos ordenados y si se puede modificar el arreglo original
• La bifurcación entre longitudes pares e impares, el cálculo de índices y los errores de off-by-one son buenos para observar el proceso de depuración del candidato
• En un problema corto también se puede verificar la diferencia entre mediana y promedio, la facilidad para escribir pruebas e incluso el conocimiento de la biblioteca estándar statistics de Python
• La implementación de ejemplo lanza ValueError con una lista vacía, ordena una copia con sorted() y luego devuelve el promedio de los dos valores centrales si la longitud es par, o el valor central si es impar

---

Por qué el problema de la mediana es adecuado para una entrevista

• Una buena pregunta de entrevista técnica no debe ser un problema rebuscado tipo acertijo, sino permitir sacar temas más profundos a partir de una implementación intuitiva
• La pregunta “escribe una función que reciba un arreglo de números y devuelva la mediana” sirve bien como una señal tipo Fizz Buzz para comprobar si el candidato realmente sabe programar
• Reducir los valores de un arreglo a un solo resultado es una habilidad básica, y además el problema es lo bastante pequeño como para ver fácilmente la conversación y la depuración

Puntos de decisión que aparecen durante la implementación

• Para calcular la mediana, primero hace falta ordenar
  • Hay que decidir si la función ordena por sí misma o si quien la llama debe pasar un arreglo ya ordenado
  • Cuando el arreglo se pasa por referencia, también entra en el contrato de la API si se permite modificar el original
  • Estas decisiones también conectan con discusiones de rendimiento
• El cálculo de índices tiene trampas de off-by-one
  • Más que el error en sí, se puede observar cómo depura un problema pequeño
• La forma de devolver el resultado cambia según la longitud del arreglo
  • Si la longitud es par, devuelve el promedio de los dos valores centrales
  • Si la longitud es impar, devuelve el valor central

Una conversación que se amplía a partir de un problema corto

• La mediana puede llevar a una discusión estadística, por ejemplo sobre por qué en muchos casos puede ser una mejor opción que el promedio
• Como las entradas y los valores esperados son simples, es fácil de probar y permite que el candidato muestre criterio para escribir tests
• En Python, también es una oportunidad para mostrar conocimiento de la biblioteca estándar statistics

Decisiones en la implementación de ejemplo en Python

• Una lista vacía provoca ValueError("median called with empty list")
• Se usa sorted(numbers) para no ordenar directamente la lista de entrada, a diferencia de numbers.sort()
• La longitud se obtiene con len(numbers) y el índice central se calcula como mid = length // 2
• Si la longitud es par, devuelve (numbers[mid - 1] + numbers[mid]) / 2.0; si es impar, devuelve numbers[mid]

[GN⁺]

Opiniones en Lobste.rs

• No se entiende muy bien este artículo. Parece que el autor no sabe que la mediana puede calcularse en O(n). Referencia: https://rcoh.me/posts/linear-time-median-finding/
  Así que eso de que “los números tienen que estar ordenados desde el principio” es incorrecto. Por eso tampoco me parece una buena pregunta de entrevista. La solución óptima usa un algoritmo complejo; salvo que alguien se lo sepa de memoria, es difícil esperar que lo saque en el momento, y saberlo de memoria tampoco ayuda mucho para evaluar al candidato.
  En todo caso, podrías pedirle al candidato que proponga una solución ingenua: ordenar el arreglo con una función de biblioteca y devolver el valor del medio

  • Casi me enojo porque recuerdo que propuse una solución de n*log(n) y me filtraron en una entrevista telefónica por eso
    Después aprendí quickselect en una clase de algoritmos, y pensé: “No pueden haber esperado en serio que se me ocurriera eso en el momento”. Bueno, quizá simplemente no encajaba con ese puesto
  • Soy el autor. Si un candidato menciona quickselect, me parecería bastante impresionante. Aun así, no creo que sea una mala pregunta. Incluso con algoritmos intuitivos hay bastante de qué hablar
    Sobre eso de esperar “la solución ingenua de ordenar el arreglo con una función de biblioteca y devolver el valor del medio”, no esperaría que el candidato escriba algo mejor que la biblioteca estándar de Python

• Como bono, te permite ver de inmediato si alguien ha estudiado algoritmos o al menos si se preparó para entrevistas. Va a proponer usar quickselect: https://en.wikipedia.org/wiki/Quickselect

  • Me sorprendió que no lo mencionaran. Si me hicieran esta pregunta y estuviera usando C++, probablemente usaría nth_element
    Y si tuviera que escribir quickselect desde cero, también podría hacerlo. Básicamente se parece a partición + búsqueda binaria
  • En realidad no lo veo así. Esta pregunta parece más una prueba básica de “¿de verdad puedes programar?”, o sea, “¿la persona que hizo el filtro previo hizo bien su trabajo?”. Aunque pudiera recitar quickselect de memoria, creo que no lo haría perfecto y elegiría la solución ingenua para no hacer perder tiempo al entrevistador
  • El caso en que el arreglo tiene longitud par es interesante. Puedes ejecutar quickselect normal dos veces para los dos índices centrales, o ajustar quickselect para esa tarea. Puede que al final sea prácticamente lo mismo
  • Me confundió el requisito de que la lista tuviera que estar ordenada. Intuitivamente tampoco es necesario
  • Esa fue la respuesta que me dio un LLM, y hasta incluía una variante inmutable opcional por si uno la quería elegir

• El tipo int de Python no tiene overflow, pero si usas C, C++ o Go, ¿no habría que preocuparse también por el overflow en la suma en la rama del arreglo de longitud par?

  • Esa suma ocurre en float, no en int. Aun así, podría desbordarse a inf. Si los dos elementos del arreglo son sys.float_info.max, la respuesta también debería ser sys.float_info.max, pero el resultado de la suma sería inf, y al dividirlo entre 2 seguiría siendo inf
    Podrías intentar arreglarlo distribuyendo la división entre 2 sobre la suma, pero entonces daría una respuesta incorrecta con números subnormales. La mayoría simplemente asume que en sus programas no van a aparecer números tan grandes como para causar este problema. Incluso numpy aquí devuelve inf con una advertencia:

    >>> 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)  
    

• En la práctica, también hay varias formas de elegir la mediana en sí. Puedes optar por interpolación lineal, por el límite superior o por el límite inferior
  Y si te pasas a los cuantiles, podrías hablar durante horas. Elegir uno solo y elegir varios a la vez requiere enfoques distintos

• Yo no uso preguntas de entrevista como la del artículo original. Yo exijo suavidad, es decir, que la dificultad del problema tenga que variar de forma fluida según la habilidad y la experiencia del candidato. En especial, si saber que existen funciones de biblioteca o algoritmos como quickselect o radix sort cambia el resultado de forma brusca, entonces no es una buena pregunta para medir nada
  Terminas no midiendo la experiencia y capacidad del candidato, sino si conoce cierto artefacto mágico específico. Se puede compensar con preguntas de seguimiento, pero es mejor plantear desde el inicio un problema más suave

  • Si puedes compartirlo, me daría mucha curiosidad ver ejemplos concretos de ese tipo de problema suave