Katkat
Back

Find Longest Activatable Server Streak

AmazonSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to use the sliding window technique to find the longest contiguous subarray that satisfies a specific count-based constraint.

Problem Statement

You are monitoring a cluster of n servers, represented by an array status where status[i] = 1 indicates an active server and status[i] = 0 indicates an inactive one.

You are allowed to perform at most k "maintenance overrides," which allow you to flip the status of an inactive server (change 0 to 1). Your goal is to find the length of the longest contiguous subarray of active servers you can create after performing at most k flips.

Function Signature

def longest_active_streak(status: List[int], k: int) -> int:

Constraints

  • 1 <= len(status) <= 10^5
  • status[i] is either 0 or 1.
  • 0 <= k <= len(status)

Example 1

Input: status = [1, 0, 1, 0, 1, 1], k = 1 Output: 4 Explanation: Flipping the 0 at index 1 results in [1, 1, 1, 0, 1, 1]. The longest streak is 3. Flipping the 0 at index 3 results in [1, 0, 1, 1, 1, 1]. The longest streak is 4.

Example 2

Input: status = [0, 0, 1, 1, 0, 0], k = 2 Output: 4 Explanation: Flipping both 0s at the start or end results in a streak of 2. Flipping the two 0s in the middle indices results in [0, 1, 1, 1, 1, 0], length 4.

Edge Cases

  • If k is equal to the number of zeros, the answer should be the total length of the array.
  • If the array contains no zeros, the answer is the total length of the array.

Hints

Hint 1

Transform the problem into finding the longest subarray containing at most k zeros.

Hint 2

Use a two-pointer approach (sliding window) where you maintain a window [left, right] and count the number of zeros inside it.

Hint 3

Whenever the zero count exceeds k, increment the 'left' pointer and update the count until the number of zeros is once again less than or equal to k.

Follow-up questions

  • How would you modify your solution if the input was a stream of server statuses coming in one by one?
  • What is the time and space complexity of your solution, and can you optimize the space complexity to O(1)?
  • If instead of flipping zeros, you could only flip servers in a specific range of length `m`, how would that change your approach?