Prática para teste de programação no estilo Codility

Como costuma ser o teste real

Não existe um único teste da Codility. A Codility é uma plataforma: cada empregador escolhe as tarefas, as linguagens permitidas e o limite de tempo do teste. O convite do empregador é a melhor referência para saber como será o seu.

O que a Codility descreve. A Codility diz que cada tarefa é avaliada automaticamente com base em critérios definidos (Codility). As aulas gratuitas para programadores (Codility) mostram o formato das tarefas: um problema curto, uma função para escrever e limites de entrada especificados. Por exemplo, a tarefa da aula BinaryGap pede "an efficient algorithm" para entradas de até 2,147,483,647 (Codility), e uma das aulas se chama Time Complexity (Codility).

O que costuma ser relatado sobre os testes da Codility (por candidatos e guias, não confirmado em uma página da Codility que conseguimos acessar):

• Algumas tarefas com um único cronômetro para o teste inteiro, geralmente entre 30 minutos e 2 horas.
• Testes ocultos de correção: seu código é verificado em casos que você não consegue ver, além do exemplo incluído na tarefa.
• Desempenho com entradas grandes em tarefas de algoritmos: uma solução correta, mas lenta, pode perder pontos.
• O tempo que você leva dentro do limite não faz parte da pontuação.

O que nossos simulados incluem. Cada simulado completo tem três tarefas de programação em 90 minutos, começando por uma tarefa mais fácil e chegando a uma mais difícil. Você escreve e executa uma solução em Python, JavaScript, Java ou C++, que é verificada em casos de teste ocultos. Você recebe crédito por cada caso aprovado. Recomendamos usar um laptop. Você pode voltar e alterar uma solução até enviá-la.

O que nossos simulados fazem de diferente. Costuma-se relatar que as tarefas reais da Codility são verificadas quanto à correção e, em muitas tarefas, ao desempenho com entradas grandes. Nossos casos ocultos são pequenos e verificam a correção e os casos extremos, então uma solução lenta não excede o tempo; a explicação de cada tarefa indica a complexidade necessária para uma entrada grande. As 10 questões gratuitas são de múltipla escolha sobre correção, complexidade, casos extremos e velocidade: os conceitos por trás de passar nessas verificações.

Tipos de questão com exemplos resolvidos

Um exemplo resolvido de cada tipo de questão, com a armadilha em que a maioria cai.

1. Qual solução está correta. Tarefa: retornar o número de valores distintos em uma lista. Solução: len(set(A)). Ela está correta para qualquer lista, inclusive uma lista vazia, que retorna 0. Armadilha: criar seu próprio loop com uma lista ordenada e esquecer o primeiro ou o último item. Quando uma função integrada resolve o problema, confira se ela lida com os casos extremos e use-a.

2. Complexidade de tempo. Uma solução percorre A e, dentro do loop, chama max(A[:i]). O fatiamento e max acessam até i itens cada, então o total é de cerca de N ao quadrado dividido por 2 etapas, ou O(N ao quadrado). Manter o maior valor encontrado até então reduz a complexidade para O(N). Armadilha: ver um loop e dizer que é O(N). Procure fatiamentos, somas, contagens e buscas dentro dele.

3. Qual entrada causa uma falha. Tarefa: retornar o menor inteiro positivo que não está em A. Uma solução retorna max(A) + 1. Experimente A = [1, 2, 3]: ela retorna 4, que está correto. Experimente A = [1, 3]: ela retorna 4, mas 2 está faltando, então a resposta é 2. Experimente A = [-3, -1]: ela retorna 0, mas a resposta é 1. Armadilha: parar depois de encontrar um caso em que a solução funciona. Liste de propósito os casos extremos: lacunas, todos os valores negativos, lista vazia se permitida, um item, todos iguais e os maiores valores permitidos.

4. Rápida o bastante para N de até 100,000. Como regra geral, para esse tamanho, prefira O(N) ou O(N log N). O(N ao quadrado) significa cerca de 10 bilhões de etapas, muito além de um limite de tempo típico. Armadilha: testar com dez itens, quando qualquer abordagem parece instantânea. Pense em como o trabalho aumenta à medida que N cresce.

5. Como ler os limites. Se os valores podem chegar a 1,000,000,000 e N é 100,000, a soma pode chegar a 100 trilhões. Os inteiros do Python dão conta desse valor, mas em linguagens com inteiros de tamanho fixo ocorreria um estouro. Armadilha: ignorar o intervalo dos valores. Ele indica a possibilidade de estouro e quais técnicas podem ser usadas, como um array de contagem.

Como se preparar

1. Leia primeiro o convite. Anote o número de tarefas, o tempo total e as linguagens permitidas. Quem define isso é o empregador, então não presuma.
2. Use uma linguagem que você conheça bem. Conheça suas listas, dicionários, conjuntos, métodos de ordenação e de strings sem precisar consultar.
3. Leia os limites antes de programar. Os tamanhos de entrada e os intervalos de valores informados na tarefa mostram a velocidade necessária para a solução e quais casos extremos importam, como nas próprias tarefas das aulas da Codility (Codility).
4. Primeiro, acerte; depois, otimize. Comece escrevendo uma versão simples e correta. Se ela for O(N ao quadrado) e N puder chegar a 100,000, procure usar um total acumulado, um dicionário, um conjunto ou ordenação para reduzir a complexidade.
5. Teste você mesmo os casos extremos. O exemplo de uma tarefa é apenas um caso. Se for permitido, teste uma entrada vazia, um único item, todos os valores iguais, valores negativos, os valores mínimo e máximo e o maior N.
6. Aprenda os padrões mais comuns. Somas de prefixo, janelas deslizantes, contagem com um dicionário, dois ponteiros, ordenação inicial e escolhas gulosas simples aparecem em muitas tarefas curtas de algoritmos. As aulas gratuitas da Codility são um bom lugar para conhecer o formato (Codility).
7. Escreva soluções completas com tempo cronometrado. Nos nossos simulados completos, você escreve e executa código com casos ocultos. Faça o mesmo com tarefas próprias para se acostumar a programar com tempo limitado.
8. Pratique no ritmo real. Faça simulados completos e cronometrados para se acostumar a resolver três tarefas com um único cronômetro antes do dia do teste.

Como a pontuação costuma funcionar

A pontuação é definida por cada empregador. A Codility informa que cada tarefa é pontuada automaticamente com base em critérios fixos (Codility), e cada empregador decide qual resultado é bom o suficiente. Não existe uma nota de corte universal.

Relatos comuns sobre como esses critérios funcionam: a pontuação de uma tarefa vem de testes ocultos de correção e, em muitas tarefas algorítmicas, de testes de desempenho com entradas grandes. Esses resultados são combinados em uma porcentagem para a tarefa e, depois, para o teste. Uma solução correta para entradas pequenas, mas lenta demais para entradas grandes, pode perder pontos de desempenho. Já uma solução que falha em um caso extremo perde parte da pontuação de correção. Por isso, as perguntas dos nossos simulados continuam perguntando separadamente: "Está correto?" e "É rápido o suficiente?".

Nossa pontuação de prática é o número de questões próprias que você acertou, com um detalhamento por tarefa para que você veja onde precisa se concentrar. É uma pontuação de prática: não é uma pontuação da Codility nem o resultado de qualquer empregador, e não prevê se você será aprovado.

Erros comuns

• Confiar no exemplo. O exemplo de uma tarefa é apenas um entre muitos casos ocultos. Uma solução pode passar nele e ainda assim perder a maior parte da pontuação.
• Ignorar N. Uma solução correta de complexidade O(N squared) pode falhar nos testes de desempenho quando N = 100,000. Confira os limites primeiro.
• Fazer operações ocultas dentro de um loop. Uma fatia, soma, contagem, busca de índice ou operação "in" em uma lista dentro de um loop multiplica o custo.
• Não incluir o último item. Errar os limites em intervalos e terminar a execução no fim da lista são falhas comuns. Acompanhe à mão a última etapa.
• Usar valores iniciais errados. Começar o máximo em 0 ou o mínimo em um número grande inventado dá errado com números negativos ou muito grandes. Comece pelo primeiro item.
• Alterar a ordem da qual a tarefa depende. Ordenar é uma ótima ferramenta, mas não quando a resposta depende das posições ou do "primeiro da lista".
• Passar todo o tempo em uma tarefa. Envie uma versão correta de cada tarefa e depois melhore a velocidade, se sobrar tempo.