Minha Entrevista No Google
Sam Goto
Esse daqui é um email que eu escrevei e mandei para 5 pessoas assim que eu terminei a minha entrevista de estágio que fiz por telefone em 2006, enquanto eu estava no quinto ano da faculdade.
Ao longo dos anos, conforme a galera ia se aplicando para entrevistar no google, eu mandava para o pessoal um log da minha entrevista para dar uma noção do nível de preparo que se espera. Pelo menos 70+ pessoas já receberam esse email diretamente por mim.
Eu escrevi separadamente algumas dicas de como se preparar para o processo de entrevista do Google aqui.
Essa daqui foi a minha entrevista de estágio. A minha entrevista para engenheiro foi feita por 4 engenheiros (3 reviewers ao longo do estágio e 1 pessoal) e eu não botei no papel as perguntas que foram feitas :(
As perguntas que me fizeram já são relativamente conhecidas publicamente, e o Google me autorizou publicar esse log aqui. Subject: Entrevista Com O Google Ae galera !!!
Puta que pariu, acabei de sair de uma entrevista com o Google, e estou te repassando esse email para falar da minha experiência que talvez seja importante pra vocês durante alguma entrevista de trabalho ...
Porra, o baguio foi foda, os negos chutaram o balde !! hehehe !!!
Olha só as perguntas que me fizeram :
Entrevistador 1
1) Entrevistador : No orkut, vc tem o negócio de quando você está na página de uma pessoa, o orkut mostra o "caminho" entre você e esta pessoa ( Samuel -> Aloisio -> Julia -> Beto 03 ). Como achar o caminho mínimo, e qual a ordem do custo ?
Eu : primeira idéia : depth first search
Entrevistador : qual o problema ?
Eu : estouro de memória
Eu : dijstra, O( n ** depth )
Entrevistador : Descreva dijistra e analise o custo. O que é n ?
Eu : O grau de "relacionamentos" médio de pessoas.
( descrevo dijistra e calculo a ordem O() )
Entrevistador : existe algorítimo melhor
Minha resposta : melhor que dijistra ?
Entrevistador : sim. Esqueça o "Algorithims Text Book" e pense como o grafo está apresentado.
Eu : heurísticas. Procurar primeiro pessoas em comum, etc.
Entrevistador : sem usar heurísticas.
Eu : ( droga ! hehe )
Pensei, pensei, pensei, e cheguei em um O( n ** depth / 2 ) com um dijistra bi direcional search ( do Beto03 aa mim, e de mim ao Beto03. Para quando encontra alguém em comum no meio ). É isso que eles fazem.
2) Entrevistador : Imagina q vc tem dois vetores de USER IDS ordenados, representando os amigos de duas pessoas. Como você faria para achar os amigos em comum ( intersecção dos vetores )
Eu : Um primeiro approach que funciona é procurar para todos os usuários do array 1 no array 2, mas provavelmente isso não vai te satisfazer.
Entrevistador : Sim, você pode fazer melhor. Mas só por curiosidade, qual a ordem desse algorítimo.
Eu : n * m
Entrevistador : certo. Faça melhor do que isso.
Eu : Pra cada elemento de n, procure em m com uma busca binária.
Entrevistador : perfeito. Na verdade, é isso que a gente usa na maioria dos casos aqui no Orkut. Qual o custo disso ?
Eu : puta véio ... hehe ... humm ... ávore binária ... linear no primeiro vetor .... humm ... n * log2 m
Entrevistador : perfeito. Melhore o primeiro algoritímo.
Eu : Bom, como os vetores estão ordenados, você pode parar qnd o valor q vc tá procurando já é maior do que voce tá comparando.
Entrevistador : Ok. Custo ?
Eu : no pior caso, n * m
Entrevistador : Ok. Dá pra você fazer ainda melhor.
Eu : hummm .... bom, você pode parar também quando o valor que você tá procurando é menor do que o q você tá comparando (vetor ordenado). Além disso, você pode manter dois ponteiros, e continuar do lugar onde você parou da última vez.
Entrevistador : perfeito. Custo ?
Eu : n + m
Entrevistador : Ok. Agora me diga, em quais situações seria melhor vc usar a primeira versão ( árvore binária ) e em qual circunstância seria melhor vc usar a segunda ?
depois de alguns chutes
Eu : quando m fica muito grande. n + m > n log m
Entrevistador : perfeito ! Na verdade, é isso que a gente acaba fazendo aqui no orkut também.
Comenta alguma coisa sobre o orkut. Comenta alguma coisa sobre o google. Pede minhas sugestões sobre algumas coisas.
Entrevistador 2
me pergunta a respeito do Sinapse ( minha engine de xadrez ), da minha implementação de RPC sobre a rede jabber, sobre o meu sistema operacional, e sobre um componente que eu escrevi para o jabber.
Entrevistador : Você conhece a notação de fatorial ?
Eu : sim
Entrevistador : Ok. No resultado de fatorial ( n ), como você faria para calcular o número de zeros à direita ( trailling zeroes ) do resultado sem calcular o fatorial ? Imagina que n pode ser bastante grande ...
Eu : ( em voz baixa : " puta que pariu ! ") ...
depois de um tempo tentando entender o enunciado ...
Eu : Peraí, deixa eu ver se eu entendi ... f ( 5 ) = 1 2 3 4 5 = 120 . Então, temos um zero à direita. É isso que voce quer ?
Entrevistador : sim
Eu : ( em voz baixa : " puta véio ! " )
Eu : pensando ... 2 * 5 = 10 ...
Eu : pensando ... 4 * 5 = 20 ... 4 * 25 = 100 ....
Eu : Ok ... se vc contar o número de duplas de números pares e potências de 5 e de 10, você terá o seu resultado ( par, potência de 5 e 10 ). Para cada potência n > 1, conte n vezes.
Entrevistador : perfeito. Você está esquecendo de alguma coisa, que provavelmente só vai conseguir enxergar quando montar direito o algorítimo, mas está bom.
Eu : ufa
Entrevistador : Agora, vc está acostumado com aplicações multi trheaded ?
Eu : sim. Vi na graduação, e já debuguei muito código ao escrever o micro kernel do unicampOS.
Entrevistador : Ok. Me diga a definição de read locks e write locks.
Eu : read locks, são locks shared. vários processos podem pegar, contanto que não tenho um write lock no objeto. write locks são locks exclusivos : um processo só pode pegar qnd ninguém tem nem shared nem x locks.
Entrevistador : Me de um exemplo de situação onde ocorrem dead locks.
Eu : grafo de espera ( wait graph ) cíclico, vários processos, vários resources
Entrevistador : Me diga mais ...
Eu :
processo 1 processo 2
W(A) W(B)
R(B) R(A)
context switch depois de p1 W(A) e p2 depois de W(B).
Entrevistador : como antecipar isso ?
Eu : 2 phase lock
conversamos sobre outras coisas ... ele me disse que o google ficou interessado em algumas das coisas que eu escrevi durante a graduação ... e acabou !
É isso ! Bom, espero que se vocês forem fazer uma entrevista vcs estejam mais preparados ( eu não sabia que era uma entrevista teórica/técnica ... pensei que fosse mais uma coisa pessoal do que técnica ... ) e que se saiam bem !!!
Repassem para quem vocês acharem interessante,
Abraços, mel