sgo.to posts drafts

Minha Entrevista No Google

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