Solve load balancing and perfect pairs

Q: Solve load balancing and perfect pairs

This is a Coding & Algorithms interview question from Microsoft for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Contiguous load balancing: You have n identical resources (servers) and m ordered tasks with processing times burstTime[0..m-1]. Each server must be assigned a contiguous subarray of tasks; every task must be assigned to exactly one server; the servers' partitions cover the array in order. Define the load of a server as the sum of its assigned tasks. Find the minimal possible value of the maximum server load over all valid partitions. Provide an algorithm, prove correctness, analyze time and space complexity, and discuss trade-offs (e.g., binary search on the answer with a feasibility check vs dynamic programming). Work through the example n=3, m=6, burstTime=[4,3,2,2,2,6] where an optimal maximum load is 7. Consider edge cases (n≥m, n=1, very large m).
Counting perfect pairs: A pair (x, y) of integers is perfect if min(|x−y|, |x+y|) ≤ min(|x|, |y|) and max(|x−y|, |x+y|) ≥ max(|x|, |y|). Given an array arr of length n, count pairs (i, j) with 0 ≤ i < j < n such that (arr[i], arr[j]) is perfect. Design an algorithm faster than O(n^ 2): characterize when two numbers form a perfect pair, handle zeros and duplicates correctly, and analyze time and space complexity. Validate your approach on arr = [2, 5, −3], which has two perfect pairs: (2, −
and (5, − 3). Discuss optimizations to avoid TLE on large inputs.

Solve load balancing and perfect pairs

Comments (0)