sexta-feira, 20 de dezembro de 2013

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.

Parte 1


O início da entrevista passa por uma breve apresentação do entrevistador: nome, função e projecto em que trabalha. De seguida, o entrevistador pode passar directamente para a Parte 2 ou fazer algumas perguntas iniciais para quebrar o gelo e começar a conversa. Alguns exemplos de perguntas:
  • Coisas sobre o CV (algum projecto mencionado, tópicos de investigação, etc).
  • Conceitos relacionados com a linguagem de programação favorita do candidato ou programação em geral (e.g. qual é a diferença entre overloading e overriding?).
  • Um puzzle de resposta rápida (exemplos).

Parte 2


A grande maioria das entrevistas requer que o candidato resolva algumas coding questions e implemente a solução na sua linguagem de programação favorita (mas normalmente entre C++, Java ou Python). Numa entrevista telefónica, a implementação é feita num Google Docs, se for uma entrevista presencial, a implementação é feita à mão num whiteboard. O código tipicamente não precisa de estar 100% compilável (alguns entrevistadores são mais exigentes do que outros), mas pseudo-código não costuma ser permitido.
Esta parte foca-se mais na forma de pensar do candidato do que propriamente encontrar a "resposta certa". As perguntas podem ser propositadamente vagas e é negativo se o candidato saltar para soluções sem clarificar os objectivos da pergunta.

Entrevistador: Escreve uma função que dado um array com N números inteiros, determina o K-ésimo menor número presente no array.

Nós: Podemos alterar o array?

E: Sim.

É importante fazer perguntas para esclarecer dúvidas sobre o enunciado. De preferência, não se deve assumir nada sem a confirmação com o entrevistador.

Nós: Uma solução simples é ordenar o array de forma crescente e devolver o elemento na posição K-1. Esta abordagem seria O(N log N).

E: Ok. Consegues fazer melhor?

Nós: Há algoritmos de selecção lineares - O(N). O Quickselect é semelhante ao Quicksort.

E: Como é que o Quickselect funciona?

Nós: À semelhança do Quicksort, o algoritmo escolhe um pivot e coloca todos os números menores ou iguais ao pivot do lado esquerdo do array, os números maiores à direita e o pivot no meio. Sabendo que o pivot é o X-ésimo menor elemento do array, é possível saber onde está o K-ésimo número que queremos:

  • Se X = K, então o K-ésimo número é o pivot
  • Se X < K, então o K-ésimo número está na parte direita do array
  • Se X > K, então o K-ésimo número está na parte esquerda
A diferença do Quickselect para o Quicksort é que o algoritmo só é chamado recursivamente numa das partes do array. Daí ter um tempo esperado de O(N) em vez de O(N log N).

E: "Esperado"?

Nós: Sim. Tem um worst case de O(N2) tal como o Quicksort, mas corre em O(N) na grande maioria dos casos. Existe outro algoritmo baseado na mediana das medianas que garante O(N) no worst case.

E: Porque é que o worst case do Quickselect é O(N2)?

Nós: Se tivermos azar sucessivamente na escolha do pivot, podemos estar a escolher o elemento máximo ou mínimo do array, fazendo com que o número de elementos a considerar em cada chamada recursiva só diminua por 1. Isto é, o tamanho do array vai ser N, N-1, N-2, N-3,..,1 ao longo das chamadas recursivas, logo o "trabalho" é N chamadas recursivas * (1+2+3+..N) = N*(N+1)/2 ~ O(N2).
A probabilidade de isto acontecer com um pivot aleatório é extremamente baixa.

E: Que outros métodos de escolha de pivots conheces?

Nós: Podemos escolher sempre um pivot fixo, o número na 1ª posição por exemplo, mas um método melhor é pegar em 3 números e seleccionar a sua mediana como pivot.

E: Porque é que esse método é melhor?

Nós: O pivot ideal é a mediana do array porque permite descartar metade dos elementos numa iteração. A mediana de 3 números oferece uma estimativa melhor da verdadeira mediana do array e espera-se que nos permita descartar mais números em cada iteração do que um pivot qualquer.

E: Ok, entre as abordagens que referiste, qual é que escolherias?

Nós: O Quickselect. Apesar de ter um worst case de O(N2), é muito rápido na prática e tem um factor constante bastante menor que o algoritmo da mediana das medianas.

E: Ok, implementa-o.

Nós: Posso assumir que o K está entre 1 e N?

E: Sim.

Idealmente, convém explicar o código à medida que escrevemos a solução. Parte da explicação dada acima poderia ser feita enquanto estamos a escrever o código
Nós: Terminei.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Partição por pivot aleatório. Retorna a posição do pivot.
int Partition(int* numeros, int n) {
    int pivot_pos = rand() % n;
    int pivot = numeros[pivot_pos], left = 1;
    swap(numeros[0], numeros[pivot_pos]);
    for (int i = 1; i < n; i++) {
        if (numeros[i] <= pivot) {
            swap(numeros[i], numeros[left]);
            left++;
        }
    }
    swap(numeros[0], numeros[left-1]);
    return left-1;
}
int QuickSelect(int* numeros, int n, int k) {
    if (n == 1) {
        return numeros[0];
    }
    int num_left = Partition(numeros, n) + 1;
    if (num_left == k) {  
        return numeros[num_left -1];  // o pivot é o k-ésimo número
    } else if (num_left < k) {
        return QuickSelect(numeros+num_left , n-num_left , k-num_left);
    } else {
        return QuickSelect(numeros, num_left-1, k);
    }
}
É boa ideia "testar" manualmente o código. Se o entrevistador detectar bugs, dá dicas para o candidato os encontrar e corrigir

E: Ok. Supõe agora que em vez de um array, estamos a receber números de um stream. Este stream suporta as operações HasNext() e GetNext(), para saber se existem mais números por receber e obter um número, respectivamente. Como farias?

Nós: Podemos colocar os números num array e reduzir isto ao problema anterior?

E: Não. Não temos memória suficiente para isso.

Nós: Mas o K é suficientemente pequeno para termos K números em memória?

E: Sim.

Nós: Nesse caso, podemos processar os números pela ordem que os recebemos no stream e manter os K números mais pequenos em cada momento. Se utilizarmos uma max-heap como a priority_queue da STL, podemos adicionar cada número à heap e eliminar o maior número da heap se o seu tamanho exceder K números porque esse número não poderá ser o K-ésimo mais pequeno. Depois de processarmos todos os números, o K-ésimo mais pequeno é o maior número na heap.
Como o tamanho da heap não excede K+1, cada operação de inserção e remoção corre em O(log K). Se o stream tiver N números, o tempo total do algoritmo é O(N log K).

E: Ok. Implementa. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int KesimoMaiorStream(Stream* stream, int k) {
    priority_queue<int> heap;
    while (stream->HasNext()) {
        heap.push(stream->GetNext());
        if (heap.size() > k) {
            heap.pop();
        }
    }
    if (heap.size() == k) {
        return heap.top();
    } else {
        return -1;  // ou outro valor significando erro.
    }
}
Mais uma vez, se o entrevistador detectar bugs, dá dicas para o candidato os encontrar e corrigir

Parte 3


Para além de perguntas para programar, uma parte importante das entrevistas é o System Design. Estas são perguntas mais abstractas, sem código, onde se discute a melhor forma de desenhar um sistema para responder a um determinado cenário.

Entrevistador: Supõe que tens uma rede de computadores, onde cada computador guarda logs de urls visitados. Como é que farias para determinar quais são os 10 urls mais visitados globalmente?

Nós: Qual é a estrutura dos logs? E o que significa exactamente ser dos 10 urls mais visitados?

E: Cada log é composto por registos com o url e data de uma visita a um site. Assim, queremos os 10 urls com maior soma de número de visitas efectuadas por todos os computadores.

Nós: Uma solução inicial poderia ser agregar o número de visitas por computador, criando um mapeamento url -> numero_visitas. Isto poderia ser feito com um Hash Map de forma eficiente. De seguida, esta informação podia ser enviada para um computador central que depois soma o número de visitas em cada site e produz a lista dos mais visitados.

É boa ideia começar com uma solução básica. Para além de poder ser um bom ponto de partida, ganha-se tempo para pensar numa solução melhor

E: Ok, mas é demasiada informação para concentrar num computador central...

Nós: Uma alternativa melhor é aproveitar as propriedades do hashing após agregarmos o número de visitas de cada url por computador. Se utilizarmos uma boa função de hash, esta pode transformar o texto dos urls em números distribuídos de forma uniforme num certo intervalo [0, MAX_HASH].
Assim, podemos dividir este intervalo [0, MAX_HASH] em partes iguais, uma por cada computador. Cada computador fica responsável por agregar os resultados dos urls cujo valor de hash se encontre na sua parte.
Depois da fase inicial, cada computador envia a informação do 1º mapeamento para o computador responsável de cada url. Posto isto, cada computador agrega os números de visitas por url e determina os seus 10 urls mais visitados usando uma heap como na pergunta anterior, por exemplo. Usando uma boa função de hash, é esperado que o trabalho seja distribuído de forma uniforme por todos os computadores.
Por fim, cada computador envia o seu top 10 para um computador central, que determina o top 10 global usando o mesmo método. Como são só 10 por computador, esperamos que o computador central não tenha problemas em processar o resultado final.

Apesar da descrição informal, esta abordagem tem semelhanças com o paradigma MapReduce

Parte 4


Esta é a última fase de qualquer entrevista, onde podemos colocar perguntas ao entrevistador. Esta fase é importante para perceber como as coisas funcionam do lado da empresa. Algumas sugestões de perguntas:
  • Como é que vocês se organizam em equipas e qual é a metodologia de desenvolvimento?
  • É normal colaborar com equipas de outros países? Como funciona esta colaboração?
  • Como é trabalhar em Nova Iorque comparado com o Silicon Valley?
  • 10 questions to ask your potential employer

Conclusão


Um factor muitas vezes menosprezado nestas entrevistas é o nervosismo e o stress. Estes factores podem levar-nos a bloquear completamente. Na minha 2ª entrevista telefónica em 2011, eu estava super nervoso e bloqueei durante uns 3 minutos (3 a 5 em 45 minutos não é tão pouco quanto isso) numa altura estranha porque já tinha identificado e discutido a solução para uma pergunta e bloqueei a meio de escrever o código (que deveria ser a parte mais fácil). A minha sugestão é tentarem relaxar o máximo possível antes da entrevista e, caso bloqueiem, peçam dicas ao entrevistador. Mais vale perder uns pontos pelas dicas do que estragar a entrevista completamente.

Existem outros artigos com uma descrição mais geral do estilo das entrevistas (como este ou este) e até um video no youtube com dicas para entrevistas.
Estes são apenas exemplos de perguntas e tópicos possíveis. Dariam respostas diferentes a estas perguntas?


Publicada por à(s)
Etiquetas: , , ,

Sem comentários:

Enviar um comentário

Subscrever: Enviar feedback (Atom)