A minha entrevista para a SAPO

Queria partilhar um episódio de algum tempo, até posso que afirmar que um pouco traumatizante. A minha entrevista para webdeveloper na SAPO.

Posso adiantar-vos que não estava nada preparado para o que me esperava. No fim fiquei de mãos a abanar e custou-me, para além do roubo do preço pelo estacionamento, ali mesmo em frente ao edifício da PT, umas horitas de vida. Contudo, foi um gosto conhecer a malta da SAPO e o espaço/ambiente.

O espaço é engraçado, muito verde (óptimo para daltónicos e sportinguistas) com uma sala própria para workout. E os colaboradores, muito habituados a estas lides de entrevistas, têm já um batalhão de questões para separar o trigo do joio que lhes é apresentado pelas empresas de RH. O processo que usam é: colocam a questão; vão criando um nível de complexidade nas questões sucessivas até que o entrevistado "rebente". Penso que a ideia é perceber o limite dos conhecimentos e criatividade no solucionamento dos problemas.

Foram aboradados vários temas, desde segurança, bases de dados, servidores, algoritmia...

Para mim, de facto a entrevista foi tão traumatizante, talvez mais pela parte mais desumana do processo, que ainda me lembro de cor algumas dessas questões que quero aqui partilhar.

Uma das primeiras questões foi:

• Tens uma conjunto de endereços IP em base de dados e queres apenas os IPs de uma determinada gama.

• Conhece o protocolo HTTP?

• Onde são guardadas as sessões?

• Para que serve o apache e o PHP? Que funções têm?

• Desenhar uma expressão regular para os número de telefone da TMN e email

• Já ao nível de base de dados, eles partilham no blog. Para mim, a abstracção, foi o mais complicado

«Tomemos como exemplo a seguinte tabela, onde anotamos quanto dinheiro emprestamos a cada pessoa, sendo que já emprestamos dinheiro mais que uma vez a algumas pessoas:

| nome | valor |

|--------------|

| josé  | 20   |

| joão  | 10   |

| rui   | 5    |

| pedro | 3    |

| josé  | 5    |

| pedro | 10   |

| luís  | 25   |

|--------------|

Tendo por base esta tabela, o problema consiste em escrever várias queries SQL para:

• Descobrir quanto dinheiro emprestaste no total.

• Descobrir quanto é que cada pessoa te deve.

• Descobrir quais as pessoas a quem emprestaste dinheiro mais que uma vez.

• Seleccionar os nomes das pessoas a quem emprestaste dinheiro, numa só linha, separados por vírgula.

Para quem quiser tentar responder a este problema sugere-se a criação da tabela e o teste das queries no computador.»

• Outra de base de dados, foi a seguinte. Tens um texto enorme. Deram-me um exemplo de um livro. Como deve ficar a estrutura de base de dados para que possas pesquisá-lo. As pesquisas por texto (mas não é de pequenas strings, é de páginas inteiras).

• Ao nível da algoritmia, como calcular a maior diferença entre dois números numa lista. A pergunta e resposta estão ambas no blog.

«O problema consistia em desenhar (escrever) um algoritmo para resolver o seguinte problema, em pseudo-código:

"Vais receber uma lista de números. Encontra a maior diferença entre quaisquer dois números nessa lista."

Hoje vamos analisar algumas das soluções com que nos deparámos nas entrevistas.

Estranhamente, uma solução que é apresentada com frequência é a seguinte:
  maior_diferenca = 0;

   for ( i = 1 ; i < length lista ; i++ ) {
       if ( lista[i] - lista[i-1] > maior_diferenca ) {
           maior_diferenca = lista[i] - lista[i-1];
       }
   }

   return maior_diferenca;
Esta é uma solução que não apresenta o resultado correcto e que demonstra uma série de problemas no raciocínio do candidato (problemas esses que não iremos abordar aqui, mas é de facto uma situação comum).

Eis a solução mais básica que poderia ser apresentada (seguindo-se a lista de problemas que a mesma apresenta):
  maior_diferenca = 0;

   for ( i = 0 ; i < length lista ; i++ ) {
       for ( j = 0 ; j < length lista ; j++ ) {
           if ( abs( lista[i] - lista[j] > maior_diferenca ) ) {
               maior_diferenca = abs( lista[i] - lista[j] );
           }
       }
   }

   return maior_diferenca;
Problemas de eficiência:

• Para cada dois números na lista, a diferença é calculada duas vezes
• Em cada um dos ciclos, o resultado de "length lista" é calculado n vezes

Erros e corner-cases:

• O valor 0 é retornado caso a lista seja vazia ou tenha apenas um elemento.

Vejamos agora a mesma solução já com alguns destes problemas resolvidos:
  maior_diferenca = 0;

   tamanho = length lista;

   for ( i = 0 ; i < tamanho ; i++ ) {
       for ( j = i+1 ; j < tamanho ; j++ ) {
           diferenca = abs( lista[i] - lista[j] );
           if ( diferenca_actual > maior_diferenca ) ) {
               maior_diferenca = diferenca_actual;
           }
       }
   }

   return maior_diferenca;
Apesar de esta solução ainda não estar a prever os casos da lista vazia ou da lista com um único elemento, esta já é uma solução mais eficiente que a anterior.

Ainda assim, um bom candidato consegue, desde o início, compreender que não necessita realizar tantas operações, já que lhe basta encontrar o maior e o menor elemento da lista e calcular a diferença entre dois.

Infelizmente, isto faz com que alguns candidatos apresentem uma solução semelhante à seguinte:
  lista = sort  lista;
   max   = last  lista;
   min   = first lista;
   return max - min;
Apesar da solução estar correcta, não é de todo eficaz, dada a complexidade de um sort numa lista com, por exemplo, 20,000 valores.

Eis uma outra solução seguindo esta ideia, ainda com alguns problemas:
  min = 0;
   max = 0;

   for ( i = 0; i < tamanho; i++ ) {
       if ( lista[i] < min ) {
           min = lista[i];
       }

       if ( lista[i] > max ) {
           max = lista[i];
       }
   }

   return max - min;
Esta é uma solução que não funciona, uma vez que basta que todos os números sejam positivos ou negativos para retornar o valor errado.

Uma melhor solução seria algo no seguinte sentido:
  min = null;
   max = null;

   for ( i = 0; i < tamanho; i++ ) {
       if ( min == null or lista[i] < min ) {
           min = lista[i];
       }

       if ( max == null or lista[i] > max ) {
           max = lista[i];
       }
   }

   if ( min != null and max != null ) {
       return max - min;
   }
   else {
       # ...
   }
Entre todas estas versões, há ainda mais uma série de variantes que outros candidatos apresentam.

Há também questões específicas de cada linguagem que podem fazer com que pequenas partes devam ser alteradas por uma questão de eficiência.

Ao ser confrontado com este problema, o candidato ideal:

• sabe que a lista pode ser vazia ou ter apenas um elemento
• sabe que a lista pode ser enorme (e não tenta fazer um sort)
• sabe que a lista recebida pode ter elementos que não sejam números
• percebe quase imediatamente que basta encontrar o máximo e o mínimo da lista
• consegue sugerir uma ou mais soluções para quando não é possível encontrar uma diferença
• resolve o problema rápida e eficazmente, e sabe explicar porque fez o que fez

Convém ainda deixar claro que este é apenas um problema que fez parte de um grande conjunto de desafios colocados aos candidatos e que não é apenas a resolução de um simples problema que dita o recrutamento ou não da pessoa.

»

• Tens 2 variáveis, dois números, como transferes os valores de uma variável para a outra? Depois, sem usar uma terceira variável auxiliar.

• Outras questões relacionadas com webservices:
• Sabes o que são Webservices?
• Para que serve o WSDL?

• Esta, se não foi a última, foi das últimas. Problema: tem um webservice que disponibiliza apenas 15 resultados,  e você apresenta 20 em cada página, como faz para mostrar os 20. Como ter paginação?

Se me lembrar de mais, vou colocando...

Boa sorte!