Oefenen voor programmeertests in Codility-stijl

Hoe de echte test er meestal uitziet

Er bestaat niet één Codility-test. Codility is een platform: elke werkgever kiest de opdrachten, de toegestane programmeertalen en de tijdslimiet voor de test. De uitnodiging van de werkgever geeft je de beste aanwijzing over jouw test.

Wat Codility zelf beschrijft. Codility zegt dat elke opdracht automatisch wordt beoordeeld aan de hand van vaste criteria (Codility). De gratis lessen voor programmeurs (Codility) laten zien hoe de opdrachten eruitzien: een kort probleem, een functie die je moet schrijven en opgegeven invoerlimieten. Zo vraagt de BinaryGap-les bijvoorbeeld om "an efficient algorithm" voor invoerwaarden tot 2,147,483,647 (Codility). Een andere les heet Time Complexity (Codility).

Wat er vaak over Codility-tests wordt gemeld (door kandidaten en in handleidingen, maar niet bevestigd op een Codility-pagina die we konden laden):

• Een paar opdrachten met één timer voor de hele test, vaak met een tijdslimiet tussen 30 minuten en 2 uur.
• Verborgen tests op correctheid: je code wordt getest met gevallen die je niet ziet, naast het voorbeeld in de opdracht.
• Prestaties bij grote invoer voor algoritmische opdrachten: een juiste maar trage oplossing kan punten kosten.
• De tijd die je nodig hebt binnen de tijdslimiet telt niet mee voor de score.

Wat onze oefentoetsen bevatten. Elke volledige oefentoets bestaat uit drie programmeeropdrachten in 90 minuten, van een eenvoudigere tot een moeilijkere opdracht. Je schrijft en voert een oplossing uit in Python, JavaScript, Java of C++. Die wordt getest met verborgen testgevallen, en je krijgt punten voor elk geval dat je doorstaat. Een laptop wordt aanbevolen. Je kunt teruggaan en een oplossing aanpassen totdat je deze indient.

Wat onze oefentoetsen anders doen. Volgens veel meldingen worden echte Codility-opdrachten gecontroleerd op correctheid en, bij veel opdrachten, op prestaties bij grote invoer. Onze verborgen testgevallen zijn klein en controleren de correctheid en randgevallen. Een trage oplossing loopt dus niet vast door een time-out. In de uitleg bij elke opdracht staat welke complexiteit nodig zou zijn bij grote invoer. De 10 gratis vragen zijn meerkeuzevragen over correctheid, complexiteit, randgevallen en snelheid: de kennis die je nodig hebt om voor die controles te slagen.

Vraagtypen met uitgewerkte voorbeelden

Een uitgewerkt voorbeeld per vraagtype, met de valkuil waar de meeste mensen intrappen.

1. Welke oplossing is correct. Opdracht: geef het aantal unieke waarden in een lijst terug. Oplossing: len(set(A)). Deze is correct voor elke lijst, ook voor een lege lijst, waarvoor het antwoord 0 is. Valkuil: zelf een lus schrijven met een gesorteerde lijst en het eerste of laatste item vergeten. Als een ingebouwde functie de klus klaart, controleer dan of die ook de randgevallen aankan en gebruik die functie.

2. Tijdscomplexiteit. Een oplossing doorloopt A en roept in de lus max(A[:i]) aan. De slice en max bekijken elk maximaal i items. Het totaal is dus ongeveer N in het kwadraat gedeeld door 2 stappen, oftewel O(N in het kwadraat). Als je in plaats daarvan het lopende maximum bijhoudt, wordt het O(N). Valkuil: één lus zien en de complexiteit O(N) noemen. Kijk in de lus ook naar slices, sommen, aantallen en zoekopdrachten.

3. Welke invoer laat het misgaan. Opdracht: geef het kleinste positieve gehele getal terug dat niet in A staat. Een oplossing geeft max(A) + 1 terug. Probeer A = [1, 2, 3]: de uitkomst is 4, en dat klopt. Probeer A = [1, 3]: de uitkomst is 4, maar 2 ontbreekt, dus het antwoord is 2. Probeer A = [-3, -1]: de uitkomst is 0, maar het antwoord is 1. Valkuil: stoppen na één geval waarin het werkt. Maak bewust een lijst met randgevallen: gaten, alleen negatieve getallen, leeg als dat mag, één item, alleen gelijke waarden en de maximaal toegestane waarden.

4. Snel genoeg voor N tot 100,000. Streef als vuistregel bij die grootte naar O(N) of O(N log N). O(N in het kwadraat) betekent ongeveer 10 billion stappen, veel meer dan binnen een gebruikelijke tijdslimiet past. Valkuil: testen met tien items, waarbij elke aanpak direct lijkt. Bedenk hoe het werk toeneemt als N groter wordt.

5. De grenzen lezen. Als waarden maximaal 1,000,000,000 kunnen zijn en N 100,000 is, kan een som oplopen tot 100 trillion. De gehele getallen van Python kunnen dat aan, maar in talen met gehele getallen van een vaste grootte zou er een overflow optreden. Valkuil: het waardebereik negeren. Het vertelt je iets over overflow en over welke trucs, zoals een telarray, mogelijk zijn.

Hoe je je voorbereidt

1. Lees eerst de uitnodiging. Noteer het aantal opdrachten, de totale tijd en de toegestane programmeertalen. Werkgevers bepalen dit, dus ga er niet zomaar van uit.
2. Gebruik één taal die je goed kent. Zorg dat je de lijsten, dictionaries, sets, sorteermethoden en stringmethoden ervan kent zonder iets op te hoeven zoeken.
3. Lees de limieten voordat je code schrijft. De invoergroottes en waardebereiken in een opdracht vertellen je hoe snel de oplossing moet zijn en welke randgevallen belangrijk zijn. Dat zie je ook in de eigen lessen van Codility (Codility).
4. Zorg eerst dat je oplossing klopt en maak die daarna snel. Schrijf eerst een eenvoudige, juiste versie. Als die O(N squared) is en N tot 100,000 kan oplopen, zoek dan naar een lopende totaaltelling, een dictionary, een set of een sorteermethode om de complexiteit te verlagen.
5. Test zelf de randgevallen. Het voorbeeld in een opdracht is maar één geval. Probeer lege invoer als dat is toegestaan, één item, waarden die allemaal gelijk zijn, negatieve waarden, de kleinste en grootste waarden en de grootste N.
6. Leer veelgebruikte patronen. Prefix sums, sliding windows, tellen met een dictionary, twee pointers, eerst sorteren en eenvoudige greedy-keuzes komen voor in een groot deel van de korte algoritmeopdrachten. De gratis lessen van Codility zijn een goede plek om te zien hoe zulke opdrachten eruitzien (Codility).
7. Schrijf complete oplossingen binnen de tijd. In onze volledige oefentoetsen schrijf en voer je code uit met verborgen testgevallen. Oefen hetzelfde met opdrachten die je zelf kiest, zodat schrijven onder tijdsdruk vertrouwd voelt.
8. Oefen op het tempo van de echte test. Maak volledige oefentoetsen met een timer, zodat het op de dag zelf vertrouwd voelt om drie opdrachten binnen één tijdslimiet te maken.

Hoe de beoordeling meestal werkt

De beoordeling wordt door elke werkgever ingesteld. Codility zegt dat elke opdracht automatisch wordt beoordeeld aan de hand van vaste criteria (Codility), en elke werkgever bepaalt welk resultaat goed genoeg is. Er is geen universele slaaggrens.

Volgens veel meldingen werkt die beoordeling als volgt: de score voor een opdracht is gebaseerd op verborgen tests voor juistheid en, bij veel algoritmische opdrachten, prestatietests met grote invoer. Die scores worden gecombineerd tot een percentage voor de opdracht en vervolgens voor de test. Een oplossing die goed werkt met kleine invoer, maar te langzaam is met grote invoer, kan punten voor prestaties verliezen. Een oplossing die faalt op een randgeval verliest een deel van de score voor juistheid. Daarom vragen de vragen in onze oefentoetsen steeds afzonderlijk: "Is het juist?" en "Is het snel genoeg?".

Onze oefenscore is het aantal van onze eigen vragen dat je juist hebt beantwoord, uitgesplitst per opdracht, zodat je ziet waar je je op kunt richten. Het is een oefenscore: geen Codility-score of resultaat van een werkgever, en de score voorspelt niet of je zult slagen.

Veelgemaakte fouten

• Het voorbeeld vertrouwen. Het voorbeeld bij een opdracht is één geval tussen veel verborgen gevallen. Je oplossing kan daarvoor slagen en toch het grootste deel van de punten mislopen.
• N negeren. Een juiste oplossing met O(N squared) kan de prestatietests niet doorstaan bij N = 100,000. Controleer eerst de limieten.
• Verborgen werk in een lus. Een slice, som, telling, index of "in" op een lijst binnen een lus vermenigvuldigt de werklast.
• Het laatste item missen. Off-by-one-bereiken en lussen die eindigen aan het einde van de lijst zijn klassieke fouten. Loop de laatste stap met de hand na.
• Verkeerde beginwaarden. Een maximum laten beginnen bij 0 of een minimum bij een verzonnen groot getal gaat mis bij negatieve of heel grote waarden. Begin bij het eerste item.
• De volgorde wijzigen waar de opdracht van afhankelijk is. Sorteren is handig, maar niet als het antwoord afhangt van posities of van het 'eerste item in de lijst'.
• Alle tijd aan één taak besteden. Dien voor elke taak eerst een correcte versie in en verbeter daarna de snelheid als je tijd over hebt.