Quesiti da colloquio (1)
Il percorso critico
Anni fa feci il mio primo colloquio in un’azienda di Milano. Non ricordo il nome dell’azienda, potrei trovarlo facilmente cercando nelle email ma non mi va… e non mi va perchè andò male. Era un quesito abbastanza semplice. Lo risolsi tornato a casa in un foglio di carta in molto meno dei 40 minuti che mi diedero,ma sul momento andai nel pallone.
Ho deciso di postare il quesito e la sua soluzione.
(E’ la mia soluzione, non ho voluto cercarae conferme in letteratura nemmeno dopo)
Il quesito era qualcosa del genere
Sia L una lista di jobs ognuno dei quali ha un proprio tempo di esecuzione e dipende da un certo numero di jobs anchessi presenti in L. Calcolare il tempo di esecuzione di tutti i lavori supponendo di avere un numero illimitato di worker.
( era presentato in modo molto più discorsivo, parlava di antenne e di tecnici riparatori… ma la storiella proprio non la ricordo)
Analizzando il problema si può subito tirare fuori una soluzione basata sulla semplificazione di un grafo.
Inventiamoci una lista un minimo complessa e vediamo che succede.
Poniamo caso di avere la seguente lista di jobs:
ID | Tempo | Dipendenze |
---|---|---|
0 | 3 | — |
1 | 21 | 5 6 |
2 | 20 | — |
3 | 17 | 0 1 5 6 |
4 | 13 | 5 |
5 | 11 | 7 |
6 | 7 | 2 9 |
7 | 19 | — |
8 | 23 | — |
9 | 8 | — |
10 | 3 | 11 |
11 | 1 | — |
12 | 5 | 13 |
13 | 7 | 14 |
14 | 11 | — |
Dalla lista possiamo trarre direttamente un grafo direzionato
Si è aggiunto un nodo End che connette tutti i nodi da cui non partirebbe nessun arco.
Ha un valore puramente “visivo”
Un modo per affrontare il problema è semplificare il grafo fino ad arrivare ad un grafo costituito da n nodi collegati direttamente ad End.
Considerando che da ogni nodo escono archi che hanno tutti lo stesso peso per comodità di notazione chiameremo peso del nodo il peso dei suoi archi
Il tempo di esecuzione sarà il peso del ramo più pesante.
La regola di semplificazione è la seguente:
- Per ogni nodo a cui sono collegate solo foglie
- Si cerca la foglia più pesante
- Si eliminano le foglie collegate al nodo ( lo si rende foglia) e si aggiorna il suo peso al vecchio peso più il peso della foglia più pesante a cui era collegato.
- Si ripete la procedura fino ad avere solo foglie.
In questo modo si può semplificare il grafo ed arrivare alla soluzione.
La codifica in Ruby dell’algoritmo è molto semplice:
JOBS=[ { time: 2 ,dependencies: [] }, { time: 21,dependencies: [5,6] }, { time: 20,dependencies: [] }, { time: 17,dependencies: [0, 1, 5, 6] }, { time: 13,dependencies: [5] }, { time: 11,dependencies: [7] }, { time: 7 ,dependencies: [2,9] }, { time: 19,dependencies: [] }, { time: 23,dependencies: [] }, { time: 8,dependencies: [] }, { time: 3,dependencies: [11] }, { time: 1,dependencies: [] }, { time: 5,dependencies: [13] }, { time: 7,dependencies: [14] }, { time: 11,dependencies: [] }, ]
Adesso l’algoritmo vero e proprio, solo 14 righe in Ruby
def calcola(i) return JOBS[i] if JOBS[i].class == Fixnum return JOBS[i][:time].to_i if JOBS[i][:dependencies].size==0 m=0 JOBS[i][:dependencies].each{|d| JOBS[d]=calcola(d) m=[m,JOBS[d]].max } m + JOBS[i][:time] end JOBS.size.times{ |i| JOBS[i]=calcola(i) } puts JOBS.inspect puts JOBS.max
L’output dell’algoritmo è questo
[2, 51, 20, 68, 43, 30, 27, 19, 23, 8, 4, 1, 23, 18, 11]
68