Balance server capacity | allenlipeng47

Balance server capacity | allenlipeng47
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?
Ex:
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'.
Ex2:
Server capacity limits: 1, 3
Task capacity needs: 4
For this example, program should return false.
Solution:
First impression would be using greedy algorith. Each time, put the max task in the max capacity server. But it won't find the best answer for a lot of times. An counter-example is: Server capacity [4, 3], task[3, 2, 2].
So the solution should be use recursion to traverse the whole result possibilities.

1.     public static int[] balanceServer(int[] server, int[] task){
2.         if(server==null||task==null){
3.             return null;
4.         }
5.         int[] result = new int[task.length];
6.         for(int i=0;i
7.             result[i] = -1;
8.         }
9.         balanceServerUtil(server, task, 0, result);
10.         return result;
11.     }
13.     //put task[n] in the server, and save the result
14.     public static boolean balanceServerUtil(int[] server, int[] task, int n, int[] result){
15.         if(n>=task.length){
16.             return true;
17.         }
18.         for(int i=0;i
19.             if(server[i]>=task[n]){
20.                 server[i] -= task[n];
21.                 result[n] = i;
22.                 if(balanceServerUtil(server, task, n+1, result)){
23.                     return true;
24.                 }
25.                 server[i] += task[n];
26.                 result[n] = -1;
27.             }
28.         }
29.         return false;
30.     }

https://github.com/roseperrone/interview-questions/blob/master/tasks_for_servers.py
def tasks_for_servers(capacity_limits, capacity_needs, assignments):
  # Check if there are already 8 tasks scheduled to the given server
  if len(capacity_needs) == 0:
    return True
  for i in range(len(capacity_needs)):
    need = capacity_needs[i]
    new_needs = copy(capacity_needs)
    del new_needs[i]
    for j, limit in enumerate(capacity_limits):
      if len(assignments[i]) < 8 and sum(assignments[j]) + need <= limit:
        new_assignments = copy(assignments)
        new_assignments[j].append(need)
        if tasks_for_servers(capacity_limits, copy(new_needs), new_assignments):
          return True
    print need
    print assignments
  return False
Read full article from Balance server capacity | allenlipeng47