Questo articolo è la traduzione di un mio post del 2022 intitolato The Coding Interview.

Negli ultimi tempi ho dovuto fare molte interview per tre posizioni aperte nel mio team, e nel mio colloquio standard c’è una domanda in cui chiedo di sviluppare del codice. Mi focalizzo tendenzialmente su problemi che non prendano più del 50% del tempo a mia disposizione, quindi la domanda ideale che pongo dev’essere semplice, almeno in superficie, ma nascondere una soluzione migliore che necessiti un minimo di ragionamento per essere trovata.

Uno dei motivi per cui faccio una domanda di programmazione è vedere come la persona ragiona (se risolve il problema), e parte è vedere come reagisce ad una serie di situazioni che vanno al di là della domanda (come arrivano alla soluzione, e come proseguono). Durante il colloquio, ad esempio, pongo la mia attenzione sulla rapidità con cui ragionano, e sono in grado di spiegare i ragionamenti che stanno facendo, oppure no. Se richiedono aiuto, riescono a cogliere i suggerimenti al volo, o richiedono una descrizione dettagliata? Tutti questi piccoli elementi mi dicono quanto bene la persona si integrerà nel team, e quanto e come dovrò interagire con loro se saranno assunti.

Di solito, dopo che hanno risolto tutto il problema, propongo una serie di modifiche al codice che potrebbero migliorare il codice o meno, e chiedo loro di discutere le modifiche. A volte le modifiche possono essere convenienti per alcuni casi (ad esempio, in una funzione generica, solo alcuni tipi potrebbero beneficiare dalla modifica). Mi aspetto che il candidato sappia capire le implicazioni, ed concordare o rifiutare le mie modifiche. Questo è ancora parte del colloquio.

Ma alla fine, la domanda più importante che mi chiedo come selezionatore è semplice: mi piacerebbe lavorare con questa persona?

Dato che molti di questi dettagli non risultano chiari ai candidati, da oggi cercherò di scrivere una serie di post dove analizzerò alcuni colloqui ipotetici, presenterò delle soluzioni possibili, e darò qualche idea su come prepararsi ad un colloquio tecnico di programmazione, per capire quello che il vostro selezionatore si aspetta di vedere.

Nota: Questa non è una domanda che chiedo solitamente, ma un esempio di come dovreste cercare di svolgere il vostro colloquio tecnico, sottolineando cosa un selezionatore vorrebbe vedere e sentire.

La domanda

Data una sequenza (array) di interi non-negativi, trovare una sotto-sequenza contigua che abbia come somma un dato numero S. Implementare la soluzione come un algoritmo generico, ma visualizzare il valore del primo e dell’ultimo elemento con gli indici che partono da 1.

Il prototipo

Come prima cosa, il problema richiede di scrivere una funzione, quindi scriveremo il prototipo della funzione. Dal momento che ci è richiesto di scrivere un algoritmo generico, è sempre meglio usare le convenzioni correnti: in questo caso cercheremo di imitare la libreria standard (STL). Prenderemo due iteratori in ingresso (come tutti gli algoritmi pre-c++20 che si trovano in <algorithm>), assieme al valore che abbia lo stesso tipo dei valori delle sequenza, e produciamo in uscita una coppia di iteratori (proprio come std::equal_range).

Per rispettare il comportamento della libreria standard, considereremo il primo iteratore come inclusivo (il primo iteratore indica il primo elemento della sequenza), e l’ultimo come esclusivo (il secondo iteratore rappresenta il primo elemento oltre la fine della sequenza).

In questa soluzione, decidiamo di rappresentare la mancanza di soluzione con un intervallo {end(sequence), end(sequence)}. Un’altra opzione potrebbe essere un optional<pair<...>>, o un’eccezione.

Siamo pronti per scrivere il nostro prototipo (che in realtà è un’implementazione basilare, che fallisce sempre):

template<typename Iterator>
std::pair<Iterator, Iterator> find_range(Iterator b, Iterator e, std::decay_t<decltype(*b)> sum) {
    using result_t = std::decay_t<decltype(*b)>;
    static_assert(std::is_unsigned_v<result_t>);
// ...
    return {e, e};
}

In questo caso ho voluto dedurre il tipo del parametro sum. Questo permette di usare questa funzione con una collezione di qualunque tipo, a patto che il tipo rispetti la precondizione. Come controllo aggiuntivo, ho aggiunto uno static_assert per controllare la precondizione che il tipo dell’elemento sia non-negativo (il tipo è lo stesso della variabile sum). Se riuscite a scrivere questo codice con facilità fatelo; se siete incerti, sarà meglio spendiate il vostro tempo a cercare di risolvere il problema reale (questi, dopotutto, sono dei dettagli implementativi di importanza relativa).

I casi di test

Se non vi è dato del codice specifico per testare la vostra funzione, è meglio che partiate da lì, per mostrare al selezionatore che avete capito la domanda.

Dato che la richiesta era di rappresentare i risultati tramite indici che partono da 1, dobbiamo aggiungere tale valore alla posizione iniziale, ma non dobbiamo fare lo stesso per la fine (perché nella convenzione di STL questo caso è compensato dal fatto che l’iteratore finale sia esclusivo).

int main() {
    unsigned int sum = 15;
    unsigned int A[] =  {1,2,3,4,5,6,7,8,9,10};

    auto result = find_range(std::begin(A), std::end(A), sum);
    std::cout << "from " << result.first - std::begin(A) + 1 << " to " <<  result.second - std::begin(A);
}

Un’aggiunta interessante potrebbe essere la verifica che il risultato sia diverso da {std::end(A), std::end(A)}, ma durante un colloquio tecnico di programmazione il tempo è anche importante, quindi consiglio di saltare questo test. Ma non scordate di informare il selezionatore che sapete del fatto che il risultato sarà “strano” (l’indice di inizio sarà oltre la sequenza, e maggiore di quello di fine, che invece indicherà l’ultimo elemento), e che state evitando quel controllo intenzionalmente.

La soluzione ingenua

È sempre buona norma pensare prima alla soluzione più ingenua. Non è necessario che la implementiate, ma a volte può essere una buona base di partenza per arrivare alla soluzione finale. Se non siete sicuri di come procedere, e avete già un’idea migliore di questa soluzione, chiedete al selezionatore se vuole vedere anche la soluzione più semplice.

In questo caso, la soluzione semplice è di considerare tutte le sotto-sequenze che partono da begin(sequence) e finiscono con ciascun elemento, poi quelle che partono da begin(sequence) + 1, e così via.

template<typename Iterator>
std::pair<Iterator, Iterator> find_range(Iterator b, Iterator e, std::decay_t<decltype(*b)> sum) {
    using result_t = std::decay_t<decltype(*b)>;
    static_assert(std::is_unsigned_v<result_t>);
    Iterator start_of_range = b;
    for(Iterator start_of_range = b; start_of_range != e; ++start_of_range) {
        for(Iterator end_of_range = start_of_range; end_of_range != e; ++end_of_range) {
            if (std::accumulate(start_of_range, end_of_range, result_t{}) == sum) {
                return {start_of_range, end_of_range};
            }
        }
    }
    return {e, e};
}

Questa soluzione non è realmente utile per il nostro obiettivo finale, ma ci permette di calcolare la complessità di una soluzione sicuramente peggiore. La complessità è chiaramente O(N³), in quanto abbiamo 3 cicli uno dentro l’altro (due for, e un algoritmo std::accumulate), e tutti i cicli potrebbero potenzialmente scandire l’intera sequenza (N è in questo caso il numero di elementi nella sequenza). Esercitatevi nel calcolare sempre la complessità di ciascuna soluzione, inclusa la più ingenua, in automatico, questo vi aiuterà a visualizzare un possibile piano d’attacco per il problema.

Questa soluzione chiaramente considera sotto-sequenze che sono molto lontane dall’obiettivo S, e anche quest’informazione ci da l’idea che forse dovremmo concentrarci solo su una parte di queste sotto-sequenze..

La soluzione

L’idea “furba” è di scandire la sequenza solo una volta, tenendo traccia di una coppia di iteratori (uno è l’inizio della sequenza da analizzare, mentre l’altro è la fine

Iniziamo con la sottosequenza {begin(sequence), begin(sequence)}, per la quale sappiamo che la somma è 0 (terremo traccia di questa somma in modo incrementale, in questo modo non dovremo scandire la sequenza ulteriormente per calcolarne la somma).

Quando un elemento viene aggiunto alla sotto-sequenza (facendo avanzare l’iteratore di fine sequenza in avanti), la somma viene incrementata di una quantità pari al valore dell’elemento aggiunto, e al contrario, quando un elemento viene rimosso dalla sotto-sequenza (facendo avanzare l’iteratore di inizio sequenza in avanti), la somma viene aggiornata sottraendo il valore dell’elemento tolto.

Un elemento viene aggiunto se la somma corrente è sotto l’obiettivo S, e rimossose è al di sopra dell’obiettivo. Se raggiungiamo l’obiettivo, abbiamo ottenuto la soluzione, mentre se raggiungiamo la situazione in cui la sequenza risulta essere {end(sequence), end(sequence)}, non abbiamo nessuna soluzione.

In questo modo, forziamo l’algoritmo a considerare le sole soluzioni attorno al valore obiettivo S, e solo quelle, ignorando tutte le sotto-sequenze distanti da tale valore. Ci aspettiamo che questa soluzione abbia complessità O(N).

Il codice

Nel codice, per l’inizio della sotto-sequenza riutilizzeremo il parametro b, mentre la fine sarà denotata dalla variabile end_of_range. Rispetto alla discussione precedente, c’è un trucco extra: quando raggiungiamo la fine della sequenza per la prima volta, se siamo al di sotto dell’obiettivo non c’è modo per la somma di crescere ulteriormente, e quindi abbiamo un’uscita anticipata con il valore {end(sequence), end(sequence)}.

#include <cstdint>
#include <utility>
#include <iterator>
#include <iostream>
#include <type_traits>

template<typename Iterator>
std::pair<Iterator, Iterator> find_range(Iterator b, Iterator e, std::decay_t<decltype(*b)> sum) {
    using result_t = std::decay_t<decltype(*b)>;
    static_assert(std::is_unsigned_v<result_t>);
    result_t s = 0;
    Iterator end_of_range = b;
    while (sum != s && b != e) {
        if (s < sum) {
            if (end_of_range == e) {
                return {e, e};
            }
            s += *end_of_range;
            ++end_of_range;
        } else {
            // s > sum
            s -= *b;
            ++b;
        }
    }
    return {b, end_of_range};
}

int main() {
    unsigned int sum = 15;
    unsigned int A[] =  {1,2,3,4,5,6,7,8,9,10};

    auto result = find_range(std::begin(A), std::end(A), sum);
    std::cout << "from " << result.first - std::begin(A) + 1 << " to " <<  result.second - std::begin(A);
}

Domande aggiuntive

Cos’altro potrebbe chiedere un selezionatore, dopo che avete trovato la soluzione ottimale?

Per la soluzione qui sopra, mi vengono in mente un paio di domande:

• Possiamo rimuovere il controllo addizionale end_of_range == e? Quali sono le implicazioni sulla complessità?
• Possiamo spostare quel controllo alla condizione del ciclo while, al posto di b == e?

Altre domande, di natura diversa, potrebbero essere:

• Puoi pensare ad un contro esempio, nel quale questo codice fallisce? (forse la soluzione non è perfetta)
• Possiamo migliorare la complessità ulteriormente?

Non credo di dover inserire tutte le risposte qui, provate voi a ragionare sugli scenari alternativi!

Nota: Un enorme ringraziamento ad Alberto Invernizzi, che mi ha aiutato a correggere la mia traduzione originale, che oggettivamente era stata scritta un po’ di fretta durante un tragitto in treno, e ha corretto anche parecchi errori tipografici nella versione inglese.