Esercitazioni per test di programmazione in stile Codility

Com'è di solito il test vero

Non esiste un unico test Codility. Codility è una piattaforma: ogni datore di lavoro sceglie gli esercizi, i linguaggi ammessi e il limite di tempo del test. L'invito del datore di lavoro è il riferimento più affidabile per sapere cosa aspettarsi.

Cosa descrive Codility. Codility afferma che ogni esercizio viene valutato automaticamente in base a criteri prestabiliti (Codility). Le sue lezioni gratuite per programmatori (Codility) mostrano il formato degli esercizi: un problema breve, una funzione da scrivere e limiti di input specificati. Per esempio, l'esercizio della lezione BinaryGap richiede "an efficient algorithm" per input fino a 2,147,483,647 (Codility), e una lezione si intitola Time Complexity (Codility).

Cosa viene comunemente riferito sui test Codility (da candidati e guide, ma non confermato su una pagina Codility che siamo riusciti a consultare):

• Alcuni esercizi con un unico timer per l'intero test, spesso da 30 minuti a 2 ore.
• Test di correttezza nascosti: il codice viene verificato su casi che non è possibile vedere, oltre all'esempio nell'esercizio.
• Prestazioni con input di grandi dimensioni negli esercizi algoritmici: una soluzione corretta ma lenta può perdere punti.
• Il tempo impiegato entro il limite non fa parte del punteggio.

Cosa comprendono le nostre simulazioni. Ogni simulazione completa prevede tre esercizi di programmazione in 90 minuti, da uno più semplice a uno più difficile. Si scrive e si esegue una soluzione in Python, JavaScript, Java o C++, che viene verificata su casi di test nascosti e assegna punti per ogni caso superato. Si consiglia di usare un laptop. È possibile tornare indietro e modificare una soluzione fino all'invio.

In cosa sono diverse le nostre simulazioni. Secondo quanto viene comunemente riferito, gli esercizi reali di Codility vengono verificati per la correttezza e, in molti casi, per le prestazioni con input di grandi dimensioni. I nostri casi nascosti sono piccoli e verificano la correttezza e i casi limite, quindi una soluzione lenta non va in timeout; la spiegazione di ogni esercizio indica quale complessità servirebbe con un input di grandi dimensioni. Le 10 domande gratuite sono a scelta multipla e riguardano correttezza, complessità, casi limite e velocità: l'approccio necessario per superare queste verifiche.

Tipi di domande con esempi svolti

Un esempio svolto per ogni tipo di domanda, con l'errore in cui cade più spesso chi risponde.

1. Quale soluzione è corretta. Compito: restituire il numero di valori distinti in una lista. Soluzione: len(set(A)). È corretta per qualsiasi lista, anche se vuota, nel qual caso restituisce 0. Errore comune: scrivere un ciclo personalizzato con una lista ordinata e dimenticare il primo o l'ultimo elemento. Quando una funzione integrata risolve il problema, verifica che gestisca i casi limite e poi usala.

2. Complessità temporale. Una soluzione scorre A e, all'interno del ciclo, richiama max(A[:i]). Sia lo slicing sia max possono esaminare fino a i elementi, quindi il totale è circa N squared diviso 2 passaggi, cioè O(N squared). Mantenendo invece il massimo progressivo, la complessità diventa O(N). Errore comune: vedere un ciclo e concludere che la complessità è O(N). Controlla se al suo interno ci sono slicing, somme, conteggi o ricerche.

3. Quale input causa un errore. Compito: restituire il più piccolo intero positivo che non è presente in A. Una soluzione restituisce max(A) + 1. Prova A = [1, 2, 3]: restituisce 4, che è corretto. Prova A = [1, 3]: restituisce 4, ma manca 2, quindi la risposta è 2. Prova A = [-3, -1]: restituisce 0, ma la risposta è 1. Errore comune: fermarsi dopo aver trovato un caso che funziona. Elenca appositamente i casi limite: valori mancanti, solo valori negativi, lista vuota se consentita, un solo elemento, tutti i valori uguali e i valori massimi ammessi.

4. Abbastanza veloce per N fino a 100,000. Come regola generale, per questa dimensione punta a O(N) o O(N log N). O(N squared) significa circa 10 billion passaggi, molto oltre un limite di tempo tipico. Errore comune: provare con dieci elementi, quando ogni approccio sembra istantaneo. Chiediti come cresce il lavoro all'aumentare di N.

5. Interpretare i limiti. Se i valori possono arrivare a 1,000,000,000 e N è 100,000, la somma può arrivare a 100 trillion. Gli interi di Python possono gestirla, ma nei linguaggi con interi di dimensione fissa si verificherebbe un overflow. Errore comune: ignorare l'intervallo dei valori. È utile per capire se può verificarsi un overflow e quali tecniche, come un array di conteggio, sono possibili.

Come prepararsi

1. Leggi prima l'invito. Prendi nota del numero di esercizi, del tempo totale e dei linguaggi ammessi. Sono i datori di lavoro a stabilirli, quindi non fare supposizioni.
2. Scegli un linguaggio che conosci bene. Impara a usare liste, dizionari, set, ordinamento e metodi per le stringhe senza doverli cercare.
3. Leggi i limiti prima di scrivere il codice. Le dimensioni dell'input e gli intervalli dei valori indicati in un esercizio ti dicono quanto deve essere veloce la soluzione e quali casi limite sono importanti, come negli esercizi delle lezioni di Codility (Codility).
4. Prima la correttezza, poi la velocità. Scrivi prima una versione semplice e corretta. Se ha complessità O(N al quadrato) e N può arrivare a 100,000, prova a ridurla usando un totale progressivo, un dizionario, un set o l'ordinamento.
5. Verifica personalmente i casi limite. L'esempio di un esercizio è solo un caso. Prova un input vuoto, se consentito, un solo elemento, valori tutti uguali, valori negativi, il valore minimo e quello massimo e il valore massimo di N.
6. Impara gli schemi più comuni. Le somme prefisse, le finestre scorrevoli, il conteggio con un dizionario, i due puntatori, l'ordinamento iniziale e le semplici strategie greedy sono utili per molti esercizi algoritmici brevi. Le lezioni gratuite di Codility sono un buon modo per familiarizzare con il formato (Codility).
7. Scrivi soluzioni complete con un limite di tempo. Nelle nostre simulazioni complete si scrive e si esegue il codice su casi nascosti; esercitati allo stesso modo con esercizi tuoi, così scrivere entro un limite di tempo diventerà normale.
8. Allenati al ritmo del test. Svolgi simulazioni complete a tempo, così affrontare tre esercizi con un unico timer diventerà normale il giorno del test.

Come funziona di solito la valutazione

Il sistema di valutazione è stabilito da ogni datore di lavoro. Codility afferma che ogni esercizio viene valutato automaticamente secondo criteri prestabiliti (Codility) e che ogni datore di lavoro decide quale risultato sia sufficiente. Non esiste una soglia di superamento universale.

Secondo quanto viene comunemente riferito sul funzionamento di questi criteri, il punteggio di un esercizio deriva da test di correttezza nascosti e, per molti esercizi di algoritmi, da test delle prestazioni con input di grandi dimensioni. I risultati vengono combinati in una percentuale per l'esercizio e poi per il test. Una soluzione corretta con input piccoli ma troppo lenta con quelli grandi può perdere punti relativi alle prestazioni; una soluzione che non supera un caso limite perde parte del punteggio di correttezza. Ecco perché nelle nostre simulazioni le domande «È corretto?» e «È abbastanza veloce?» vengono poste separatamente.

Il nostro punteggio di esercitazione corrisponde al numero di nostre domande a cui hai risposto correttamente, con una suddivisione per esercizio, così puoi capire su cosa concentrarti. È un punteggio di esercitazione: non è un punteggio Codility né il risultato di un datore di lavoro, e non prevede se supererai il test.

Errori comuni

• Fidarsi dell'esempio. L'esempio di un'attività è solo uno dei tanti casi nascosti. Una soluzione può superarlo e comunque sbagliare la maggior parte dei test.
• Ignorare N. Una soluzione corretta con complessità O(N quadrato) può non superare i controlli delle prestazioni con N = 100,000. Controlla prima i limiti.
• Lavoro nascosto dentro un ciclo. Eseguire uno slice, una somma, un conteggio, una ricerca dell'indice o un controllo "in" su una lista all'interno di un ciclo moltiplica il costo.
• Dimenticare l'ultimo elemento. Gli intervalli con errore di uno e i cicli che terminano alla fine della lista sono una causa classica di errore. Segui a mano l'ultimo passaggio.
• Valori iniziali errati. Iniziare il massimo da 0 o il minimo da un numero molto grande inventato causa problemi con i numeri negativi o molto grandi. Parti dal primo elemento.
• Cambiare l'ordine da cui dipende l'attività. Ordinare è uno strumento utilissimo, ma non quando la risposta dipende dalle posizioni o dal «primo nell'elenco».
• Dedicarе tutto il tempo a una sola attività. Invia una versione corretta di ogni attività, poi migliora la velocità se hai tempo.