Frontend School

Max Contiguous Server Block

DSA
medium

Max Contiguous Server Block

Medium
Binary Search
Arrays
Sliding Window
Algorithms

Overview

Gupshup manages a vast network of servers that are logically arranged in a linear fashion. For an upcoming feature rollout, engineers need to allocate a contiguous block of servers. To ensure system stability and optimize resource utilization during deployment, it's crucial to identify the largest possible contiguous block of servers that can be activated without exceeding a specified total load tolerance.

What you need to do / Task

Implement a function findMaxContiguousServers that determines the maximum length of a contiguous sub-array of servers whose sum of loads does not exceed a given maxAllowedLoad.

Input & output

Your function will receive the following parameters:

  • serverLoads: An array of non-negative integers (number[]), where serverLoads[i] represents the load of the i-th server.
  • maxAllowedLoad: A non-negative integer (number), representing the maximum total load allowed for any contiguous block.

The function should return a number representing the maximum possible length of a contiguous block of servers satisfying the condition. If no block (even a single server) can satisfy the condition, return 0.

Clarifications

  • If the serverLoads array is empty, the function should return 0.
  • All serverLoads[i] values are non-negative.
  • The maxAllowedLoad is also non-negative.

Examples

1

Example 1

Input:

serverLoads = [1, 2, 3, 4, 5], maxAllowedLoad = 10

Output:

4

Note:

The contiguous block [1,2,3,4] has a total load of 10, which is within the maxAllowedLoad. No block of length 5 satisfies the condition (e.g., [1,2,3,4,5] sums to 15).

2

Example 2

Input:

serverLoads = [5, 10, 1, 7, 2], maxAllowedLoad = 8

Output:

2

Note:

The contiguous block [1,7] has a total load of 8, which is within the maxAllowedLoad. No block of length 3 or more satisfies the condition (e.g., [1,7,2] sums to 10).

3

Example 3

Input:

serverLoads = [100, 200, 300], maxAllowedLoad = 50

Output:

0

Note:

Even a single server's load (e.g., 100) exceeds the maxAllowedLoad of 50. Therefore, no valid contiguous block can be formed.

Constraints

Constraints & assumptions

  • 1 <= serverLoads.length <= 10^5
  • 0 <= serverLoads[i] <= 10^9
  • 0 <= maxAllowedLoad <= 10^14
  • The sum of loads for a block of servers can be large, but will fit within standard number type in JavaScript/TypeScript (up to Number.MAX_SAFE_INTEGER).
  • Expected time complexity: O(N log N), where N is the length of serverLoads.
  • Expected space complexity: O(1) (excluding input/output storage).

What interviewers evaluate

  • Correct application of binary search on the answer space (possible lengths).
  • Efficient implementation of the helper function to check feasibility for a given length, typically using a sliding window.
  • Thorough handling of edge cases, such as an empty input array, maxAllowedLoad being zero, or no valid block found.
  • Code clarity, modularity, and adherence to specified time and space complexity requirements.

Loading editor...