Domande da colloquio tech e sviluppo: enigmi di algoritmi risolti
Questi enigmi allenano a ridurre il numero di tentativi, a dividere lo spazio dei possibili e a scegliere un algoritmo in base al suo costo in tempo e in memoria. Ecco 4 enigmi classici con la soluzione spiegata.
Enigma delle due uova e dei 100 piani: la soluzione
Domanda di colloquio nel settore tech sulla ricerca di una soglia con un numero minimo di prove.
Hai due uova identiche e un palazzo di 100 piani. Esiste un piano critico oltre il quale un uovo lanciato si rompe; sotto di esso sopravvive e può essere riutilizzato. Qual è il numero minimo di lanci necessario, nel caso peggiore, per trovare questo piano critico?
Un indizio?
Se il primo uovo si rompe, devi testare i piani uno per uno con il secondo: scegli quindi dei gradini le cui distanze diminuiscono.
Mostra la risposta e la soluzione
Risposta: 14 lanci al minimo nel caso peggiore, lanciando il primo uovo a gradini le cui distanze diminuiscono da 14 a 1.
Il ragionamento
Per ogni lancio del primo uovo si accetta di dover percorrere, nel peggiore dei casi, l'intervallo che lo precede con il secondo uovo, un piano dopo l'altro. Si lancia il primo uovo ai piani 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 e poi 100, con distanze di 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4 e infine 1. Se il primo uovo si rompe a un gradino, il secondo testa i piani uno per uno a partire dal gradino precedente: nel peggiore dei casi servono k lanci per il k-esimo gradino, più la distanza meno uno, cioè 14 lanci in tutto e in ogni caso. Il numero n di lanci deve soddisfare n(n+1)/2 ≥ 100: per n = 13 si ottiene 91, insufficiente, e per n = 14 si ottiene 105, sufficiente. La risposta è quindi 14 lanci.
Trovare il numero mancante in un array: la soluzione dell'enigma
Domanda di colloquio per sviluppatori su algoritmi e complessità.
Un array contiene gli interi da 1 a n, tranne uno, e i suoi elementi sono in disordine. Conosci il valore di n, ma non il numero mancante né l'ordine degli elementi. Come trovare il numero mancante nel modo più efficiente possibile?
Un indizio?
Pensa a una proprietà aritmetica della sequenza degli interi da 1 a n che permetta di ritrovare l'elemento assente senza cercarlo.
Mostra la risposta e la soluzione
Risposta: Sottrai la somma degli elementi dell'array dalla somma attesa n(n+1)/2: la differenza è il numero mancante, con complessità O(n) di tempo e O(1) di memoria.
Il ragionamento
La somma degli interi da 1 a n vale n(n+1)/2, formula che basta calcolare una sola volta. Se si sommano tutti gli elementi presenti nell'array, manca esattamente il numero assente, quindi la somma reale è inferiore a quella attesa esattamente di quel numero. La differenza tra le due somme dà direttamente il valore cercato. Il calcolo scorre l'array una sola volta, quindi la complessità è O(n) nel tempo, e servono solo poche variabili, cioè O(1) di memoria aggiuntiva. Un altro metodo, altrettanto efficiente, consiste nell'eseguire l'OR esclusivo (XOR) di tutti i numeri presenti con quelli da 1 a n: il risultato è il numero mancante.
Indovinare un numero da 1 a 1000 con domande sì o no: la soluzione
Algoritmi: domanda sulla ricerca dicotomica, che divide l'intervallo a ogni domanda.
Penso a un numero intero compreso tra 1 e 1000. Puoi farmi domande a cui rispondo solo con sì o no. Quante domande sì o no bastano, nel caso peggiore, per indovinare questo numero con certezza?
Un indizio?
Non provare i numeri uno per uno: scegli ogni domanda in modo da eliminare la metà delle possibilità rimaste.
Mostra la risposta e la soluzione
Risposta: 10 domande: ogni risposta dimezza il numero di possibilità, e 2 elevato a 10 vale 1024, maggiore di 1000.
Il ragionamento
Ogni domanda sì o no divide le possibilità rimaste in due gruppi, ad esempio chiedendo se il numero è maggiore di 500. Qualunque sia la risposta, si conserva una metà dell'intervallo e si ripete il procedimento su questa nuova metà. Dopo k domande restano al massimo circa 1000 diviso 2 elevato a k possibilità. Con 9 domande si possono distinguere solo 2 elevato a 9, cioè 512 casi, insufficienti per 1000 numeri. Con 10 domande se ne distinguono 2 elevato a 10, cioè 1024, che bastano. La risposta è quindi 10 domande nel caso peggiore. Questo principio è quello della ricerca dicotomica, di complessità O(log n).
Rilevare un ciclo in una lista concatenata senza memoria: la soluzione
Domanda di colloquio per sviluppatori su strutture dati e complessità di memoria.
Una lista concatenata è una sequenza di nodi, ciascuno dei quali punta al successivo. Può capitare che un nodo punti a un nodo già incontrato: la lista forma allora un ciclo e non finisce mai. Come rilevare se esiste un ciclo, senza usare memoria supplementare proporzionale alla dimensione della lista?
Un indizio?
Immagina due corridori che percorrono la lista a velocità diverse: cosa succede se girano indefinitamente su un ciclo?
Mostra la risposta e la soluzione
Risposta: Algoritmo di Floyd: un puntatore avanza di un nodo, l'altro di due; se si incontrano, c'è un ciclo (complessità O(n) di tempo, O(1) di memoria).
Il ragionamento
Bastano due puntatori all'inizio della lista: la tartaruga avanza di un nodo a ogni passo, la lepre di due nodi. Se la lista finisce, la lepre raggiunge la fine e si conclude che non c'è un ciclo. Se esiste un ciclo, i due puntatori finiscono per entrarvi: la lepre raggiunge allora la tartaruga, perché guadagna un nodo a ogni passo, e si incontrano su uno stesso nodo. Il numero di passi è proporzionale alla dimensione della lista, quindi la complessità è O(n) nel tempo. Poiché si memorizzano solo due puntatori, la memoria aggiuntiva è O(1).
Domande frequenti
Quali tipi di enigmi trovo in questa pagina tech?
La pagina raccoglie quattro enigmi di ragionamento algoritmico: il problema delle due uova e dei 100 piani, la ricerca di un numero mancante in un vettore, la ricerca di un numero tra 1 e 1000 con domande sì o no, e il rilevamento di un ciclo in una lista concatenata. Ognuno si descrive con un metodo breve e un costo in tempo e in memoria.
Bisogna saper programmare per risolvere questi enigmi?
No: il metodo si descrive prima a parole, per esempio dimezzando il numero di possibilità a ogni domanda, e solo dopo si traduce in codice. Il codice arriva dopo, quando il ragionamento e il suo costo sono stabiliti.
Come prepararsi a questi enigmi di algoritmi?
Per ogni enigma, enuncia il metodo e poi indica il suo costo in tempo e in memoria, come fanno le soluzioni di questa pagina. Inizia dai problemi di suddivisione dello spazio dei possibili, poi passa alle strutture dati come le liste concatenate.
E poi?
Il ragionamento si allena come la memoria: provandoci spesso. Mettiti poi alla prova con i nostri quiz di cultura generale.