1 day ago

Sarthak • 10

Hyderabad

Question: Minimum Network Lag (Data Centers & Servers)

Problem Statement: An AWS client has brought servers and databases from data centers in different parts of the world for their application. For simplicity, let's assume all the servers and data centers are located on a 1-dimensional line.

You have been given the task of optimizing the network connection. Each data center must be connected to a server. The positions of n data centers and n servers are given in the form of arrays. Any particular data center, center[i], can deliver to any particular server destination, destination[j]. The lag is defined as the distance between a data center at location x and a server destination at location y is |x - y|, i.e., the absolute difference between x and y.

Determine the minimum lag to establish the entire network.

Example: n = 3 center = [1, 2, 2]

destination = [5, 2, 4]

The most efficient deliveries are:

• The center at location 1 makes the first connection to the server at location 2.
• The center at location 2 makes the second connection to the server at location 4.
• The center at location 2 makes the third connection to the server at location 5.

• The minimum total lag is = abs(1 - 2) + abs(2 - 4) + abs(2 - 5) = 1 + 2 + 3 = 6.

6 hours ago

Rohit • 30

Hyderabad

Minimum Network Lag Solution

Overview

1. The goal is to pair each data center with a server to minimize the total absolute distance between them.
2. To minimize crossover distances on a straight 1D line, the smallest available coordinates must always be paired together.
3. Sorting both arrays and matching them index by index mathematically guarantees the absolute minimum network lag.

Approach

1. Sorting the Positions

Think of the data centers and servers as dots on a single number line. If we don't sort them, lines connecting centers to servers will cross over each other, creating unnecessary extra distance. By sorting both the center array and the destination array in ascending order, we naturally line them up from left to right.

2. Calculating the Total Lag

Once both arrays are sorted, the most optimal pairing is right in front of us. We simply iterate through the arrays and pair the $i$-th center with the $i$-th server. We calculate the absolute difference between their positions and add it to our running total.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long minLag(vector<int>& c, vector<int>& d) {
    sort(c.begin(), c.end());
    sort(d.begin(), d.end());
    
    long long res = 0;
    for (int i = 0; i < c.size(); i++) {
        res += abs((long long)c[i] - d[i]);
    }
    return res;
}

int main() {
    vector<int> c = {1, 2, 2};
    vector<int> d = {5, 2, 4};
    cout << minLag(c, d);
    return 0;
}