Distribute Machines to Clusters

Assuming clusters are new clusters to setup, try to figure out a way to make the maximum work load optimized--meaning least maximum work load.

The quiz is from 2 Sigma OA. Here's a screen dump I found on the Net.


This should be from hacherrank.com because it asked for parsing input. I hate that part. You can use Scanner in java to do so, but who bother to remember they API details?

Anyway, assuming parameters are already parsed from input, then the solution is like this:

1. assign at least 1 machine to each cluster. because that's reasonable.
2. for rest of machines, in order to distribute to clusters, check the work load it will make in each cluster, pick the one/cluster that ends up with minimum work load.
3. do 2 for each of machine, until no machine to add in.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

static int[] distributeMachineToClusters(int b,int n,int[] a){ //define distribution array and initialize it with 1 distribution, which is minimum num of distr //also maximum of load int[] distributions = new int[n]; for(int i=0;i<n;i++){//O(n) distributions[i] = 1;//at least one distribution } b-=n;//used n already while(b>0){//O(bxn) int j = -1; int leastMax=Integer.MIN_VALUE; for(int i=0;i<n;i++){ //distribute to each of cluster, pick the one that drops load the least if(a[i]/(distributions[i]+1)>leastMax){ leastMax = a[i]/(distributions[i]+1); j=i; } } b--; distributions[j]++; } return distributions; }

Below is an improvement with MAX Heap.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

static int[] distributeMachineToClustersPQ(int b, int n, int[] a) { class Entry<K, V, N> { K cluster; V avgLoad; N numMachine; public Entry(K k, V v, N c) { cluster = k; avgLoad = v; numMachine = c; } } // now instead of thinking dropping load the least, thinking to mitigate // the one having most average load int[] distributions = new int[n]; PriorityQueue<Entry<Integer, Integer, Integer>> pq = new PriorityQueue<Entry<Integer, Integer, Integer>>( new Comparator<Entry<Integer, Integer, Integer>>() { @Override public int compare(Entry<Integer, Integer, Integer> o1, Entry<Integer, Integer, Integer> o2) { return o2.avgLoad - o1.avgLoad; } }); for (int i = 0; i < n; i++) {// O(n) Entry<Integer, Integer, Integer> e = new Entry<Integer, Integer, Integer>( i, a[i], 1);// maximum load per machine pq.add(e); } b -= n;// used n already while (b > 0) {// O(bxn) Entry<Integer, Integer, Integer> e = pq.poll(); b--; e.avgLoad = (e.avgLoad * e.numMachine) / (e.numMachine + 1); e.numMachine++; pq.add(e); } // prepare result int distributions[] = new int[n]; for (Entry<Integer, Integer, Integer> e : pq) { distributions[e.cluster] = e.numMachine; } return distributions; }