Durante un colloquio telefonico da Software Development Engineer in Amazon mi è stato chiesto di trovare, e codificare tramite la piattaforma CollabEdit, la soluzione al seguente problema:
Dato un array di interi, scrivere un metodo che ritorna true se all’interno dell’array ci sono due elementi che sommati tra loro danno il valore x fornito come input e false altrimenti..
Vediamo come affrontare il problema.
La prima idea è quella di utilizzare una strategia forza bruta e sommare tra loro tutte le coppie di valori e confrontare il risultato con il valore x fornito in input.
L’immagine seguente illustra il procedimento, che consiste nel partire dal primo elemento e sommarlo ad ogni iterazione a quelli successivi, poi tornare al secondo elemento e ripetere l’operazione, partendo da quello successivo a se stesso. Il confronto con i precedenti non viene eseguito perchè è già stato effettuato nell’iterazione precedente. Nell’immagine sono evidenziati in rosso i confronti che non vengono eseguiti.
Implementiamo questa prima soluzione:
public class AmazonSumToX {
public static boolean findSumBruteForce(int[]a, int x) {
for (int i=0; i< (a.length-1); i++) {
for (int k=i+1; k < a.length; k++) {
if((a[i] + a[k]) == x){
System.out.println(a[i] + " + " + a[k] + " = " + x);
return true;
}
}
}
return false;
}
public static void main(String[] args) {
// inputs
int[] ar = { 10, 5, 6, 20, 12, 40, 11, 3, 25, 15, 14, 1 };
int x = 55;
boolean ris = findSumBruteForce(ar, x);
System.out.println("Found: " + ris);
}
}
Abbiamo quindi creato la nostra funzione e gli forniamo in input un array di interi ed un valore x da cercare. Con il test case fornito, ci aspettiamo che la funzione ritorni true, in quanto è presente la coppia di elementi 40 e 15 che da come somma proprio il 55 della nostra x.
Proviamo ad eseguire il programma ed otteniamo il seguente risultato:
40 + 15 = 55 Found: true
Sottoponiamo ora al programma un test case in cui assegnamo alla variabile x un valore che non viene ottenuto dalla somma di nessuna delle coppie di elementi presenti.
Modifichiamo nel codice precedente la riga:
int x = 100;
ed otteniamo:
Found: false
A questo punto analizziamo la complessità dell'algoritmo in termini di numero di confronti effettuati tra le coppie di elementi.
Il primo elemento viene confrontato con tutti gli altri elementi, quindi per un array di lunghezza N, il primo elemento viene confrontato N-1 volte. Il secondo elemento, viene confrontato con tutti gli elementi tranne il primo e se stesso, quindi effettua N-2 confronti. Il terzo elemento N-3 confronti e cosi via, fino al penultimo elemento che effettua 1 confronto con l'ultimo elemento.
Analizziamo il caso peggiore, quello cioè in cui nessuna coppia di elementi da come risultato della loro somma il numero x di input. In questo caso l'algoritmo effettua (N-1)+(N-2)+(N-3)...+1 confronti, che possiamo quindi calcolare con (N*(N-1))/2
Torniamo al nostro esempio e modifichiamo il codice aggiungendo una variabile per il conteggio dei confronti e la stampa a video del suo valore al termine della funzione di ricerca:
public class AmazonSumToX {
public static boolean findSumBruteForce(int[]a, int x) {
int count = 0;
for (int i=0; i< (a.length-1); i++) {
for (int k=i+1; k < a.length; k++) {
count++;
if((a[i] + a[k]) == x){
System.out.println(a[i] + " + " + a[k] + " = " + x);
System.out.println("Number of comparisons: " + count);
return true;
}
}
}
System.out.println("Number of comparisons: " + count);
return false;
}
public static void main(String[] args) {
// inputs
int[] ar = { 10, 5, 6, 20, 12, 40, 11, 3, 25, 15, 14, 1 };
int x = 55;
boolean ris = findSumBruteForce(ar, x);
System.out.println("Found: " + ris);
}
}
Eseguendo questa nuova versione del programma otteniamo:
40 + 15 = 55 Number of comparisons: 49 Found: true
Se modifichiamo nuovamente la nostra x assegnandole un valore che non compare come somma di due elementi dell'array, otteniamo:
Number of comparisons: 66 Found: false
Il numero di confronti ottenuti nel caso peggiore è 66 dato, come visto in precedenza da:
N=12
N-1=11
(N*(N-1))/2 = 132/2 = 66
Ovviamente questa soluzione non è molto efficiente, per cui dobbiamo trovare un modo per realizzare una funzione che produce lo stesso risultato ma con una complessità computazionale inferiore.
Un modo per farlo, ed è la soluzione che ho fornito durante il colloquio, è il seguente:
- Ordiniamo l'array utilizzando un algoritmo efficiente come il QuickSort (caso medio O(n*logn))
- Sommiamo il primo e l'ultimo elemento, mantenendo due indici su di essi e poi:
- ritorniamo true se la loro somma è uguale a x
- incrementiamo l'indice dell'elemento inferiore se la somma È minore di x
- decrementiamo invece l'indice dell'elemento superiore se la somma è maggiore di x
La figura seguente illustra un esempio di questo procedimento: abbiamo un array di elementi e il valore di input x da cercare uguale a 14.
La prima operazione è quella di ordinare l'array. Una volta fatto ciò, come detto, assegnamo due indici al primo ed all'ultimo elemento ed iniziamo i confronti da questi due elementi. In questo caso il primo elemento è 3 e l'ultimo è 20, per cui otteniamo 23 che è maggiore del nostro target 14. Decrementiamo quindi l'indice superiore alla posizione precedente e sommiamo questa volta l'elemento 3 con l'elemento 15. Il risultato è ancora maggiore di 14 per cui decrementiamo ancora l'indice superiore che punta così all'elemento 10. Sommando 3 e 10 otteniamo 13 che questa volta è inferiore a 14, per cui questa volta teniamo fisso l'indice superiore ed incrementiamo l'indice inferiore. Sommiamo quindi l'elemento 5 e l'elemento 10, ottenendo 15 e decrementiamo quindi l'indice superiore. Questa volta sommando gli elementi 5 e 9 otteniamo il valore target di 14, per cui abbiamo completato la ricerca.
Implementiamo questa nuova versione della funzione:
import java.util.Arrays;
public class AmazonSumToX {
public static boolean findSumSort(int[] a, int x) {
Arrays.sort(a); // quicksort
for (int i = 0, k = a.length - 1; i < k;) {
int tmp = a[i] + a[k];
if (tmp == x)
return true;
else if (tmp < x)
i++;
else
k--;
}
return false;
}
public static void main(String[] args) {
int[] ar = { 10, 3, 5, 8, 15, 9, 20 };
int x = 14;
boolean ris = findSumSort(ar, x);
System.out.println("Found: " + ris);
}
}
Forniamo al programma l'array ed il valore di input utilizzati nell'esempio illustrato in figura e proviamo ad eseguirlo. Prima di farlo però, aggiungiamo qualche istruzione di stampa a video che ci permetterà di tracciare il flusso di esecuzione e la sequenza di confronti effettuati dall'algoritmo:
public static boolean findSumSort(int[] a, int x) {
Arrays.sort(a); // quicksort
for (int i = 0, k = a.length - 1; i < k;) {
int tmp = a[i] + a[k];
System.out.println(a[i] + " + " + a[k] + " = " + tmp);
if (tmp == x)
return true;
else if (tmp < x) {
System.out.println(tmp + " < " + x);
i++;
}
else {
System.out.println(tmp + " > " + x);
k--;
}
}
return false;
}
Eseguendo il programma l'output che otteniamo è:
3 + 20 = 23 23 > 14 3 + 15 = 18 18 > 14 3 + 10 = 13 13 < 14 5 + 10 = 15 15 > 14 5 + 9 = 14 Found: true
L'output generato rispecchia la sequenza di operazioni illustrate precedentemente tramite la figura. Al solito, lo proviamo anche su un test case che prevede che il valore x fornito non sia presente nell'array di input.
Assegniamo ad esempio x = 16 ed otteniamo:
3 + 20 = 23 23 > 16 3 + 15 = 18 18 > 16 3 + 10 = 13 13 < 16 5 + 10 = 15 15 < 16 8 + 10 = 18 18 > 16 8 + 9 = 17 17 > 16 Found: false
Il caso peggiore è sempre quello in cui una coppia di elementi che sommati da x non sia presente ed in questo caso la complessità dell'algoritmo è data:
il costo del processo di ordinamento (n*logn) + (n-1) confronti tra gli elementi
Effettuiamo ora un confronto sul comportamento dei due algoritmi in termini di performance nel caso peggiore, al crescere della dimensione N dell'array di input.
Modifichiamo il codice nel modo seguente, in cui popoliamo ogni volta un array con numeri casuali inferiori a 100 e forniamo in input un valore x che non puÚ essere raggiunto dalla somma di due elementi dell'array.
import java.util.Arrays;
import java.util.Random;
public class AmazonSumToX {
public static final int NUM_OF_ELEMENTS = 50_000;
public static boolean findSumSort(int[] a, int x) {
Arrays.sort(a); // quicksort
for (int i = 0, k = a.length - 1; i < k;) {
int tmp = a[i] + a[k];
if (tmp == x)
return true;
else if (tmp < x)
i++;
else
k--;
}
return false;
}
public static boolean findSumBruteForce(int[]a, int x) {
for (int i=0; i< (a.length-1); i++) {
for (int k=i+1; k < a.length; k++) {
if((a[i] + a[k]) == x)
return true;
}
}
return false;
}
public static void main(String[] args) {
int[] ar = new int[NUM_OF_ELEMENTS];
int x = 210;
Random r = new Random();
for (int i =0; i < NUM_OF_ELEMENTS; i++)
ar[i] = r.nextInt(100);
System.out.println("Array SIZE: " + NUM_OF_ELEMENTS);
long startTime = System.nanoTime();
boolean ris = findSumBruteForce(ar, x);
long endTime = System.nanoTime();
System.out.println("Brute Force: " + ris + " - Time: " + ((endTime-startTime)/1000000.0));
startTime = System.nanoTime();
ris = findSumSort(ar, x);
endTime = System.nanoTime();
System.out.println("Sort and Search: " + ris + " - Time: " + ((endTime-startTime)/1000000.0));
}
}
Di seguito sono riportati dei risultati significativi dell'esecuzione ripetuta dei 2 algoritmi su dimensioni dell'array da 50 mila a 500 mila elementi espressi in millisecondi.
Come possiamo vedere la seconda soluzione offre delle prestazioni significativamente migliori!
Array SIZE: 50000 Brute Force: false - Time: 1344.479255 Sort and Search: false - Time: 4.626856 Array SIZE: 100000 Brute Force: false - Time: 5360.940353 Sort and Search: false - Time: 5.980064 Array SIZE: 200000 Brute Force: false - Time: 21429.703085 Sort and Search: false - Time: 9.089177 Array SIZE: 500000 Brute Force: false - Time: 134992.31612 Sort and Search: false - Time: 20.261945
Il codice del programma è scaricabile qui:
Pingback: Amazon Interview: trovare l’unico elemento che compare un numero dispari di volte all’interno di un array di interi | Dede Blog