Sono andato per un colloquio e ho avuto un problema con il carico di lavoro:
Problem: write a function to tell whether a series of workloads will exceed
the maximum workload or not
Input: MaxWorkLoad: example 10
Timeslot and workload: example [(2, 6, 3), (3, 8, 2), ... ]
The (2, 6, 3) is begin time, end time, and workload
And it means from time 2 to time 6, the workload is 3
You can treat the 2, 6 as the UNIX epoch time.
The time may not be integers, so instead of 2, it can be 2.2
The input can be in any time order. For example: [(20, 60, 3), (3, 8, 2)]
The workload will "add up", so a 3 and 2 will add up to 5
Output: a boolean indicating whether the series of workload can fit in without
exceeding MaxWorkLoad
La domanda breve è: questo problema del carico di lavoro appartiene a una classe di algoritmi e quando la matrice è vuota, ma i dati continuano a venire in M di volte e dobbiamo dire possibile o non M di volte, c'è una soluzione migliore di O(M * M) ?
dettagli:
Se mi concentro su come determinare se gli intervalli di tempo si sovrapporranno l'uno con l'altro, si scopre che non è una soluzione facile.
Quindi non sono sicuro che sia adatto come domanda per un colloquio, perché potresti sapere come risolverlo o non lo fai. Se l'hai già visto, lo risolverai come un gioco da ragazzi. Se non l'hai visto prima, non credo che 20 minuti potrebbero essere il tempo sufficiente per sbloccare.
Potresti voler pensare a come potresti risolverlo, se vuoi divertirti.
La soluzione semplice, che potrei inventare, ma dopo 15 minuti dopo, in realtà, può essere: usa semplicemente un dizionario e usa il limite di tempo come chiave, e se è (2, 6, 3) , quindi segna come dict[2] = 3 e dict[6] = -3 .
Allo stesso modo, per (3, 8, 2) , quindi dict[3] = 2 e dict[8] = -2
(e in realtà, se consideriamo l'endpoint temporale come inclusivo, allora non avremo dict[8] = -2 ma abbiamo dict[9] = -2 , trattandolo come un calo del carico di lavoro al momento 9 anziché a 8 )
E poi, una volta che hai l'intero dizionario, ora esegui il loop di ogni chiave nel dizionario, in ordine ordinato, e mantieni un numero CurrentWorkLoad come carico di lavoro. Pertanto, quando vedi dict[2] come 3 , aggiungi 3 a CurrentWorkLoad e quando vedi dict[3] , aggiungi 2 a CurrentWorkLoad e quando vedi dict[6] , aggiungi% da-3 a CurrentWorkLoad .
Quindi, non appena CurrentWorkLoad è maggiore di MaxWorkLoad , puoi immediatamente restituire false . Altrimenti, alla fine del ciclo, restituisci semplicemente true .
E se ci fosse (2, 6, 3) e (6, 8, 1) , il che significa che l'endpoint può "sovrapporsi" al momento 6 ? Quindi, mi sono inventato, o usare un array per ricordare tutti i valori quando collide a 6 , o, semplicemente, sommare i valori. Quindi la prima volta che vedi (2, 6, 3) , poi dict[6] is -3 e quando vedi (6, 8, 1) , poi dict[6] += 1 e diventa -2 .
Quindi, se in JavaScript, è come
dict[beginTime] ||= 0; // if not defined, then set it to 0
dict[beginTime] += workload;
dict[endTime] ||= 0;
dict[endTime] -= workload;
e il resto dell'algoritmo rimarrà lo stesso.
Quindi la complessità temporale per la dimensione dell'array N è O(N log N) , perché abbiamo bisogno di ordinare le chiavi.
L'intervistatore mi ha chiesto, e se questa operazione fosse ripetuta M volte?
Quindi, ad esempio, se l'array iniziale è vuoto, ma i dati continuano ad arrivare, per M volte e M può essere un milione o dieci milioni. Allora qual è la complessità del tempo? Inizialmente ho detto che è O(M * M log M) , ma in seguito ho scoperto che potrebbe essere O(M * M) , perché non abbiamo bisogno di ordinare le chiavi ogni volta. Possiamo semplicemente "inserire" la chiave in una lista già ordinata.
Esiste una classe di algoritmo o di problem solving correlata a questa e una soluzione migliore di O(M * M) ?