Competições de programação: Google, IBM e FISL

A alguns anos atrás fiz uma entrevista em uma grande empresa de Java, uma dessas com 3 letras, e a primeira frase que o entrevistador me dirigiu ao ver meu curriculum foi um sonoro:

Essas competições de programação não dizem nada!

Essas competições não dizem se o programador é um bom engenheiro de software ou profundo conhecedor de alguma tecnolgoia, é verdade. Nem é essa a intenção.
As questões dessas provas apresentam problemas mais complexos que o comumente exigido no mercado de TI, e não foca tanto na parte de desenvolvimento, mas mais na capacidade de encontrar soluções. Para um cientista da computação (ou um matemático, no meu caso), essa capacidade é mais importante do que o próprio desenvolvimento e codificação. Vou relatar aqui três competições as quais tiver a oportunidade de participar este ano. Em todas as três, grandes empresas como o Google e IBM, sempre estavam a caça de talentos. Pode-se dizer que um bom resultado nessas competições certamente atrairão diversas propostas de emprego, mestrado e doutorado.

Primeiro veio o Google Code Jam Latin America. Os problemas tinham o mesmo nível das competições internacionais, mas com menos fases. Na última etapa, em Belo Horizonte, tive a chance de encontrar alguns conhecidos e fazer novas amizades no meio dos 50 finalistas, dentre elas Jelani Nelson, aluno de PhD e técnico do MIT, participando pela Virgin Islands; Vinicius Fortuna ex-competidor e agora engenheiro de software do Google em Nova Iorque, que veio entrevistar os competidores; Wanderley Guimarães, atual técnico do IME-USP, além de já conhecidos e excelentes competidores do ITA e PUC-RIO. Pelo vídeo promocional, da para você ter uma idéia do quão a sério o Google leva essas competições:

Depois teve a final mundial da ACM (ACM-ICPC) em Tokyo, Japão, onde fui representando o time do IME-USP, depois da qualificação pela Maratona de Programação brasileira. Lá contamos com a presença de diversos nomes interessantes, como o criador do Ruby, Yukihiro Matsumoto, que palestrou sobre sua linguagem de programação. Entre seus comentários oportunos, disse que eficácia não é a grande preocupação de Ruby; 80% do design de uma linguagem está feito se o nome for curto, pequeno e bonito (Ruby). Outra frase dele foi “Web 2.0, o que é isso?”. Modesto.

Também estava presente Stuart Feldman que, além de presidente da ACM e criador do primeiro compilador de Fotran 77, fez parte do grupo que criou o Unix e o make. Yuhichi Nakamura, criador do Xerces (xml4j), e diretor do IBM Tokyo Research Lab estava ajudando na coordenação do evento.

Nessa competição, mais de seis mil equipes participaram do evento nas competições regionais, de mais de 1700 universidades diferentes do mundo inteiro. A competição foi emocionante, com os quatro times brasileiros bem colocados. Além disso, dois times brasileiros resolveram 4 problemas, um marco na história da competição, onde o problema mais simples envolvia um algoritmo do tipo Longest Common Subsequence. Esse é um algoritmo muito usado em inúmeros lugares, como em biologia computacional para verificar padrões de sequencias de DNA. No fim das contas, os problemas dessas competições não são tão irreais assim! Alguns problemas são muito difíceis, sendo que nenhuma equipe do mundo conseguiu resolver. Você pode ver a prova da competição aqui.

O evento aconteceu no Hilton Tokyo Bay, um hotel dentro da Disney de Tokyo e muito bonito. Os quartos tinham vista para o monte Fuji e foi possível conhecer um pouco do país e de sua história.

07-DH_CON-_D4V0186[LO] 07-DH_TP-_MG_0281
07-DH_CON-_D4V0178[LO] 07-DH_CON2-_D4V0240[LO]

O Fórum Internacional de Software Livre preparou esse ano uma competição diferente, a Arena de programação, composta por duas fases. Para poder se inscrever, era necessário resolver um problema de lógica no próprio site, no estilo python-challenge, mas bem mais simples. A idéia era encontrar o caminho para a inscrição usando de seus dotes “hackers”. O Dorneles postou a descrição de como se inscrever em detalhes.

Chegando no evento, pronto para a primeira fase, a Arena era um cercado de vidro, quase um aquário, onde os animais eram os programadores.

A primeira fase terminou com alguns conhecidos entre os top. O Hugo Corbucci, colega de viagem ao fisl pelo IME-USP, o Klaus Wustefeld e o Kalecser Kurtz, o Dornelles Tremea e eu nos qualificamos entre os top 12. A segunda fase começou no dia seguinte e era composta por, supostamente, 24 horas de programação non-stop. Os 12 primeiros da fase anterior foram divididos em quatro grupos de três competidores. Na minha equipe? Kalecser, expert em Java e Dornelles, expert em Python e linux em geral. A tarefa? Resolver quatro bugs ou feature requests do Debian. Isso mesmo. Eles deram quatro códigos de bugs que estão ocorrendo em pacotes do Debian ou que feature requests que os usuários postaram e pediram para as equipes resolverem. Excelente proposta!

O primeiro bug envolvia um problema com o teclado. Você que é fã incondicional do Debian pode alternar para o tty1 (Ctrl+alt+F1), ativar o CAPS LOCK e tentar digitar “ABCD”… se o resultado for “ABcD”, você reproduziu o bug – que só funciona com alguns layouts de teclado. Encontramos muitas informações sobre o assunto e não conseguimos resolvê-lo, fomos capazes de encontrar textos indicando que o problema era mais delicado. Tudo isso após passar por muito código fonte em bash, perl etc. O segundo bug estava no pacote cdebconf, que é responsável pelo processo de configuração de pacotes debian durante o processo de instalação dos mesmos. Após correr por diversos arquivos feitos em C, com um “quê” de orientação a objeto, fomos capazes de isolar o bug e corrigi-lo, e o patch deve se tornar disponível em breve.

O terceiro bug envolve o bugtracking do debian, que não apresentava os dados da maneira que era requisitado, enquanto o último problema estava ligado ao particionador, que encontrava problemas durante o redimensionamento em determinados casos. Muito código perl apareceu enquanto solucionávamos o terceiro bug, mas não houve tempo suficiente para sequer olhar com calma o último. No dia seguinte, a segunda parte dessa fase envolveu o desenvolvimento do zero de um programa para facilitar a internacionalização dos pacotes debian. Nosso objetivo era utilizar o Lucene para fazer o partial matching de palavras ou frases já traduzidas anteriormente em outros pacotes, mas devido ao padrão de i18n adotado pelo debian, o Java acabou segurando um pouco o desenvolvimento, mas ainda fomos capazes de mostrar algo funcional com uma implementação do Edit Distance para procurar palavras similares.

O resultado de tudo isso saiu no final do dia, durante o fechamento do evento, nossa equipe ficou em primeiro lugar! O que ganhei com tudo isso? Conheci novas pessoas que trabalham com projetos open source de áreas diferentes de Java, coloquei em prática o meu conhecimento de C que só usava na teoria, e ajudei com um projeto que jamais sonhei ser possível ajudar. Claro, o notebook que deram para cada um de nossa equipe também conta! Fui entrevistado a respeito dessa competição. Espero encontrar vocês nas próximas!

22 Comentários

  1. Galmeida 20/04/2007 at 06:11 #

    Gui, o Julian me falou sobre essa competição, parabéns. Pena que não pude ir

  2. Phillip Calcado Shoes 20/04/2007 at 08:37 #

    Grande relato! Eh dificil achar no Brasil pessoas que nao vivam ou no extremo da teoria ou no da gambiarra, parabens por ser um dos poucos que mostra que esse pais tem programadores e nao apertadores de parafusos.

  3. lambari 20/04/2007 at 11:12 #

    qual a configuração do notebook?

  4. Tiago Porangaba 20/04/2007 at 13:12 #

    “Essas competições de programação não dizem nada!”

    essa frase me soou mais como inveja do entrevistador hein!

    como a competição tem como propósito avaliar a capacidade de resolver problemas computacionais num curto espaço de tempo e a sua equipe chegou às finais mundiais na competição, é óbvio que esse fato diz alguma coisa, ou seja, que você e a sua equipe muito provavelmente são bons no propósito da competição: a solução de problemas computacionais, oras.

    Aliás, parabéns pra você pelas conquistas e por representar nosso país!

  5. Giovane Kuhn 20/04/2007 at 18:03 #

    Belo relato, não sei quando as empresas (há exceções) vão abrir os olhos para pessoas que realmente sabem solucionar problemas !!!

    Sejam eles programadores de maratona, mestrandos e doutorandos. É muito conhecimento e potencialidade, para pouco reconhecimento, é triste !!

    Parabéns pelo notebook, achei que este prêmio fosse uma lenda, mas realmente aconteceu !!! heheh

  6. Guilherme Silveira 22/04/2007 at 19:58 #

    Obrigado pelos comentários… ainda não sabemos qual vai ser o notebook, estamos aguardando a chegada deles.

    Sobre as empresas, hoje em dia o mercado possui algumas empresas que se preocupam muito com qualidade e boas equipes, e essas ainda correm atrás de alguns programadores que saem de maratonas. Não que todos sejam bons programadores, pois podem não ter o conjunto de habilidades necessários para enfrentar o desenvolvimento de um projeto.

    Abraço

  7. ASOBrasil 23/04/2007 at 06:42 #

    Essa parte do texto (“Essas competições de programação não dizem nada!”) realmente chama a atenção! Pensei a mesma coisa que o Tiago Porangaba postou: “inveja”!

    Pelos prêmios e conquistas, Parabéns! Quando eu crescer, quero programar tão bem quando você! (rs)

  8. Paulo Silveira 23/04/2007 at 09:57 #

    Sobre a pessoa que fez o comenrário “Essas competições de programação não dizem nada!“, realmente não foi inveja. É uma pessoa de cargo alto, nivel academico e nivel tecnico. É apenas uma outra opinião, que é valida em algumas circunstâncias….

  9. Guilherme Silveira 23/04/2007 at 10:09 #

    Alias, era impressionante o conhecimento da pessoa que fez a entrevista… fiquei extremamente empolgado da possibilidade de trabalhar com ele. Infelizmente não deu certo, mas o cara era bom demais, mas como o Paulo disse, com opiniões diferentes.

  10. Fernando Boaglio 24/04/2007 at 08:08 #

    Parabéns Gui, espero que quando tiver tempo comente por aqui algum desafio interessante que enfrentou nas maratonas.

  11. André Barbosa 24/04/2007 at 11:11 #

    Rapaz… você não é deste mundo! Mas é bom ter pessoas de outro mundo por perto, bom se tivessem mais. Parabens pelo relato!

  12. Ironlynx 24/04/2007 at 15:50 #

    Meus Parabéns!!!Muito bom mesmo…
    Já disseram acima: Guilherme quando eu crescer eu quero programar igual a vc.
    Existe um “gabarito” oficial dessa prova da competição?

  13. Luca Bastos 24/04/2007 at 22:47 #

    Parabéns!

    Uma curiosidade: em alguma das competições que você participou foi proposto resolver o problema do jantar dos filósofos?

    Costumam cair problemas clássicos nestas competições?

  14. Guilherme Silveira 25/04/2007 at 09:03 #

    Obrigado denovo pessoal. Luca, os problemas não são de concorrência, não envolvem questões como thread.
    Daniel, tem sim gabarito.. dá uma olhada no maratona.ime.usp.br e no proprio site do fisl.

    Boaglio, um exemplo de problema (o mais simples, claro) foi de somar doze números e dizer a média, arredondando o valor na segunda casa decimal, esse foi do fisl.

    Um exemplo mais fácil do mundial (que é razoavelmente dificil de perceber, mas facil de implementar) é o seguinte: cargas chegam no porto no começo do dia. Elas estão com os nomes dos navios que elas tem que ser colocadas, por exmeplo: chega a carga A, C, B, A. A medida que as cargas chegam, você deve empilhá-las em quantas pilhas desejar, sempre colocando cargas recem chegadas em cima, exemplo:
    uma pilha fica com A (no topo)
    outra pilha fica com C, B, A (no topo)

    apos empilhar tudo, chegam os navios, sempre em ordem alfabetica. voce SO pode retirar caixas de cima das pilhas (a mesma restricao de antes do guindaste). qual o menor numero de pilhas (espaco) que vc pode montar? no meu exemplo, se as caixas vem em A, C, B, A, é dois.

    detalhe: se eu tentasse empilhar:
    uma pilha fica com A, C, B, A (no topo)
    quando chegasse o navio A eu nao conseguiria colocar tudo nele.. portanto nao eh uma solucao valida… o minimo é mesmo duas pilhas.

    note que quando o navio A, por exemplo, é carregado ele vai embora e nunca mais volta, não te da a chance de terminar o carregamento depois.

    no exemplo A, B, C, D, B, D, B, A é quatro. pq?

  15. Ricardo Nakamura 25/04/2007 at 21:39 #

    Realmente esse seu relato é impressionante.
    Parabéns Guilherme.

  16. Fernando Boaglio 30/04/2007 at 07:45 #

    Se eu entendi direito o número mínimo de pilhas é sempre igual ao menor ao número de diferentes letras que aparecerem.
    No segundo exemplo q vc deu que são quatro pilhas, se a carga “C” viesse por último, o mínimo seriam três pilhas.

  17. Guilherme Silveira 30/04/2007 at 09:58 #

    Sim sim…

  18. Antonio Kantek 30/04/2007 at 14:22 #

    Olah Guilherme,

    Parabens pela maratona. Olha soh, voces da Caelum podiam abrir um curso
    preparatorio para maratonas. Afinal, um monte de gente gostaria de aprender
    mais sobre esse tema. O que acontece eh que chegar onde voce chegou nao eh facil.
    Jah pensou que legal um curso que ensinasse essas paradas de programacao dinamica,
    grafo, estrutura de dados avancadas..Alias esse curso poderia ser dividido em uns
    3 ou 4 modulos (ou ateh mais). Acho que um monte de gente iria se interessar…

  19. Kimie Nakahara 01/05/2007 at 05:48 #

    Ola Guilherme!

    Parabens pelo FISL e principalmente, pela ACM: competindo com quase 1800 equipes de mais de 80 paises, vcs (e o pessoal da PUC-Rio) representaram *muito* bem o Brasil. Muito legal!!

    Aproveito p dizer q sou fa do blog da Caelum, o nivel dos posts e excepcional.

    tudo de bom! 🙂

  20. Camilo Lopes - LpJava 19/05/2007 at 09:31 #

    ae guilherme!! parabens mesmo cara, seu blog ta em favoritos..fico feliz pela sua vitoria…. essa ideia que tem de que somente quem eh de fora que é bom.. vc quebrou isso… parabens mesmo…um dia que tiver coragem participo de uma maratona dessas.. nao como a google, tem q ter muita bala na agulha… so para vc e companhia abração 😀

  21. Tiago 01/11/2007 at 11:47 #

    Qual eh essa linguagem sibel…silbel…qual eh a palavra certa????

Deixe uma resposta