CODEWITHSUNDEEP
algorithm
sandy
sandy

Reputation: 529

How to load balance n servers with following constraints?

This was one of the interview questions asked to me in my campus placements.

There are 'n' servers which are assigned with some load(in integer). We have to find out the min. time required to balance them such that each server has load 1 on it.

Each server can share its load only with its adjacent neighbors(left and right).

Total load on all servers add up to n.

Ex. n=10
Initially, 0,0,10,0,0,0,0,0,0,0
Time 1 : 0,1,8,1,0,0,0,0,0,0
Time 2 : 1,1,6,1,1,0,0,0,0,0
.
.
Time 7 : 1,1,1,1,1,1,1,1,1,1

Answer is 7.

Initially, the load on servers can be present in any fashion. Not necessary that it will be present on only one server as it is in our current example.

How do I solve it? I couldn't come up with any approach.

Thanks in advance

Upvotes: 4

Views: 188

Answers (2)

user3386109
user3386109

Reputation: 34839

For each server, you need to decide how much of its load needs to move left and how much needs to move right. In your example, only two jobs can move left, so 7 have to move right, which takes 7 time periods.

If you have a situation like this

0, 0, 6, 0, 4, 0, 0, 0, 0, 0

then only two can move left from the 6, so three need to move right. That occupies the first six servers, so the 4 jobs need to occupy the last four servers. So it will take 5 time periods, since one job needs to move from the 4 to the last server.

One more example with n=15

0, 0, 0, 3, 0, 0, 0, 0, 4, 0, 0, 6, 2, 0, 0

The 3 needs to move left, taking 3 time periods. The 4 needs to move left, taking 5 time periods (since one of the jobs must occupy the space vacated by the 3). Four of the jobs from the 6 need to move left, taking 4 time periods. One of the jobs from the 6 needs to move right, taking 1 time period. The 2 jobs need to move right, taking 2 time periods. And the answer is 5, since one of the jobs from the 4 needed to move left 5 positions.

From these examples, it should be clear that's there's a simple O(n) solution to the problem:

int excess = 0;
int answer = 0;
for ( int i = 0; i < N; i++ )
{
    excess = excess + array[i] - 1;
    if ( abs(excess) > answer )
        answer = abs(excess);
}

The excess is negative when jobs need to move to the left, and positive when jobs need to move to the right. The maximum of the absolute value of the excess is the answer.

Upvotes: 4

halfo
halfo

Reputation: 223

I'm assuming that the sum of load is no more than the number of servers. My approach is using binary search over time and the complexity is O(n * logn).

Say, I'm going to check if it is possible to balance the load in time t. And I'll prefer to distribute the loads of a server s among it's left ones first. If it is not possible to distribute all the load to it's left (because maybe it will take more than time t to distribute all the loads to left or maybe some of those servers are already occupied), then I'm going to chose the servers on it's right side. If it is possible to distribute all the load within time t then, I'm going to chose a smaller t on next iteration, otherwise higher (a.k.a. binary search).

bool isBalancableWithin(Time t, Load[] loads) {
    int lastOccupiedIndex = -1;
    foreach (index, loads) {
        int startIndex = max(lastOccupiedIndex + 1, index - t);
        int endIndex   = startIndex + loads[i] - 1;

        if (endIndex > index + t || endIndex >= loads.length) return false;

        lastOccupiedIndex = endIndex;
    }

    return true;
}

Time lowerBound(Load[] loads) {
    Time lowest  = 0;
    Time highest = loads.length;

    while (lowest <= highest) {
        Time mid = (lowest + highest) / 2;

        if (isBalancableWithin(mid, loads)) highest = mid - 1;
        else lowest = mid + 1;
    }

    return lowest;
}

Upvotes: 3

Related Questions