Katkat
Back

Solve load balancing and perfect pairs

MicrosoftSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

  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.