La entrevista técnica se desmorona (2022)

 (xeiaso.net)
1 puntos por GN⁺ 2023-07-09 | 1 comentarios | Compartir por WhatsApp
  • Palima Aethera parecía la candidata capaz de rescatar la infraestructura caótica de Techaro, pero volteó por completo el ambiente de la entrevista al proponer adrede una extraña solución de ordenamiento en una prueba de código en vivo
  • El entrevistador Jeff, tras confirmar la pronunciación de su nombre y si ese era realmente su rostro, mostró gran interés por la experiencia de Palima con la infraestructura de MovieFlix y por el caso en que eligió FreeBSD
  • En el ejercicio de ordenar un arreglo de números, Palima implementó en Haskell sleepsort, creando un hilo por cada valor, durmiendo en proporción al valor y luego imprimiéndolo
  • Palima insistió en llamar a esa solución un “ordenamiento en tiempo constante” y explicó que había logrado una optimización de 10x al reducir el tiempo de espera de múltiplos de 100000 a 10000 microsegundos, haciendo reír a Jeff
  • Después de la entrevista, Palima esperaba ser rechazada, pero Techaro le envió una oferta de contratación por una suma considerable, y ella decidió irse a dormir diciendo que el trabajo se ordenaría solo

El día de la entrevista, iniciado en un sueño

  • En un sueño, Palima ve que su amuleto de despertar había desaparecido de su muñeca y se da cuenta de que está soñando
  • Tras despertar por la vibración de su reloj de pulsera, recuerda que ese día tiene un compromiso importante
  • El trayecto al trabajo termina en 30 segundos, y Palima se sienta en una silla modificada para acomodar su cola y aleta dorsal
  • La estación de trabajo avisa que Firefox está desactualizado, y un script compila y ejecuta una versión nueva

Comienza la entrevista de Techaro

  • La videollamada se realiza mediante un servicio de la serie E100, y Palima enciende la iluminación de la cámara
  • El primer entrevistador, Jeff, pronuncia mal el nombre de Palima y lo corrige de inmediato
    • Palima explica que se pronuncia Pa-lee-mah y Aethera como Ay-theer-ah
    • Jeff dice que lo anotará para que otras personas también la llamen correctamente
  • Cuando Jeff pregunta si usa un avatar virtual, Palima responde: “este es mi rostro real”
  • Palima deduce, con solo ver la descripción del puesto, que la infraestructura de Techaro está en caos y necesita una heroína

Presentación profesional y experiencia en infraestructura

  • Palima se presenta diciendo que ha pasado mucho tiempo creando dispositivos automáticos digitales y enviándolos al mundo para que cumplan objetivos
  • En MovieFlix contribuyó a construir la infraestructura de streaming simultáneo de películas y programas de TV populares
  • Añade que también ha trabajado en muchos proyectos que no puede revelar, y que Jeff actualmente se beneficia de al menos tres de ellos
  • Explica que quiere unirse a una empresa pequeña porque desea conocer a la gente de una manera más personal, y que el atractivo de trabajar como una pieza anónima dentro de una máquina no dura para siempre
  • Menciona como su proyecto de infraestructura favorito el benchmarking del kernel del sistema operativo para el backend de MovieFlix
    • Palima esperaba que ganara Linux, pero después de epoll(7), FreeBSD funcionó más rápido, así que eligió FreeBSD
    • Añade que probablemente todavía tenga permisos de commit en FreeBSD

Código en vivo: sleepsort

  • Jeff explica que el perfil de Palima parece encajar con lo que Techaro busca, pero que deben hacer un desafío de programación para evaluar a todas las personas con el mismo criterio
  • La tarea consiste en ordenar un arreglo de números en un sitio web y explicar el método de ordenamiento
  • El lenguaje era libre, y Palima escribió código en Haskell
  • La implementación crea un green thread independiente para cada número y, tras threadDelay (100000 * time), escribe el valor en un canal para imprimirlo
  • Palima dice que este ordenamiento no usa comparaciones y que “a veces solo hace falta un poco de descanso”
  • Cuando Jeff pregunta si el tiempo no varía según los valores de entrada, Palima responde que la complejidad temporal no se preocupa por efectos secundarios como el tiempo

Optimización y un resultado inesperado

  • Cuando Jeff pregunta cómo optimizarlo, Palima solo cambia el multiplicador del retraso
    • Reduce 100000 * time a 10000 * time
    • Palima explica que ahora es 10 veces más rápido
  • Jeff termina soltando una gran carcajada, y cuando Palima le pregunta por qué usó un algoritmo de ordenamiento tan extraño, ella le devuelve la pregunta: “¿por qué hiciste una pregunta tan extraña?”
  • Palima concluye que Techaro no es lo suficientemente compleja como para contenerla y que, en lugar de Kubernetes, probablemente les habría bastado con un solo servidor dedicado de Typhoon Digital
  • Tras terminar la entrevista, espera que pronto llegue un correo de rechazo
  • Sin embargo, Techaro le envía un correo diciendo que quiere contratarla por una suma considerable, y Palima se pregunta si realmente saben lo que están dispuestos a asumir
  • Palima decide volver a dormirse, diciendo que para la noche el trabajo ya se habrá ordenado solo

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-09
Comentarios de Hacker News

  • No es tiempo constante, ni tampoco tiempo polinomial, sino tiempo seudopolinomial. Parece que fallaría con números negativos, y para que fuera lineal respecto a la cantidad de bits usada para representar la entrada, necesitarías algo como 10000 * log(time + min(time) + 1)
    En teoría de la complejidad computacional, decir que un algoritmo numérico corre en tiempo seudopolinomial significa que su tiempo de ejecución es un polinomio del valor numérico de la entrada, es decir, del entero más grande que aparece en la entrada, no un polinomio de la longitud de la entrada (la cantidad de bits necesaria para representar ese número)
    https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time

    • Sí sabes que eso es parte del chiste, ¿no? Ya que vamos a arruinar el chiste poniéndonos detallistas, ni siquiera hace falta esperar tiempo real
      La complejidad computacional trata del número de pasos dentro del modelo de cómputo, no de cuánto tiempo pasa en el reloj. sleep sort aprovecha propiedades del scheduler del sistema operativo, y en un entorno de tiempo virtual el tiempo avanza directamente hasta el siguiente evento programado. Si asumes algo así como modelo de cómputo, en realidad sí corre con complejidad polinomial
      Y si vas a corregir a otros, por lo menos conviene escribir bien pseudo-polynomial
    • ¿No podría cualquier problema seudopolinomial volverse de tiempo polinomial con solo cambiar la codificación? Si tienes una caja que calcula algún valor en tiempo seudopolinomial, puedes hacer una caja que reciba una sola entrada formada por poner 1 repetido según la longitud de cada valor y separarlos con 0
      Volver a convertir eso en enteros es lineal, llamas a la caja original y luego devuelves el resultado, y ahora ya es tiempo polinomial respecto a la longitud de mi entrada. Dije entero, pero el punto clave es el esquema de codificación; para decimales podrías usar un solo 0, y 00 para separar entradas, por ejemplo
      De todos modos, ¿no es que el centro del chiste está en que el tiempo dormido no cuenta? La computadora puede hacer otras cosas mientras tanto. Tiene una lógica bastante convincente del tipo “es tonto, pero me gusta”

  • sleep sort empezó en /prog/ [0]. Seguro que varios lurkers de HN participaron en aquel hilo de sleep sort; quizá xena también fue una de ellas :)
    [0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...

    • Si cargo cañones con pólvora según el número actual, pongo más pólvora para los números más grandes para que vuelen más lejos, y luego voy caminando a recoger los números a lo largo de la trayectoria, ¿eso cuenta como ordenamiento físico?
    • Hace muchísimo que no pensaba en /prog/. Mi publicación favorita era una sobre un aprendiz de programador que inventó el operador <=> para usarlo cuando quieres comprobar “menor, igual o mayor”. Genialidad pura

  • Como dice el autor original, este texto se parece muchísimo al estilo narrativo de la serie Interview de aphyr, como “Rewriting the Technical Interview”. Todas se leen muy bien
    [0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...

    • El estilo es muy distinto, pero en eso de burlarse de las entrevistas técnicas también está “Fizzbuzz in Tensorflow” (2016)
      https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
      Una probadita:

      interviewer: Um, you understand the problem is fizzbuzz, right?
      me: Do I ever. So, now let's talk models. I'm thinking a simple multi-layer-perceptron with one hidden layer

  • El ordenamiento por computadora necesita leer la entrada, así que como mínimo requiere tiempo lineal. Más aún si no conoces otra información sobre la entrada, como una distribución uniforme o algo por el estilo
    Hay varios métodos de ordenamiento en tiempo lineal, como sleep sort, postman sort, counting sort, etc. Eso sí, para conjuntos limitados de números o claves ordenables
    Pero si usas un ábaco en vez de una computadora, hay un ordenamiento de tiempo constante que casi parece real: https://en.wikipedia.org/wiki/Bead_sort

    • También existen las sorting networks. Aunque claro, eso no cambia mucho el punto principal :D

  • Es una historia simpática, pero en ningún sentido es tiempo constante
    Crear N hilos y agregarlos todos a una lista de despertado ordenada toma entre O(N log N) y O(N^2), según el sistema operativo o el runtime del lenguaje
    En algún lugar detrás hay una lista ordenada, un heap o un algoritmo N^2. Del mismo modo, sleep sort tampoco deja de requerir como mínimo tiempo lineal, porque para imprimir N elementos ordenados hay que despertar N hilos
    Peor aún, el tiempo de reloj real también aumenta según la magnitud de los valores. Primero puedes encontrar el mínimo y el máximo para comprimir el rango, pero eso también es tiempo lineal

    • A riesgo de arruinar el chiste, cuando dije “tiempo constante” estaba aludiendo al lenguaje y la forma del análisis de complejidad temporal, pero no lo dije literalmente en ese sentido
      Aquí es un juego de palabras que explota dos concepciones en conflicto de la palabra “tiempo”. Desde la perspectiva del análisis de complejidad, es cierto que no se puede hacer un algoritmo de ordenamiento en tiempo constante
      La intención real del chiste era el tiempo de reloj. En una entrevista ese tiempo es más relevante y, en la práctica, cuando alguien te lanza algo como “escribe una función para ordenar enteros”, rara vez usan números menores que 100, así que este programa se siente como si corriera casi de inmediato
      Es un chiste metalingüístico sutil que se burla de darle la vuelta a la comprensión de cómo funciona la informática. Lástima que no pegó
    • En un universo con vida útil finita, todo es tiempo constante
      https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
    • En teoría, el argumento que entra a sleep al final tendría que reducirse a un entero, así que algo como radix sort también podría hacerse en tiempo lineal
      Hay espacios de problemas donde sigue siendo una ventaja, incluso con la dependencia del tamaño del valor más grande
      Claro, en la práctica no existe un sistema así. Los timeouts de system calls normalmente no son un lugar donde ese enfoque resulte ventajoso. Y por supuesto, sería mejor aplicar radix sort directamente, que usar un método que crece linealmente con el máximo en vez de solo con log(max_value)
    • Que crear N hilos y agregarlos a una lista de despertado ordenada cueste O(N log N) a O(N^2) no es una limitación fundamental de los sistemas de scheduling
      Sobre todo si consideras hardware especializado que permita scheduling en tiempo constante con respecto al número de hilos. Por ejemplo, aunque en la realidad no tendría ningún sentido económico, podrías construir un scheduler que rebote paquetes de información con un láser sobre un enorme conjunto de espejos a distintas distancias y los haga volver a un detector conectado a la computadora
      La idea es usar la velocidad de la luz para introducir el retraso exacto. Así que sleep sort no depende esencialmente de la complejidad algorítmica oculta de alguna forma de scheduling de hilos; aunque no sea práctico, en teoría podría optimizarse a O(1)
    • Esto se parece al estilo de montar un clúster de Kubernetes para devolver “Hello World”

  • Si te gusta esto, también hay una especie de secuela llamada Protos: https://xeiaso.net/blog/protos
    Sigue escribiendo historias dentro de este “universo”, pero le toma un poco de tiempo agarrar impulso satírico. Tal vez la próxima entrega sea sobre computación espacial

    • La parte de “justo a tiempo para que suene la alerta del calendario de que la standup está por empezar” se parece a nuestro universo
      Aun así, parece que en ese universo sí saben poner mejores nombres

  • La parte de cambiar threadDelay (100000 * time) por threadDelay (10000 * time) y decir “ahora es diez veces más rápido” se relaciona con este artículo: https://thedailywtf.com/articles/The-Speedup-Loop

  • No leí el artículo, pero odio este tipo de cosas. Una vez tuve una entrevista remota con Meta y la otra persona se la pasó comiendo frente al micrófono
    Fue tan distractor que hasta se me olvidó cómo escribir un bucle for

    • La contratación remota es mucho mejor. Antes hablabas brevemente con un reclutador o con RR. HH., luego tenías que ponerte traje y manejar lejos o tomar un vuelo, y normalmente se te iba el día completo
      Si ya estabas trabajando, tenías que pedir vacaciones, y además venía el estrés de “¿de verdad voy a desperdiciar mis vacaciones limitadas en esto?”, “¿habrá estacionamiento?”, “¿llegaré a tiempo?” Luego hacías una “entrevista inicial” de 30 minutos, esperabas semanas, y después o te invitaban a una entrevista de verdad o simplemente te ghosteaban
      Todo el proceso podía tomar un mes y requerir al menos dos días de vacaciones y bastante traslado
      Ahora el reclutador o RR. HH. te llama, te pregunta si puedes hacer una videollamada, hablan 15 o 20 minutos ese mismo día, luego pasan tu CV al responsable de decidir, y te agendan una o más entrevistas por video o sesiones técnicas. Algunas empresas incluso te piden hacer pruebas de personalidad o técnicas desde la comodidad de tu casa
      Si trabajas en remoto, podrías hacer todo eso a la hora del almuerzo. La comunicación cara a cara sí tiene mucho más ancho de banda, pero solo con remoto puedes entrevistar en la mañana con una empresa de Tel Aviv, al mediodía con una de Warsaw y en la noche con una de California

  • ¿Crear 1000 hilos no es al menos tiempo lineal? Tal vez se pueda bajar hasta logarítmico, pero no parece que ese código lo haga automáticamente

    • Depende de qué entiendas por “tiempo”. Si hablas del tiempo de complejidad algorítmica, sí, como mínimo es lineal. Si hablas del tiempo de reloj, o sea el que más importa en código de entrevista, entonces es constante
    • No se puede decir que sleep sort sea más de tiempo constante que otros algoritmos de ordenamiento
      Para que sleep sort sea tiempo constante tendría que haber un límite superior para la entrada, es decir, una cota sobre el número más grande, y además habría que ignorar tareas arbitrarias como leer y procesar la entrada o crear hilos
      Pero si permites eso, entonces todos los demás ordenamientos también se vuelven de tiempo constante. De hecho, parecería que basta con permitir cualquiera de las dos cosas
    • En realidad ni siquiera es lineal. Dormir implica una inserción en heap y eso cuesta O(log n)
    • En realidad sí se estaba durmiendo durante la entrevista. De otro modo no se explicaría afirmar que la complejidad asintótica es “tiempo constante” cuando la primera línea del programa hace un bucle secuencial sobre todos los valores de entrada

  • Si el runtime de hilos mantiene su propia noción del tiempo, el algoritmo ni siquiera necesita dormir en tiempo real
    Después de crear todos los hilos, el runtime puede notar que todos están inactivos y que el siguiente hilo a programar es el del tiempo N, así que basta con actualizar el tiempo actual a N y ejecutar ese hilo. Si se repite esto, se obtiene un arreglo ordenado sin ningún sleep
    En última instancia, la tarea de ordenamiento ya terminó en el momento en que los hilos empezaron a dormirse, y luego quedaron registrados con algún coordinador que los despertará más tarde, por ejemplo una rueda de temporizador. No hace falta realizar un sueño real
    No sé de Haskell, pero el runtime tokio de Rust permite hacer esto con start_paused: https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...

    • Entiendo que así es básicamente como funciona internamente una simulación de eventos discretos. Con una estructura de datos adecuada, por ejemplo un heap con los límites de los eventos futuros, se va alternando entre agregar eventos futuros al heap y sacar del heap el siguiente evento
      Dejando de lado varias capas de abstracción y detalles de implementación omitidos, ordenar valores con un planificador así es simplemente heap sort :)
    • Si de verdad empiezas a calcular qué ejecutar después, estás reinventando el selection sort, y ya no es tiempo lineal. Así que, en la práctica, no es un algoritmo de ordenamiento con sentido :)