Come risolvere i problemi di programmazione dei colloqui di lavoro: un esempio pratico

In questo articolo vedremo come risolvere un semplice problema di programmazione che potreste incontrare nei colloqui di selezione dei candidati ad un posto di sviluppatore.

Il problema è classificato come semplice ed è il seguente:

Dato un array di numeri interi nums e un intero target, restituire gli indici dell'array i cui valori sommati restituiscano il valore di target.

Esempio numero 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Spiegazione: Poichè nums[0] + nums[1] == 9, restituiamo [0, 1].

Esempio numero 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Spiegazione: Poichè nums[1] + nums[2] == 6, restituiamo [1, 2].

Esempio numero 3:

Input: nums = [3,3], target = 6
Output: [0,1]
Spiegazione: Poichè nums[0] + nums[1] == 6, restituiamo [0, 1].

Come ragioniamo? Per prima cosa dobbiamo identificare il soggetto del problema. In questo caso il soggetto è costituito dagli array di numeri interi. Il problema vuole che noi sommiamo due valori di questo array e verifichiamo di volta in volta se il risultato della somma è uguale al numero intero di riferimento.

La somma non va effettuata a caso, ma seguendo l'ordine dell'array tenendo presente la voce corrente e quella successiva. Quindi procediamo così:

Array di input: [2,7,11,15]
Intero di riferimento: 9

1. Inizializzo un contatore per tracciare l'indice
2. Inizializzo un array di output dove memorizzare gli indici trovati
3. LOOP:
4. Incremento il contatore: intero corrente
5. Aggiungo 1 al contatore: intero successivo
6. Sommo intero corrente + intero successivo
7. SE la somma è uguale a Intero di riferimento:
• Inserisco in array di output il valore del contatore dell'intero corrente
• Inserisco in array di output il valore del contatore dell'intero successivo
• Interrompo LOOP
8. FINE LOOP
9. Restituisco l'array di output.

Vediamone l'esecuzione simulata:

INPUT = [2, 7, 11, 15]
RIFERIMENTO = 9

FUNZIONE(INPUT, RIFERIMENTO)
    CONTATORE = 0
    OUTPUT = []
    
    LOOP(INPUT)
        CONTATORE++
        SOMMA = INPUT[CONTATORE] + INPUT[CONTATORE + 1]
        SE(SOMMA == RIFERIMENTO)
            OUTPUT[] = CONTATORE
            OUTPUT[] = CONTATORE + 1
            BREAK    
    FINE_LOOP
    RETURN OUTPUT
    
FUNZIONE()
- CONTATORE = 0
- OUTPUT = []
- LOOP
  - CONTATORE = 0
  - SOMMA = 2 + 7
  - SE(SOMMA == 9)
    - OUTPUT[] = 0
    - OUTPUT[] = 1
    - BREAK
 
OUTPUT: [0, 1]          

In Python avremo:

def two_sum(nums, target):  
    if len(nums) == 0:  
        return []  
    if len(nums) == 1:  
        return [0] if nums[0] == target else []  
    output = []  
    i = -1  
    while i < len(nums) - 1:  
        i += 1  
        s = nums[i] + nums[i + 1]  
        if s == target:  
            output.append(i)  
            output.append(i + 1)  
            break  
    return output

In PHP avremo:

function two_sum($nums = [], $target = 0) {
         if(count($nums) === 0 || $target === 0) {
             return [];
         }   
         if(count($nums) === 1) {
             return $nums[0] === $target ? [0] : [];
         }
         $n = -1;
         $output = [];
         while($n <= count($nums) - 1) {
             $n++;
             $sum = $nums[$n] + $nums[$n+1];
             if($sum === $target) {
                 $output[] = $n;
                 $output[] = $n+1;
                 break;
             }
         }
         return $output;
    }

In JavaScript avremo:

const twoSum = (nums = [], target = 0) => {
    if(nums.length === 0) {
        return [];
    }
    if(nums.length === 1) {
        return nums[0] === target ? [0] : [];
    }

    const output = [];
    let i = -1;

    while(i < nums.length - 1) {
        i++;
        let sum = nums[i] + nums[i + 1];
        if(sum === target) {
            output.push(i);
            output.push(i + 1);
            break;
        }
    }

    return output;
};