← Google Interview Insights

Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Google SWE coding round, one problem the whole session. Binary search on answer type, which I've seen before but always fumble the feasibility check under pressure.

Questions Asked (1)

Q1

Given an array of task workloads and a target time threshold T, find the minimum number of workers needed so that you can partition the array into contiguous segments where no segment's sum exceeds T.

Algorithms & Data Structures
Author's notes

I recognized the binary search on answer pattern pretty quickly, which felt good.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then propose a greedy partitioning approach with binary search on the number of workers. Explain that for a fixed number of workers, you can check feasibility by greedily assigning tasks to workers while keeping each segment sum ≤ T, and then binary search for the minimum feasible workers.

Pro tip: Mention that the greedy check is optimal because any feasible partition with k workers can be transformed into the greedy one without increasing the number of workers, and highlight that binary search reduces the time complexity to O(n log n) or O(n log m) where m is the sum of workloads.

1. Clarify constraints and edge cases

Ask about input size, whether T can be smaller than any task, and if tasks are positive. Discuss edge cases like empty array, single task, or T insufficient.

2. Define feasibility check

For a given number of workers k, determine if partitioning into k contiguous segments with each sum ≤ T is possible. Use a greedy scan: accumulate tasks until adding the next would exceed T, then start a new segment.

3. Binary search on workers

The minimum workers is monotonic: if k works, any k' > k also works. Binary search k between 1 and n (or sum/T) to find the smallest feasible k.

4. Analyze complexity and optimize

The greedy check is O(n). Binary search adds O(log n) factor, giving O(n log n) time and O(1) extra space. Mention that if T is large, the upper bound can be tightened.

5. Test with examples

Walk through a small example to validate the approach, e.g., workloads [1,2,3,4,5], T=6. Show how binary search finds the minimum workers.

Key Points to Mention

  • Greedy partitioning is optimal for a fixed number of workers because it minimizes the number of segments used.
  • Binary search is applicable due to monotonicity: if k workers suffice, k+1 also suffices.
  • Time complexity: O(n log n) with binary search, or O(n log(sum)) if binary searching on sum.
  • Space complexity: O(1) extra space for the greedy check.
  • Edge cases: T < max(task) implies impossible; empty array requires 0 workers.
  • Alternative: dynamic programming is possible but less efficient (O(n^2) or O(nk)).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.