-
Notifications
You must be signed in to change notification settings - Fork 2
Recursion: Server Utilization
Server Utilization:
There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?
Example 1:
Servers capacity limits: 8, 16, 8, 32
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8
For this example, the program should say 'true'.
Example 2:
Server capacity limits: 1, 3
Task capacity needs: 4
For this example, program should return false.
First approach is checking all the possible arrangements to fit a set of task in a server. since there are only 8 servers, it wont hurt much.
- Time Complexity: O(8^8) = O(2^24)
- Space Complexity: O(1)
Second approach is based on the observation that this problem can be reduced to a bin packing problem.
a. Sort the servers in decreasing order of their capacity.
b. Pick the first server (S0) and check how many tasks in can accommodate, its akin to knapsack problem
where you tasks required capacity is its both weight and value T1(wi, vi). Lets call these set of tasks S.
c. Now repeat steps (b.) with S1 and (T - S) ie how many of the remaining tasks can be allotted to S1.
d. The terminating condition here is we run out of tasks to allocate, then return true
OR we run out of servers and we still have tasks to allocate.
- Time Complexity: O((S^2)*T) where S = no. of servers, T = no. of Tasks. Much better than exponential.
- Space Complexity: O(S*T)