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.

Depois do Codebits, o dia começou tarde.

 

Com o feriado amanhã, ainda está pouca gente.

 

Ainda assim, a equipa Mobile do SAPO está presente em peso, e tem motivos para isso: Brian LeRoux está cá.

 

 

Após um almoço de sushi a equipa passa agora a tarde com o Brian: visita guiada ao SAPO, demos e testes de uma série de produtos e plataformas e depois uma sessão de formação.

 

Quanto à fotografia que se segue, a única dificuldade em tirá-la foi perceber quais eram os protótipos que ainda não podiam ser fotografados:

 

 

Obrigado, Brian!

 

 

Há mais de um ano atrás dois elementos da equipa do SAPO Messenger tiveram uma ideia para um agregador de redes sociais diferente dos usuais.

Esboçaram a ideia, desenharam uns bonecos, marcaram uma reunião com as chefias e apresentaram o conceito.

A ideia foi bem recebida e o projecto recebeu luz verde.

 

Durante os meses que se seguiram foram recrutadas mais quatro pessoas para se juntarem a estas duas.

A meio do desenvolvimento três outros projectos cederam temporariamente três colaboradores para reforçar a equipa de desenvolvimento.

À medida que o Pond foi ganhando forma, mais recursos foram alocados: quatro pessoas da equipa de Aplicações para Terminais Móveis para desenvolver os clientes nativos para vários Smartphones, duas pessoas da equipa de Multiplataforma para desenvolver a versão para plataformas móveis, etc.

Ontem fez-se um evento simbólico de lançamento da versão beta do Pond. Mais de vinte pessoas juntaram-se numa sala no SAPO para celebrar e relembrar, entre outras coisas, a promessa que um dos elementos da equipa tinha feito: "Quando isto estiver pronto, rapo o cabelo!"

 

O Pond está neste momento em Beta, aberto por convite. A equipa continua a trabalhar arduamente, adicionando novas features do Roadmap, incluindo conectores para mais redes sociais.

No SAPO Codebits haverá uma apresentação sobre o Pond que explicará melhor a ideia, o processo de desenvolvimento, os internals e a API da plataforma.

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.

A equipa do SAPO Fotos realizou-nos uma apresentação interna sobre a sua nova plataforma de entrega de imagens.

O SAPO Fotos conta já com mais de 5 milhões de fotos, submetidas por mais de 120,000 utilizadores, servindo uma média de 400 pedidos por segundo.

O quickCachr caracteriza-se principalmente pela utilização do Stormap (um server orientado a conteúdos estáticos desenvolvido no SAPO) numa farm com hosts redundantes e por vários módulos que tratam de aspectos como Load Balancing, tratamento de URLs legacy e atributos como a privacidade das imagens ou o tamanho solicitado nos pedidos.

Outro pormenor interessante da plataforma é a Legacy Box, um conjunto de máquinas para servir os URLs legacy. Estas máquinas fazem uso de Nginx, nginx_eval_module, memcached, Apache e PHP para servir estes URLs.

A equipa realizou testes de benchmarking com apenas um frontend e, tendo em conta vários níveis de concorrência, no pior cenário destes benchmarkings o quickCachr conseguiu um melhoramento (perante a plataforma actual) de 495 para 1,179 transacções por segundo; no melhor cenário, de 627 para 2,933.

O SAPO Codebits tem este ano lugar na Cordoaria Nacional, de 3 a 5 de Dezembro.

 

3 dias non-stop (o edifício fica aberto durante a noite, e haverá inclusivé uma área para dormir), com muita tecnologia, diversão, comida e bebida.

 

 

Basta fazer o registo e aguardar que comecemos a seleccionar os candidatos. De notar que o processo de selecção serve para garantir que os 600 participantes vêm de facto do mundo da informática: developers, web designers, sysadmins, DBAs, etc.

Os 600 participantes que forem seleccionados terão direito a uma série de apresentações e workshops, para além de muitos eventos paralelos e de várias surpresas ao longo dos três dias do evento.

 

Esta terceira edição do evento tem algumas novidades dignas de nota, entre as quais a aceitação de público oriundo do estrangeiro e a utilização do Inglês como língua oficial do evento. Convém no entanto salientar que o domínio da língua inglesa não é condiciante para se ir e se disfrutar do evento e que a abertura do evento ao estrangeiro não irá condicionar a presença do público português.

 

Podem manter-se a par das novidades deste ano no blog do Codebits ou seguindo o Codebits no Twitter. Vão aparecer por lá muitas surpresas.

 

E tu, já te inscreveste?

O SAPO faz hoje 14 anos.

 

4 países, dezenas de serviços, mais de 200 colaboradores, centenas de Terabytes, milhões de utilizadores.

 

Muita tecnologia, muitas formações, SAPO Labs, Summerbits, Codebits e muitos outros eventos.

 

Parabéns, SAPO!

 

A segunda edição do Summerbits acaba de arrancar.

 

A página desta iniciativa, com a qual o SAPO irá financiar até um máximo de 10 projectos com bolsas de 2,500 euros, contém toda a informação relativa a candidaturas, calendário, projectos e pagamentos.

 

Se és estudante, tens gosto pelo software livre e interesse em desenvolver um projecto durante o Verão e receber dinheiro por isso, esta é a tua oportunidade.

 

As candidaturas estão abertas até dia 27 de Julho.

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.

 

Integração do Blog de Dev...

SAPO Developer Network v2...

"TM Forum Service Deliver...

Geek Room

Verão e t-shirts

Spacebits

1 de Abril no SAPO

Uma semana nas mailing li...

SAPO Fotos em 2009

SAPO Developer Network, v...

Janeiro 2012

Dezembro 2011

Outubro 2011

Setembro 2011

Agosto 2011

Julho 2011

Junho 2011

Maio 2011

Abril 2011

Março 2011

Janeiro 2011

Outubro 2010

Setembro 2010

Agosto 2010

Julho 2010

Junho 2010

Maio 2010

Abril 2010

Março 2010

Fevereiro 2010

Janeiro 2010

Dezembro 2009

Novembro 2009

Outubro 2009

Setembro 2009

Agosto 2009

Julho 2009

Junho 2009

Maio 2009

Abril 2009

Março 2009

Fevereiro 2009

todas as tags