Amazon Online Assessment (OA) - Multiprocessor System
Multiprocessor systems involve multiple CPUs for performing various tasks, which increases throughput and reduces response time. A multiprocessor system has a certain number of processors. Each processor has the ability to schedule a limited number of processes in one second. However, after each scheduling, the processor's ability is reduced to ability/2 rounded down to the nearest number. Only one processor can work to schedule processes each second. As an Amazonian you are tasked to find the minimum time required to schedule all the processes in the system given the processor's abilities and the number of processes.
Write an algorithm that returns minimum time required to schedule the processes.
The input to the function/method consists of three arguments:
num : an integer representing the number of processors
ability: a list of integers representing the ability of the processors
processes: a long integer representing the number of processes to be scheduled.
Return an integer representing the minimum time required to schedule the processes.
1 <= num <= 10^5
1 <= ability[i] <= 10^6
1 <= processes <= 10^12
0 <= i < num
It is guaranteed that the processes can be scheduled using the given multiprocessor system.
num = 5,
ability = [3, 1,7,2,4],
processes = 15
This can be solved optimally in the following way:
First, the processor with
ability = 7 schedules
7 processes in
one second. Now,
ability = [3, 1, 3, 2, 4] because
7 was reduced to
Second, the processor with
ability = 4 is used. After that,
ability = [3,1,3,2,2].
Third, the processor with
ability = 3 is used. Now,
ability = [1, 1, 3, 2, 2].
Finally, the processor with
ability = 1 is used to schedule the final process.
Each step requires one second of processing time, which adds up to
So, the output is