Em Fevereiro tornamos público um problema que foi usado nas entrevistas no SAPO durante 2009.

O problema, orientado a candidatos com um background forte em ambientes Linux/UNIX, consistia no seguinte:

"Encontras-te sozinho num Data Center e tens que resolver este problema sem recurso a meios exteriores (nada de telemóvel, nada de internet; o objectivo é resolveres tu o problema). Tens um servidor que não pode ir abaixo. Nessa máquina, alguém teve a brilhante ideia de executar um `chmod -x chmod`. Resolve o problema."

O primeiro ponto a apontar é o objectivo deste problema.

O objectivo não é avaliar se o candidato consegue resolver a situação, mas sim a sua reacção. O ideal seria um misto de excitação, pânico e um olho a saltar fora.

A pergunta serve, no entanto, para avaliar o conhecimento que a pessoa tem sobre estes sistemas e a capacidade de improviso/imaginação.

Durante alguns meses, a cada 3 entrevistas em que usávamos este problema, surgia uma resposta nova.

Hoje vamos abordar algumas delas.

Começamos por soluções que não se aplicam às circunstâncias descritas, como tirar o disco e levá-lo a outra máquina que ainda tenha o chmod operacional.

De seguida, partimos para outras soluções curtas e viáveis:

• usar o perl da máquina, que não usa o chmod ao qual retiramos as permissões

perl -e 'chmod 0755, "chmod"'

• usar o python da máquina, que também não usa o chmod ao qual retiramos as permissões

python -c "import os;os.chmod('testing', 0777)"

• usar o cc para criar um pequeno programa em C que altere as permissões do executável (de forma a que quando compilado tem permissões de escrita)
• lançar a BusyBox, que tem um chmod lá dentro

Algumas soluções semelhantes mas com ligeiras nuances:

• copiar um outro executável para um novo, que fica com as permissões correctas, e copiar o conteúdo do chmod para lá
• usar o cc para criar um outro executável, com permissões de execução, e de seguida copiar o conteúdo do chmod para lá

cat /bin/chmod > new_executable

• fazer um tar do ficheiro e editar o tar para alterar as permissões lá dentro
• fazer um tar do ficheiro alterando as permissões dos ficheiros ao adicioná-los
• usar o tar para criar um arquivo com as permissões correctas e descompactá-lo on-the-fly:

tar --mode 555 -cvf - chmod | tar xvf -

• fazer algo semelhante com o cpio

echo chmod | cpio -o | perl -pe 's/^(.{21}).../${1}755/' | cpio -i -u

Depois começam a surgir soluções que são dependentes da distribuição:

• em Debian, ver se o pacote ainda está em cache
• em Red Hat, usando o yum, ir ver se o RPM ainda está na máquina

E há mais (getfacl, setfacl, chflags, etc.), cada uma mais inovadora que a anterior (como um `alias chmod='/lib/ld-2.11.1.so /bin/chmod`, ou o exemplo mais abaixo).


Convém neste ponto explicar o que se sucede quando se coloca uma questão destas numa entrevista.

A interacção em torno deste problema não se cinge a uma pergunta e uma resposta, mas sim à exploração do conhecimento e capacidade inventiva da pessoa.

Eis um exemplo baseado numa entrevista verídica:

Candidato - Tenho perl na máquina?

Entrevistador - Tens.

C - Então uso o chmod do perl, que é built-in!

E - Certo. Agora vou-te tirar o perl da máquina.

C - Hum... Tenho cc?

E - Tens.

C - Então posso fazer um programa em C que usa a system call do chmod para alterar as permissões ao chmod.

E - Certo. Agora vou-te tirar o compilador.

C - Hum... Disseste que não tenho acesso à net, mas não disseste nada sobre os outros servidores no Data Center. Abro um socket para outro servidor, faço um tar do chmod de lá preservando as permissões, trago-o para a máquina a faço untar.

E - Certo. Agora vou-te tirar as outras máquinas do Data Center.

C - OK... Bem, posso sempre lançar a BusyBox, que deve estar na máquina e que tem o chmod lá dentro!

E - OK, mas agora vamos-te tirar a BusyBox. Consegues arranjar outra maneira de resolver o problema?

[o candidato pensa um pouco, olha para cima e fala como se estivesse a falar consigo próprio]

C - Eia... Esta é mesmo rabuscada... Faço um attrib ou um ls extendido para forçar o inode para a cache; agora só tenho que editar o inode que está em cache sem que o kernel se aperceba, e posso usar o sed para isso, desde que seja root; vou ao kcore procurar as estruturas do VFS e altero-lhe o bit de execução; vou é ter que ler documentação; depois é só usar o chmod para lhe repor as permissões.

[breve pausa para recuperarmos]


(já agora, e a título informativo, o candidato do texto acima encontra-se hoje em dia a trabalhar no SAPO)


Para além de todas estas (e outras) soluções (e tentativas de solução) que nos foram aparecendo, surgiram também alguns comentários interessantes como:

- Resolver o problema? Qual problema? A máquina continua a funcionar!

E questões como:

- Mas porque raio é que a bin de um servidor estava writable?

Amanhã, dia 21, a partir das 14:00, a PT estará presente no BEST Career Days, no IST (na Alameda).

Este evento conta com três apresentações do grupo, entre as quais duas são asseguradas por colaboradores do SAPO:

14:00 - Apresentação PT e Testemunhos Trainees

15:00 - Como funcionam as entrevistas técnicas (por José Castro)

15:30 - Como funciona o mundo da Publicidade Digital (por João Pedro Gonçalves)

Será no Auditório do Complexo Interdisciplinar.

A quinta edição do ENEI tem lugar de 8 a 11 de Abril de 2010 em Coimbra.

Várias centenas de estudantes são esperados para 4 dias de workshops e apresentações dos mais variados temas.

O SAPO foi convidado a realizar duas apresentações.

Estaremos presentes no dia 9 pelas 17:00 para falar das entrevistas técnicas no SAPO e no dia 10 pelas 15:30 para falar da plataforma SAPO Mapas.

O prazo limite para inscrição no evento termina hoje.

Antes ainda de analisarmos o problema do chmod e as suas múltiplas soluções, eis um problema relativamente simples de SQL.

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.

Tipicamente as entrevistas no SAPO seguem o caminho que mais conforto dá ao candidato.

Se a pessoa trabalhou mais com determinada tecnologia, é esse o assunto que vamos abordar.

Se a pessoa passou mais tempo a realizar um tipo de tarefa, é essa a informação que vamos procurar.

Quando um candidato nos afirma que se sente muito confortável em ambientes Linux e, numa escala de 0 a 1, classifica a sua proficiência como um 0.9, por exemplo, este é um exercício que colocámos bastantes vezes no ano passado:

"Encontras-te sozinho num Data Center e tens que resolver este problema sem recurso a meios exteriores (nada de telemóvel, nada de internet; o objectivo é resolveres tu o problema). Tens um servidor que não pode ir abaixo. Nessa máquina, alguém teve a brilhante ideia de executar um `chmod -x chmod`. Resolve o problema."

Brevemente discutiremos o que se pretende com um problema deste género e algumas das respostas que fomos juntando durante o ano, quer nas entrevistas, quer no seio da nossa equipa.

Recentemente colocámos neste blog um post com um dos problemas que usamos em muitas das entrevistas de 2009 no SAPO.

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.

A título da SAPO Session desta semana, em que abordaremos o tema do recrutamento, divulgamos hoje um dos problemas que foi usado em muitas das entrevistas técnicas que realizamos este ano.

O objectivo é que o candidato escreva, em papel, um algoritmo para soluccionar o seguinte problema:

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

É suposto o algoritmo ser escrito em pseudo-código. Não é de todo necessário que o mesmo compile, mas é necessário que se consiga ler e perceber.

Este é um problema com muitas nuances que serão explicadas num outro post a ser publicado muito em breve, logo depois de darmos uns dias para que todos possam preparar a sua solução.

De notar que é esperado que o problema seja resolvido em menos de cinco minutos, e não no decorrer de vários dias de estudo e optimização.

Fica a sugestão aos leitores: resolva o problema, em papel. Aquando da publicação da solução, compare a sua com a esperada.

UPDATE: 10 lugares atribuídos, 0 lugares disponíveis.

Na SAPO Session desta semana iremos levantar um pouco o véu sobre o processo de recrutamento e gestão da equipa técnica do SAPO.

As apresentações:

• Recrutamento técnico no SAPO, por José Castro

"O modus operandi do recrutamento no SAPO. Triagem de perfis, análise de CVs, entrevistas e selecção de candidatos."

• Gestão da equipa técnica do SAPO, por João Sil

"Como é feita a gestão de recursos no SAPO. Acolhimento, gestão, acompanhamento e evolução no seio de uma equipa com mais de 150 técnicos."

Temos dez lugares para o público em geral, a custo zero, a serem atribuídos aos primeiros dez emails a chegar a saposessions em sapo ponto pt referindo esta sessão no subject ou no corpo do email.

Este evento tem lugar em Picoas, Lisboa, e decorre das 09:30 às 12:30 do dia 4 de Novembro de 2009.

O grupo PT realiza este mês um Roadshow sobre o programa Trainees.

No contexto deste programa iremos recrutar recém-licenciados em várias áreas para que possam iniciar as suas carreiras profissionais em empresas do grupo PT.

O âmbito do Trainees foca-se este ano em engenharias informáticas, engenharias electrotécnicas, gestão industrial e economia, entre outras.

O SAPO é uma dessas empresas e está também presente em várias destas acções de divulgação e recrutamento.

Hoje estamos na Faculdade de Ciências e Tecnologia, no Monte da Caparica.

Amanhã estaremos na Universidade do Minho, em Braga.