segunda-feira, 23 de dezembro de 2013

Desafio: 25 cavalos

Nesta quadra natalícia, deixo-vos o meu puzzle favorito. Não requer nenhuns conhecimentos especiais, só lógica. Aproveitem e desafiem a vossa família ; )
Tens 25 cavalos e podes fazer corridas de 5 cavalos. Não tens um relógio para medir os tempos, só sabes a ordem dos cavalos em cada corrida. Qual é o número mínimo de corridas necessário para determinar os 3 cavalos mais rápidos?

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.

quinta-feira, 5 de dezembro de 2013

MIUP 2013 - Um problema de Grafos

Não tive oportunidade de escrever no blog nas últimas semanas. Para compensar, hoje vou falar de um problema um pouco mais difícil do o habitual: o problema B da MIUP 2013 - Say Geese.

Objectivo do problema:
Dado um grafo não-dirigido com N (<= 11) vértices e E (<= 45) arestas (edges), quantos subconjuntos de arestas formam um grafo conexo?