1

I have number of users to allocate to number of computers instances like docker or AWS. user can increase the number of instances and also can change the users. The instances have weight percentage.

  • Users: 10
  • Locations: 2 [{loc1.weight: 70%}, {loc2.weight: 30%}] so it's simple to have 7 and 3 users for each.

The total percentage might not be equal to hundred so scale factor can be anything.

My other requirement is each instance must have at least 1 user. I have condition applied that minimum user can not be less than locations so that part is good.

Other requirement is all users should be integers.

Example

Case #1

Users: 5
Locations: 4 where 1.weight = 15, 2.weight = 30, 3.weight = 15, 4.weight = 50 (total weight 110%)

Expected Results

Locations:
    1.users = 1,
    2.users = 1,
    3.users = 1,
    4.users = 2

Case #2

Users: 10
Locations: 4 where 1.weight = 10, 2.weight = 10, 3.weight = 90, 4.weight = 10 (total weight 120%)

Expected Results

Locations: 
    1.users = 1, 
    2.users = 1, 
    3.users = 7, 
    4.users = 1

Case #3

Users: 5
Locations: 2 where 1.weight = 50, 2.weight = 50

Expected Results

Locations: 
    1.users = 3, 
    2.users = 2

That was all of the explanation of the problem. Below is what I had tried.

function updateUsers(clients, weights) {
  
  let remainingClients = clients;
  const maxWeight = weights.reduce((total, weight) => total + parseInt(weight), 0);
  let r = [];
  weights.forEach(weight => {
    let expectedClient = Math.round(clients * (weight / maxWeight));
    let val = remainingClients <= expectedClient ? remainingClients : expectedClient;
    remainingClients -= expectedClient;
    r.push(val > 0 ? val : 1);
  });
  if ( remainingClients > 0 ) {
    r = r.sort((a, b) => a > b ? 1 : -1);
    
    for ( let i = 0; i < remainingClients; i++ ) {
      r[i] = r[i] + 1;
    }
  }
  return r;
}

I get good results for some numbers like

updateUsers(12, [5, 5, 5, 90]);

gives

[1, 1, 1, 9]; //total 12 users

but using very odd figures like below

updateUsers(12, [5, 5, 5, 200]);

returns

[2, 1, 1, 11]; //total 15 users which is wrong
TylerH
  • 20,799
  • 66
  • 75
  • 101
Aamir Mahmood
  • 2,704
  • 3
  • 27
  • 47
  • 2
    No its not a homework and its real life problem. I've been struggling to wrap my head around, and if you are removing deleting questions/answers please check i have good repute for a reason. thanks – Aamir Mahmood Apr 28 '21 at 18:44
  • For the most part, a good question in SO does not ask people to write code for them. If you want code you should try to solve the problem yourself, show us your results, and ask us where you're going wrong. You haven't even asked a question. If you're going to use a javascript tag, then we would expect, in most cases, to find code in your question. – Software Engineer Apr 28 '21 at 18:50
  • Sure, I'll try to update the question, the code I have been working is in EmberJS and is having nested objects and arrays. I can not just post what I've been doing. I had to re-write the whole thing in normal JS. I understand your intentions and I appreciate them. – Aamir Mahmood Apr 28 '21 at 18:55
  • Much better -- I'll remove my downvote – Software Engineer Apr 28 '21 at 20:19

2 Answers2

2

At first get percentage, You said that in every quota should at least have 1 user, So we used Math.floor(), If its equal to 0, we return 1 and update userCount like so 1 - percentage.

const sumProcedure = (sum, n) => sum + n;
function updateUsers(userCount, weights) {
    let n = userCount,
        totalWeight = weights.reduce(sumProcedure),
        results = weights.map(weight => {
            let percentage = (weight * userCount) / totalWeight,
                floor = Math.floor(percentage);

            if (floor == 0) {
                userCount -= 1 - percentage;
                return 1
            }
            return floor;
        }),
        remain = n % results.reduce(sumProcedure);

    while (remain--) {
        let i = weights.indexOf(Math.max(...weights));
        weights.splice(i, 1);
        results[i]++
    }
    return results;
}
console.log(updateUsers(5, [50, 50]));          // [3 , 2]
console.log(updateUsers(12, [5, 5, 5, 90]));    // [1, 1, 1, 9]
console.log(updateUsers(12, [5, 5, 5, 200]));   // [1, 1, 1, 9]
console.log(updateUsers(5, [15, 30, 15, 50]));  // [ 1, 1, 1, 2 ]
console.log(updateUsers(10, [10, 10, 90, 10])); // [ 1, 1, 7, 1 ]
console.log(updateUsers(55, [5, 5, 5, 90]));    // [ 3, 2, 2, 48 ]; It has 2 remainders
Nur
  • 2,361
  • 2
  • 16
  • 34
1

This approach works if speed is not super important. I don't know javascript, so a bit of it is going to be in pseudocode. I'll keep your notations though.

Let wSum = sum(weights) be the sum of all weights and unitWeight = wSum / weights.length be the weight each user should be assigned if all were given equal weight. Now, let

r[i] = 1;
weights[i] -= unitWeight;

for i = 0, 1 ... weights.length-1. This ensures that all locations receive at least 1 user and the weights are updated to reflect their 'remaining' weight. Now

remainingClients = clients - weights.length;

Assign the rest of the clients via a while(remainingClients > 0) loop or similar:

while(remainingClients > 0)
{
    var indexMax = argMax(weights);
    weights[indexMax] -= unitWeight;
    r[indexMax] += 1;
    remainingClients -= 1;
}

This gives the expected result for all your examples. The argMax should of course just return the index of the array corresponding to the maximum value. Due to argMax, the runtime becomes O(n^2), but it doesn't sound like you have tens of thousands of users, so I hope that's okay.

MinosIllyrien
  • 330
  • 1
  • 9