Pesquisa Binária - Parte 4: Uma pergunta de entrevista tramada

Para fechar este ciclo sobre a pesquisa binária, sugiro uma pergunta de entrevista:

Dados 2 arrays de inteiros ordenados de forma crescente, determina o K-ésimo número mais pequeno do conjunto dos 2 arrays em tempo sublinear e com O(1) de memória extra.

Exemplo de entrevista para Engenheiro de Software na Google

No mês passado, concorri a um estágio de verão na Google. O processo foi relativamente rápido (3~4 semanas), visto que já estagiei na Google no ano passado, e para minha satisfação, recebi a desejada oferta para estagiar no próximo verão em Nova Iorque :)

Para quem estiver interessado em concorrer a uma posição na Google, este post exemplifica uma entrevista para a posição de Engenheiro de Software (Amazon, Apple, Facebook, Microsoft, usam estilos semelhantes). São apresentadas possíveis questões e a forma como eu responderia, para além de alguns comentários sobre o raciocínio (em itálico). Notas prévias:

1. Esta é apenas a minha visão do funcionamento das entrevistas e não necessariamente a da Google.
2. Não pretendo, de modo algum, afirmar que esta é a melhor forma de responder a estas perguntas. Estas são simplesmente as respostas que eu daria e o tipo de raciocínio que utilizaria.
3. Estas perguntas não foram tiradas das minhas entrevistas, mas são exemplos representativos.

Estas entrevistas, quer sejam feitas por telefone ou presencialmente, têm uma duração de 45 minutos e podem ser tipicamente divididas em 4 partes:

1. Quebrar o gelo
2. Coding - perguntas para as quais temos de implementar a nossa solução
3. System Design - perguntas mais genéricas para discussão aberta
4. Espaço para fazer perguntas ao entrevistador

A única parte obrigatória é a parte 4. De resto, as entrevistas podem tocar em perguntas de cada parte ou focar-se só nas partes 2 ou 3. Uma regra de ouro é não estar muito tempo calado, mas procurar explicar ao máximo aquilo em que estamos a pensar. Caso contrário, o(a) entrevistador(a) não faz ideia se percebemos bem a pergunta ou se estamos com dificuldades.