PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Microsoft
  • Coding & Algorithms
  • Software Engineer

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

  1. 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

  1. The inequalities reduce to max(abs(x), abs(y)) <= 2 * min(abs(x), abs(y)).
Last updated: Jun 27, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Return Top K Open Businesses - Microsoft (hard)
  • Implement Memory Allocation and In-Memory Records - Microsoft (medium)
  • Implement K-Means and Detect Divisible Subarrays - Microsoft (medium)
  • Sort Three Categories In Place - Microsoft (medium)
  • Retain Top K Elements - Microsoft (medium)