Solve load balancing and perfect pairs
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
1) 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).
2) 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, −
3) and (5, −
3). Discuss optimizations to avoid TLE on large inputs.
Quick Answer: This question evaluates algorithm design, correctness proof, and complexity analysis skills by combining a contiguous partitioning load‑balancing optimization with a combinatorial/number‑theoretic pair‑counting problem.
Contiguous Load Balancing
Partition ordered tasks across n servers to minimize the maximum contiguous load.
Constraints
- Each task is assigned to exactly one contiguous server partition
Examples
Input: (3, [4, 3, 2, 2, 2, 6])
Expected Output: 7
Explanation: Prompt example.
Input: (1, [1, 2, 3])
Expected Output: 6
Explanation: One server gets all tasks.
Input: (5, [2, 7, 1])
Expected Output: 7
Explanation: At least as many servers as tasks.
Hints
- Binary-search the maximum load and greedily count required partitions.
Count Perfect Pairs
Count index pairs satisfying the perfect-pair inequalities.
Constraints
- Pairs are counted by index
Examples
Input: ([2, 5, -3],)
Expected Output: 2
Explanation: Prompt validation has two perfect pairs.
Input: ([0, 0, 1],)
Expected Output: 1
Explanation: Zero pairs only with zero.
Input: ([1, 2, 3, 4],)
Expected Output: 4
Explanation: Count by absolute values.
Input: ([-1, 1],)
Expected Output: 1
Explanation: Opposite signs can still be perfect.
Hints
- The inequalities reduce to max(abs(x), abs(y)) <= 2 * min(abs(x), abs(y)).