Entrevista técnica fracassada (2022)

• Palima Aethera parece ser a candidata capaz de salvar a infraestrutura caótica da Techaro, mas vira o clima da entrevista ao apresentar de propósito uma solução esquisita de ordenação no live coding
• O entrevistador Jeff confirma a pronúncia do nome e se o rosto dela é real, e demonstra grande interesse na experiência de Palima com a infraestrutura da MovieFlix e no caso de escolha do FreeBSD
• Na tarefa de ordenar um array de números, Palima implementa em Haskell um sleepsort, criando uma thread para cada valor, dormindo por um tempo proporcional ao valor e depois imprimindo-o
• Palima insiste que a solução é uma “ordenação em tempo constante” e explica que fez uma otimização de 10 vezes ao reduzir a latência de um multiplicador de 100000 para 10000 microssegundos, fazendo Jeff rir
• Após a entrevista, Palima espera ser reprovada, mas a Techaro envia uma proposta de contratação por uma quantia considerável; Palima decide dormir, dizendo que as coisas vão se ordenar sozinhas

---

O dia da entrevista que começou em um sonho

• Em um sonho, Palima percebe que está sonhando ao notar que o amuleto do despertar em seu pulso desapareceu
• Depois de acordar de manhã com a vibração do relógio de pulso, lembra que tem um compromisso importante naquele dia
• O trajeto até o trabalho termina em 30 segundos, e Palima se senta em uma cadeira modificada para acomodar sua cauda e sua nadadeira dorsal
• A workstation avisa que o Firefox está desatualizado, e um script compila e executa a nova versão

O início da entrevista na Techaro

• A videoconferência acontece por um serviço da família E100, e Palima liga a iluminação da câmera
• O primeiro entrevistador, Jeff, pronuncia errado o nome de Palima, mas se corrige imediatamente
  • Palima explica que Palima se pronuncia Pa-lee-mah, e Aethera, Ay-theer-ah
  • Jeff diz que vai fazer uma anotação para que outras pessoas também possam chamá-la corretamente
• Quando Jeff pergunta se ela está usando um avatar virtual, Palima responde: “este é o meu rosto de verdade”
• Palima percebe, só pela descrição da vaga, que a infraestrutura da Techaro está caótica e precisando de um herói

Apresentação da experiência e vivência com infraestrutura

• Palima se apresenta dizendo que fez muito trabalho criando dispositivos digitais autônomos e colocando-os no mundo para cumprir objetivos
• Na MovieFlix, contribuiu para construir a infraestrutura de streaming simultâneo de filmes e programas de TV populares
• Acrescenta que há muitos projetos sobre os quais não pode falar, e que Jeff atualmente se beneficia de pelo menos três deles
• O motivo para querer entrar em uma empresa menor é desejar conhecer as pessoas de forma mais pessoal; para ela, o apelo de trabalhar como uma peça anônima dentro de uma máquina não dura para sempre
• Como projeto de infraestrutura favorito, ela cita o benchmark de kernels de sistema operacional para o backend da MovieFlix
  • Palima esperava que o Linux vencesse, mas, depois de epoll(7), o FreeBSD funcionou mais rápido, então ela escolheu o FreeBSD
  • Acrescenta que provavelmente ainda tem permissão de commit no FreeBSD

Live coding: sleepsort

• Jeff explica que o histórico de Palima parece se encaixar no perfil que a Techaro procura, mas que, para avaliar todos pelo mesmo critério, precisam fazer um desafio de programação
• A tarefa é ordenar um array de números em um site e explicar também o método de ordenação
• A linguagem é livre, e Palima escreve código em Haskell
• A implementação cria uma green thread separada para cada número e, após threadDelay (100000 * time), escreve o valor em um canal para imprimi-lo
• Palima diz que essa ordenação não usa comparações e que “às vezes, tudo de que você precisa é um pouco de descanso”
• Quando Jeff pergunta se o tempo não varia conforme os valores de entrada, Palima responde que a complexidade de tempo não se importa com efeitos colaterais como o próprio tempo

Otimização e resultado inesperado

• Quando Jeff pergunta como otimizar, Palima muda apenas o multiplicador do atraso
  • Reduz 100000 * time para 10000 * time
  • Palima explica que agora ficou 10 vezes mais rápido
• Jeff acaba rindo alto, e, quando perguntam por que Palima usou um algoritmo de ordenação tão estranho, ela rebate: “por que fizeram uma pergunta tão estranha?”
• Palima conclui que a Techaro não é complexa o bastante para comportá-la, e que, em vez de Kubernetes, um único servidor dedicado da Typhoon Digital teria sido suficiente
• Depois de encerrar a entrevista, espera que um e-mail de rejeição chegue em breve
• Mas a Techaro envia um e-mail dizendo que gostaria de contratá-la por uma quantia considerável, e Palima se pergunta se eles sabem com o que estão tentando lidar
• Palima decide voltar a dormir, dizendo que, até a noite, as coisas vão se ordenar sozinhas

[GN⁺]

Opiniões do Hacker News

• Não é tempo constante, nem tempo polinomial, é tempo pseudo-polinomial. Parece que falharia com números negativos e, para ser linear em relação ao número de bits que representa a entrada, precisaria de algo como 10000 * log(time + min(time) + 1)
  Em teoria da complexidade computacional, dizer que um algoritmo numérico roda em tempo pseudo-polinomial significa que seu tempo de execução é um polinômio no valor numérico da entrada, ou seja, no maior inteiro que aparece na entrada, não um polinômio no tamanho da entrada (o número de bits necessários para representar esse número)
  https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time

  • Você sabe que isso faz parte da piada, certo? Para entrar nos detalhes e matar a piada: nem é preciso esperar em tempo real
    Complexidade computacional trata do número de passos dentro de um modelo de computação, não de quanto tempo passa no relógio. Sleep sort explora propriedades do escalonador do sistema operacional e, em um ambiente de tempo virtual, o tempo avança diretamente para o próximo evento agendado. Se você assumir isso como modelo de computação, na prática ele roda com complexidade polinomial
    E, se for ensinar os outros, é melhor pelo menos escrever pseudo-polynomial corretamente
  • Qualquer problema pseudo-polinomial não pode virar tempo polinomial só mudando a codificação? Se existe uma caixa que calcula algum valor em tempo pseudo-polinomial, dá para criar uma caixa que recebe uma única entrada com 1s na quantidade do tamanho de cada valor, separados por 0
    Converter isso de volta para inteiros é linear; depois é só chamar a caixa original e devolver o resultado, e agora fica em tempo polinomial em relação ao tamanho da minha entrada. Falei em inteiros, mas o ponto central é o esquema de codificação; para decimais, por exemplo, daria para usar um 0 para o ponto decimal e 00 para separar entradas
    De qualquer forma, o ponto da piada não é que o tempo dormindo não conta? Afinal, o computador pode fazer outras coisas nesse intervalo. Tem uma lógica bem convincente naquele estilo “é idiota, mas eu gostei”

• sleep sort começou no /prog/ [0]. Na época, deve haver por aqui vários lurkers do HN que participaram da thread de sleep sort; talvez a xena seja uma deles :)
  [0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...

  • Se eu colocar pólvora em um canhão de acordo com o número atual — quanto maior o número, mais pólvora, para lançá-lo mais longe — e depois caminhar pegando os números pelo trajeto, isso é ordenação física?
  • Fazia muito tempo que eu não pensava no /prog/. Meu post favorito era sobre um aprendiz de programador que inventou o operador <=> para quando queria testar “menor, igual ou maior”. Genial

• Como o autor original disse, este texto é bem parecido com o estilo narrativo da série Interview do aphyr, por exemplo “Rewriting the Technical Interview”. Vale ler todos, são divertidos
  [0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...

  • O estilo é bem diferente, mas também há “Fizzbuzz in Tensorflow” (2016) como sátira de entrevistas técnicas
    https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
    Degustação:

    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

• Ordenação em computadores precisa ler a entrada, então exige pelo menos tempo linear. Mais ainda se não houver outras informações, como uma distribuição uniforme da entrada
  Existem vários tipos de ordenação em tempo linear, como sleep sort, postman sort, counting sort etc. Mas isso vale para conjuntos limitados de números ou chaves ordenáveis
  Porém, se você usar um ábaco em vez de um computador, existe uma ordenação em tempo constante quase de verdade: https://en.wikipedia.org/wiki/Bead_sort

  • Também existe algo chamado rede de ordenação. Claro que isso não muda muito o ponto original :D

• É uma história fofa, mas não é tempo constante em nenhum sentido.
  Criar N threads e adicioná-las todas a uma lista ordenada de despertar leva entre O(N log N) e O(N^2), dependendo do sistema operacional ou do runtime da linguagem.
  Em algum lugar por trás há uma lista ordenada, um heap ou um algoritmo N^2. Da mesma forma, o próprio sleep sort também é, no mínimo, tempo linear, já que precisa acordar N threads para emitir N itens ordenados.
  Pior ainda: o tempo real de relógio também aumenta conforme o tamanho dos valores. Dá para primeiro encontrar o mínimo e o máximo e comprimir o intervalo, mas isso também é tempo linear.

  • Correndo o risco de matar a piada, quando eu disse “tempo constante”, estava aludindo à linguagem e à forma da análise de complexidade, mas não estava falando literalmente nesse sentido.
    Aqui é uma piada de duplo sentido que explora duas perspectivas conflitantes da palavra “tempo”. Está certo que, do ponto de vista da análise de complexidade, é impossível fazer um algoritmo de ordenação em tempo constante.
    A intenção real da piada é o tempo de relógio. Numa entrevista, esse tempo é mais relevante e, na prática, quando alguém solta algo como “escreva uma função para ordenar inteiros”, raramente usa apenas números menores que 100, então esse programa parece rodar quase instantaneamente.
    É uma piada metalinguística sutil que brinca invertendo a compreensão de como a ciência da computação funciona. Pena que a piada não pegou.
  • Num universo com vida útil finita, tudo é tempo constante.
    https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
  • Teoricamente, como o argumento passado para sleep no fim precisa se reduzir a um inteiro, daria para processar em tempo linear usando algo como radix sort.
    Há espaços de problema em que isso compensa, mesmo que passe a haver dependência do tamanho do maior valor.
    Claro que, na prática, não existe um sistema desses. Timeouts de chamadas de sistema normalmente não são um caso em que essa abordagem seja vantajosa. E, obviamente, é melhor aplicar diretamente radix sort, que depende apenas de log(max_value), em vez de algo linearmente proporcional ao valor máximo.
  • O custo de criar N threads e adicioná-las a uma lista ordenada de despertar ser O(N log N) a O(N^2) não é uma limitação fundamental dos sistemas de escalonamento.
    Isso vale ainda mais se considerarmos hardware especial que permita escalonamento em tempo constante em relação ao número de threads. Por exemplo, embora não faça nenhum sentido econômico na prática, daria para criar um escalonador que rebate pacotes de informação com laser em um enorme conjunto de espelhos posicionados a diferentes distâncias, retornando-os a um detector conectado ao computador.
    Seria uma forma de usar a velocidade da luz para atrasar algo pelo tempo especificado. Portanto, o sleep sort não depende essencialmente da complexidade algorítmica oculta de algum método de escalonamento de threads; ainda que não seja prático, em teoria poderia ser otimizado para O(1).
  • Isso é parecido com o estilo de construir um cluster Kubernetes para retornar “Hello World”.

• Se você gostou disso, também existe uma espécie de continuação chamada Protos: https://xeiaso.net/blog/protos
  Tenho escrito mais histórias desse “universo”, mas demora um pouco para a energia satírica acumular. Talvez a próxima seja sobre computação espacial.

  • A parte “bem na hora em que o alerta de calendário avisa que a reunião stand-up está prestes a começar” parece o nosso universo.
    Ainda assim, aquele universo parece ser melhor em dar nomes.

• A parte de trocar threadDelay (100000 * time) por threadDelay (10000 * time) e dizer “agora ficou dez vezes mais rápido” tem relação com este texto: https://thedailywtf.com/articles/The-Speedup-Loop

• Não li o texto, mas odeio essas coisas. Uma vez fiz uma entrevista remota na Meta e a pessoa ficou comendo no microfone o tempo todo.
  Foi tão distrativo que eu até esqueci como se escreve um laço for.

  • Contratação remota é muito melhor. Antes, depois de uma conversa rápida com o recrutador ou o RH, você tinha que vestir terno e dirigir para longe ou pegar um voo, e normalmente perdia um dia inteiro.
    Se você já estivesse empregado, precisava tirar folga, e havia estresses como “estou desperdiçando minhas férias limitadas com isso?”, “vai ter estacionamento?”, “vou chegar no horário?”. Aí fazia uma “entrevista inicial” de 30 minutos, esperava semanas e então era chamado para uma entrevista de verdade ou simplesmente levava ghosting.
    O processo inteiro podia levar um mês e exigir pelo menos dois dias de folga e um deslocamento considerável.
    Hoje o recrutador ou o RH liga perguntando se você pode fazer uma chamada de vídeo, você fala por 15–20 minutos no mesmo dia, eles encaminham seu currículo para quem decide e marcam uma ou mais entrevistas por vídeo ou sessões técnicas. Algumas empresas pedem para você fazer testes comportamentais/técnicos confortavelmente de casa.
    Se você trabalha remoto, dá até para resolver tudo na hora do almoço. A largura de banda da comunicação presencial é muito maior, mas só remotamente dá para entrevistar com uma empresa de Tel Aviv de manhã, uma de Warsaw no almoço e uma da California à noite.

• Criar 1000 threads não é, no mínimo, tempo linear? Talvez dê para reduzir até log, mas não acho que aquele código faça isso automaticamente.

  • Depende do que você considera “tempo”. Se for tempo de complexidade algorítmica, é no mínimo linear mesmo. Se for tempo de relógio, ou seja, o tempo que mais importa no código de entrevista, é tempo constante.
  • É difícil dizer que sleep sort seja mais tempo constante do que outros algoritmos de ordenação.
    Para sleep sort ser tempo constante, seria preciso haver um limite superior para a entrada, isto é, uma restrição para o maior número, e não contar operações arbitrárias como ler e processar a entrada e criar threads.
    Mas, se permitirmos isso, todas as outras ordenações também viram tempo constante. Acho que permitir apenas uma dessas duas coisas já seria suficiente.
  • Na prática, nem é linear. Dormir é uma inserção em heap e leva O(log n).
  • Ele devia estar realmente dormindo durante a entrevista. Caso contrário, não dá para afirmar que a complexidade assintótica é “tempo constante” quando a primeira instrução do programa percorre sequencialmente todos os valores da entrada.

• Se o runtime de threads mantiver sua própria noção de tempo, o algoritmo nem precisa dormir em tempo real
  Depois que todas as threads forem criadas, o runtime consegue perceber que todas as threads estão ociosas e que a próxima thread a ser agendada é a do tempo N; então basta atualizar o tempo atual para N e executar essa thread. Repetindo isso, obtém-se um array ordenado sem nenhum sleep
  No fim, a tarefa de ordenação já terminou no momento em que as threads começam a dormir, e elas estão registradas em algum coordenador que vai acordá-las depois, por exemplo uma timer wheel. Não há necessidade de efetivamente dormir
  Não sei quanto a Haskell, mas o runtime tokio do Rust permite isso com start_paused: https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...

  • Entendo que isso é basicamente como uma simulação de eventos discretos funciona internamente. Com uma estrutura de dados adequada, por exemplo um heap, você mantém a fronteira dos eventos futuros e alterna entre adicionar eventos futuros ao heap e retirar do heap o próximo evento
    Deixando de lado as várias camadas de abstração e os detalhes de implementação omitidos, ordenar valores com um scheduler desses é simplesmente heapsort :)
  • Se você começar de fato a calcular o que deve ser executado em seguida, terá reinventado a selection sort, e isso já não é mais tempo linear. Por isso, na prática, não é um algoritmo de ordenação que faça sentido :)