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.

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.

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.

What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Solve load balancing and perfect pairs | Microsoft Interview Question

Q: Solve load balancing and perfect pairs

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.

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.

Q: What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Microsoft.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

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.

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

Quick Overview

Comments (0)

Solve load balancing and perfect pairs

Quick Overview

Comments (0)