Site Message

Only Premium Users can view the Question

Question: Amazon, Online Assessment Questions | An AWS Client | Amazon Stock Prize | 10th September 2023
1
Entering edit mode

ADD COMMENTlink 22 months ago Delta 3.0k
0
Entering edit mode

can you specify your college?

ADD COMMENTlink 22 months ago rahul • 0
0
Entering edit mode

Minimize Total Network Lag Between Data Centers and Servers

Approach / Steps:

  1. Understand the Goal:
    You are given n data centers and n servers, placed on a 1D number line.
    You need to pair each data center with exactly one server such that the total lag (absolute difference) is minimized.

  2. Key Insight:
    This is a classic case of minimum sum of absolute differences between two arrays with 1:1 mapping.
    To minimize the sum:
    ➤ Sort both arrays
    ➤ Pair i-th element from center[] with i-th element from destination[].

  3. Why this works?
    Based on the Rearrangement Inequality, pairing sorted elements minimizes the sum of absolute differences.

  4. Steps:

    • Read input arrays center[] and destination[].

    • Sort both arrays.

    • For each index i from 0 to n-1, compute abs(center[i] - destination[i]).

    • Sum up all those values and print the result.

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> d_cen(n), des(n);

    for (int i = 0; i < n; i++) cin >> d_cen[i];

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) cin >> des[i];

    sort(d_cen.begin(), d_cen.end());
    sort(des.begin(), des.end());

    long long totalLag = 0;
    for (int i = 0; i < n; i++) {
        totalLag += abs(d_cen[i] - des[i]);
    }

    cout << totalLag << endl;
}

Time Complexity (TC):

  • Sorting both arrays: O(n log n)

  • Computing lag: O(n)

  • Total TC = O(n log n)


Space Complexity (SC):

  • Using O(n) space for two arrays.

  • Total SC = O(n)

ADD COMMENTlink 8 days ago Suryansh Rishit • 0
0
Entering edit mode

K-Spike (Problem 2)

Approach

The key insight is to efficiently count elements smaller than each array element in two ranges:

  1. Left range: For each index i, count elements in [0, i-1] that are smaller than arr[i]
  2. Right range: For each index i, count elements in [i+1, n-1] that are smaller than arr[i]

Algorithm Steps:

  1. Process left to right: Use a multiset to maintain elements seen so far. For each position i:
    • Count elements in multiset that are smaller than arr[i] using lower_bound()
    • Store this count in left[i]
    • Insert arr[i] into multiset
  2. Process right to left: Clear multiset and repeat the process in reverse:
    • For each position i from n-1 to 0, count smaller elements in multiset
    • Store this count in right[i]
    • Insert arr[i] into multiset
  3. Count k-Spikes: For each index i, check if both left[i] ≥ k and right[i] ≥ k
#include<bits/stdc++.h>

using namespace std;


int main(){

    int n;
    cin >> n;
    vector<int> arr(n);

    for(int i = 0 ; i < n;i++){
        cin >> arr[i];
    }
    multiset<int> s;
    int k;
    cin >> k;
    vector<int> left(n,0),right(n,0);
 
    for (int i = 0; i < n; ++i) {
        left[i] = distance(s.begin(), s.lower_bound(arr[i]));
        s.insert(arr[i]);
    }

    s.clear();  
 
    for (int i = n - 1; i >= 0; --i) {
        right[i] = distance(s.begin(), s.lower_bound(arr[i]));
        s.insert(arr[i]);
    }
 
    int cnt = 0;
    for (int i = k; i < n-k; ++i) {
        cout << arr[i] << endl;
        cout << left[i] << "  " << right[i] << endl;
        if (left[i] >= k && right[i] >= k)
            cnt++;
    }
    cout << cnt << endl;

}
 

Time Complexity (TC):

O(n log n) - Two passes through array with multiset insert and lower_bound operations

Space Complexity (SC):

O(n) - For multiset, left array, right array, and input storage

ADD COMMENTlink 8 days ago Suryansh Rishit • 0

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts