«

»

mar 21

Quesiti da colloquio (1)

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

Colloquio

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
Share Button