Server Load Balancer

Server Load Balancer

February 10, 2024
medium
dynamic programming

Problem Statement: #

You are given a list of n servers, where each server has a certain load represented by an integer. Your task is to partition this list into two sublists such that:

  • The absolute difference between the sums of the loads of the two sublists is minimized.
  • Each server belongs to exactly one sublist.
  • The order of servers in the sublists does not matter.

Return the minimum possible absolute difference.

Constraints:

  • 1 <= n <= 20
  • The load of each server is an integer in the range [1, 100].

Example:

Input: loads = [1, 2, 3, 4, 5]
Output: 1
Explanation: One optimal partition is [1, 2, 5] and [3, 4]. The sums of the loads are 8 and 7, respectively, so the absolute difference is 1.

Solution Approach: #

Dynamic Programming (DP) with Bitmasking:

This problem can be solved using a dynamic programming approach that leverages bitmasking to represent subsets of servers.

Algorithm Steps:

  1. Subset Sum Calculation: Use a bitmask to represent each possible subset of servers. The value of the bitmask at position i indicates whether server i is included in the subset. For each subset, calculate the sum of loads.

  2. DP Table Initialization: Initialize a DP table dp where dp[i] represents the minimum absolute difference achievable with the first i subsets considered.

  3. Iterate Over Subsets: For each subset, update the DP table based on the minimum absolute difference between any two partitions that can be formed.

  4. Minimize Absolute Difference: For each subset, consider splitting the servers into two groups (the current subset and the rest) and update the DP table to reflect the minimum absolute difference obtained.

  5. Result Extraction: The final answer is the minimum absolute difference achievable, which will be stored in the DP table after considering all subsets.

Code: # 

def minLoadDifference(loads):
    n = len(loads)
    totalLoad = sum(loads)
    dp = [float('inf')] * (1 << n)
    dp[0] = 0  # Base case: no server, no difference
    
    for mask in range(1 << n):
        subsetSum = 0
        for i in range(n):
            if mask & (1 << i):
                subsetSum += loads[i]
                
        for i in range(n):
            if mask & (1 << i) == 0:
                nextMask = mask | (1 << i)
                otherSubsetSum = totalLoad - subsetSum - loads[i]
                dp[nextMask] = min(dp[nextMask], abs(subsetSum + loads[i] - otherSubsetSum))
                
    return dp[-1]

# Example usage
loads = [1, 2, 3, 4, 5]
print(minLoadDifference(loads))

Time Complexity: #

  • O(n * 2^n): There are 2^n subsets of servers, and for each subset, we iterate through n elements to calculate the sum and update the DP table.

Space Complexity: #

  • O(2^n): The DP table has 2^n entries, corresponding to each possible subset of servers.