Entraînement aux tests de programmation de style Codility

À quoi ressemble généralement le test réel

Il n’existe pas de test Codility unique. Codility est une plateforme : chaque employeur choisit les tâches, les langages autorisés et la durée de son test. L’invitation de l’employeur est le meilleur guide pour savoir à quoi vous attendre.

Ce que Codility indique. Codility précise que chaque tâche est notée automatiquement selon des critères fixes (Codility). Ses leçons gratuites pour les programmeurs (Codility) donnent une idée du format des tâches : un court problème, une fonction à écrire et des limites d’entrée indiquées. Par exemple, la tâche de la leçon BinaryGap demande de concevoir « un algorithme efficace » pour des entrées allant jusqu’à 2,147,483,647 (Codility), et l’une des leçons s’intitule Time Complexity (Codility).

Ce qui est souvent rapporté au sujet des tests Codility (par des candidats et des guides, sans confirmation sur une page Codility que nous avons pu consulter) :

• Quelques tâches avec un seul chronomètre pour l’ensemble du test, souvent entre 30 minutes et 2 heures.
• Des tests de correction cachés : votre code est vérifié sur des cas que vous ne voyez pas, en plus de l’exemple fourni dans la tâche.
• Les performances sur de grandes entrées pour les tâches algorithmiques : une solution correcte, mais lente, peut perdre des points.
• Le temps que vous prenez dans la limite autorisée ne fait pas partie du score.

Ce que couvrent nos tests blancs. Chaque test blanc complet comprend trois tâches de programmation en 90 minutes, d’une tâche plus facile à une tâche plus difficile. Vous écrivez et exécutez une solution en Python, JavaScript, Java ou C++, qui est vérifiée sur des cas de test cachés. Vous obtenez des points pour chaque cas réussi. Un ordinateur portable est recommandé. Vous pouvez revenir sur une solution et la modifier jusqu’à ce que vous la soumettiez.

En quoi nos tests blancs sont différents. Selon les informations couramment rapportées, les tâches Codility réelles sont vérifiées pour leur correction et, pour beaucoup d’entre elles, pour leurs performances sur de grandes entrées. Nos cas cachés sont de petite taille et vérifient la correction et les cas limites. Une solution lente n’est donc pas interrompue par le chronomètre ; l’explication de chaque tâche indique la complexité nécessaire pour traiter une grande entrée. Les 10 questions gratuites sont des questions à choix multiples sur la correction, la complexité, les cas limites et la vitesse : elles portent sur le raisonnement nécessaire pour réussir ces vérifications.

Types de questions avec exemples corrigés

Un exemple résolu pour chaque type de question, avec le piège dans lequel tombent la plupart des gens.

1. Quelle solution est correcte ? Tâche : renvoyer le nombre de valeurs distinctes dans une liste. Solution : len(set(A)). Cette solution est correcte pour toutes les listes, y compris une liste vide, pour laquelle elle renvoie 0. Piège : écrire votre propre boucle avec une liste triée et oublier le premier ou le dernier élément. Si une fonction intégrée fait l’affaire, vérifiez qu’elle gère les cas limites, puis utilisez-la.

2. Complexité temporelle. Une solution parcourt A et appelle max(A[:i]) à l’intérieur de la boucle. Le découpage en tranches et max traitent chacun jusqu’à i éléments : le total représente environ N au carré divisé par 2 étapes, soit O(N au carré). En conservant plutôt le maximum au fil du parcours, on obtient O(N). Piège : voir une boucle et conclure que la complexité est O(N). Vérifiez si elle contient des découpages en tranches, des sommes, des comptages ou des recherches.

3. Quelle entrée la fait échouer ? Tâche : renvoyer le plus petit entier positif qui ne figure pas dans A. Une solution renvoie max(A) + 1. Essayez A = [1, 2, 3] : elle renvoie 4, ce qui est correct. Essayez A = [1, 3] : elle renvoie 4, mais 2 manque, donc la réponse est 2. Essayez A = [-3, -1] : elle renvoie 0, mais la réponse est 1. Piège : s’arrêter après avoir trouvé un cas qui fonctionne. Dressez volontairement la liste des cas limites : les valeurs manquantes, uniquement des valeurs négatives, une liste vide si elle est autorisée, un seul élément, des valeurs toutes égales et les valeurs maximales autorisées.

4. Assez rapide pour N jusqu’à 100,000. En règle générale, visez O(N) ou O(N log N) pour une telle taille. O(N au carré) représente environ 10 milliards d’étapes, ce qui dépasse largement une limite de temps habituelle. Piège : faire des essais avec dix éléments, pour lesquels toutes les méthodes semblent instantanées. Demandez-vous comment le travail augmente avec N.

5. Lire les limites. Si les valeurs peuvent atteindre 1,000,000,000 et que N est égal à 100,000, la somme peut atteindre 100 billions. Les entiers de Python peuvent gérer cette valeur, mais elle provoquerait un dépassement de capacité dans les langages qui utilisent des entiers de taille fixe. Piège : ignorer la plage de valeurs. Elle vous renseigne sur les risques de dépassement de capacité et sur les méthodes possibles, comme un tableau de comptage.

Comment vous préparer

1. Lisez d’abord votre invitation. Notez le nombre de tâches, la durée totale et les langages autorisés. Ce sont les employeurs qui les fixent, alors ne faites pas de suppositions.
2. Utilisez un langage que vous maîtrisez bien. Sachez utiliser ses listes, dictionnaires, ensembles, fonctions de tri et méthodes sur les chaînes de caractères sans avoir à les rechercher.
3. Lisez les limites avant de coder. La taille des entrées et les plages de valeurs indiquées dans une tâche vous renseignent sur la rapidité nécessaire de la solution et sur les cas limites à prendre en compte, comme dans les leçons de Codility (Codility).
4. Commencez par obtenir une solution correcte, puis rendez-la rapide. Écrivez d’abord une version simple et correcte. Si elle est en O(N squared) et que N peut atteindre 100,000, essayez d’utiliser un total cumulatif, un dictionnaire, un ensemble ou un tri pour réduire la complexité.
5. Testez vous-même les cas limites. L’exemple d’une tâche ne représente qu’un seul cas. Essayez une entrée vide si elle est autorisée, un seul élément, des valeurs toutes identiques, des valeurs négatives, les valeurs les plus petites et les plus grandes, ainsi que la valeur maximale de N.
6. Apprenez les schémas courants. Les sommes préfixes, les fenêtres glissantes, le comptage avec un dictionnaire, les deux pointeurs, le tri préalable et les stratégies gloutonnes simples couvrent une grande partie des tâches algorithmiques courtes. Les leçons gratuites de Codility sont un bon moyen de découvrir ce format (Codility).
7. Écrivez des solutions complètes en temps limité. Dans nos tests blancs complets, vous écrivez et exécutez du code qui est vérifié sur des cas cachés. Faites de même avec vos propres exercices pour vous habituer à écrire dans un temps limité.
8. Entraînez-vous au rythme du test. Faites des tests blancs complets chronométrés pour vous habituer à enchaîner trois tâches avec un seul chronomètre le jour du test.

Comment la notation fonctionne généralement

La notation est définie par chaque employeur. Codility indique que chaque tâche est notée automatiquement selon des critères fixes (Codility), et chaque employeur décide du résultat qu'il juge suffisant. Il n'existe pas de seuil de réussite universel.

D'après ce qui est généralement rapporté sur le fonctionnement de ces critères, la note d'une tâche est calculée à partir de tests de correction cachés et, pour de nombreuses tâches algorithmiques, de tests de performance sur de grandes entrées. Ces résultats sont combinés pour obtenir un pourcentage pour la tâche, puis pour le test. Une solution correcte pour de petites entrées, mais trop lente pour de grandes entrées, peut perdre des points de performance. Une solution qui échoue sur un cas limite perd une partie de ses points de correction. C'est pourquoi, dans nos examens blancs, les questions « Est-ce correct ? » et « Est-ce suffisamment rapide ? » sont posées séparément.

Notre score d'entraînement correspond au nombre de nos questions auxquelles vous avez correctement répondu. Il est détaillé par tâche pour vous aider à voir sur quoi vous concentrer. C'est un score d'entraînement : ce n'est ni un score Codility ni un résultat d'employeur, et il ne permet pas de prédire si vous réussirez.

Erreurs fréquentes

• Faire confiance à l'exemple. L'exemple d'une tâche n'est qu'un cas parmi de nombreux cas cachés. Une solution peut le réussir et pourtant échouer sur la plupart des points.
• Ignorer N. Une solution correcte en O(N au carré) peut échouer aux contrôles de performance lorsque N = 100,000. Vérifiez d'abord les limites.
• Effectuer des opérations coûteuses dans une boucle. Une slice, sum, count, index ou "in" appliqué à une liste à l'intérieur d'une boucle multiplie le coût.
• Oublier le dernier élément. Les erreurs de décalage d'indice et les parcours qui s'arrêtent à la fin de la liste sont des causes classiques d'échec. Vérifiez à la main la dernière étape.
• Choisir de mauvaises valeurs de départ. Initialiser un maximum à 0, ou un minimum à un grand nombre arbitraire, pose problème avec les nombres négatifs ou très grands. Partez du premier élément.
• Modifier l'ordre dont dépend la tâche. Le tri est très utile, mais pas lorsque la réponse dépend des positions ou du « premier élément de la liste ».
• Consacrer tout votre temps à une seule tâche. Soumettez d'abord une version correcte de chaque tâche, puis améliorez la vitesse si le temps le permet.