Quick Overview

Given a server health log of 0s and 1s and a window length k, choose at most one block of exactly k consecutive entries to repair, setting every 0 inside it to 1, and report the longest stretch of consecutive 1s that can result. The problem checks linear-time string scanning and the difference between a fixed-length repair and flipping any k zeros.

Max Consecutive Uptime After Repairing One Window of Exactly k Log Entries

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

A server's health log is a string of `0`s and `1`s, one character per time step: `1` means the server was up and running normally, and `0` means it had failed. You may run at most one maintenance operation, which picks a contiguous stretch of exactly `k` consecutive entries and sets every `0` in that stretch to `1` (entries that are already `1` are unchanged). Return the greatest possible length of a run of consecutive `1`s in the log after you choose the stretch optimally, or decide not to run the operation. The stretch length is fixed at exactly `k`. The operation does not let you flip up to `k` arbitrary zeros; it repairs only the zeros inside one window of `k` adjacent entries. ### Function Signature ```python def max_uptime_after_one_repair(log: str, k: int) -> int: ``` ### Rules - Positions are 0-indexed. A repair starting at index `s` must satisfy `0 <= s` and `s + k <= len(log)`, and it covers positions `s, s + 1, ..., s + k - 1`. - At most one repair is allowed. - Return one integer: the length of the longest run of consecutive `1`s in the final log. ### Constraints - `1 <= len(log) <= 10^5` - `1 <= k <= len(log)` - `log` contains only the characters `'0'` and `'1'`. ### Examples **Example 1** ```text Input: log = "0110100", k = 3 Output: 5 ``` Repairing positions 3 to 5 gives `"0111110"`, with a run of five `1`s at positions 1 to 5. **Example 2** ```text Input: log = "01010", k = 2 Output: 3 ``` The best windows are positions 1 to 2 or positions 2 to 3; both give `"01110"`. Fixing the zeros at positions 0 and 2 would give `"11110"` with a run of 4, but those two zeros do not lie inside one window of length 2, so that is not allowed. **Example 3** ```text Input: log = "0000", k = 1 Output: 1 ``` A window of length 1 repairs a single entry, producing one isolated `1`.

Overview: Given a server health log of 0s and 1s and a window length k, choose at most one block of exactly k consecutive entries to repair, setting every 0 inside it to 1, and report the longest stretch of consecutive 1s that can result. The problem checks linear-time string scanning and the difference between a fixed-length repair and flipping any k zeros.

Read the full Amazon Software Engineer interview experience this question came from

A server's health log is a string `log` of `'0'` and `'1'` characters, one character per time step: `'1'` means the server was up and running normally at that step, and `'0'` means it had failed. You may run at most one maintenance operation. The operation picks a contiguous stretch of exactly `k` consecutive entries and sets every `'0'` in that stretch to `'1'`; entries that are already `'1'` are unchanged. The stretch length is fixed at exactly `k`: the operation does not let you flip up to `k` arbitrary zeros, it repairs only the zeros inside one window of `k` adjacent entries. Positions are 0-indexed. A repair starting at index `s` must satisfy `0 <= s` and `s + k <= len(log)`, and it covers positions `s, s + 1, ..., s + k - 1`. Implement `max_uptime_after_one_repair(log, k)`. Return one integer: the greatest possible length of a run of consecutive `'1'`s in the final log after you choose the stretch optimally, or decide not to run the operation. ### Example 1 Input: `log = "0110100", k = 3` Output: `5` Repairing positions 3 to 5 gives `"0111110"`, with a run of five `1`s at positions 1 to 5. ### Example 2 Input: `log = "01010", k = 2` Output: `3` The best windows are positions 1 to 2 or positions 2 to 3; both give `"01110"`. Fixing the zeros at positions 0 and 2 would give `"11110"` with a run of 4, but those two zeros do not lie inside one window of length 2, so that is not allowed. ### Constraints - `1 <= len(log) <= 10^5` - `1 <= k <= len(log)` - `log` contains only the characters `'0'` and `'1'`. - The answer is at most `len(log) <= 10^5`, so no value exceeds `2^31 - 1` and a 32-bit `int` suffices in every language.

Constraints

  • 1 <= len(log) <= 10^5
  • 1 <= k <= len(log)
  • log contains only the characters '0' and '1'.
  • The answer is at most len(log) <= 10^5, so no value exceeds 2^31 - 1.

Examples

Input: ('0', 1)

Expected Output: 1

Explanation: Minimum valid input: a single failed entry; the only window repairs it, giving a run of 1.

Input: ('1', 1)

Expected Output: 1

Explanation: Minimum valid input: a single healthy entry; the repair changes nothing and the run is 1.

Hints

  1. The repaired stretch always has exactly k entries, so two zeros can be fixed together only if they fit inside one window of length k (see Example 2).
  2. Turning 0s into 1s never shortens a run, so running the operation is never worse than skipping it.
  3. For one fixed start s, think about which 1s end up in the same run as the repaired stretch.

Loading coding console...

Show the approach

Approach

Algorithm: for a repair starting at s, the run of 1s that contains the repaired window is made of the 1s directly to its left (the run ending at s - 1), the k repaired entries, and the 1s directly to its right (the run starting at s + k). Precompute, from right to left, ones_from[i] = length of the run of 1s starting at i, with ones_from[len(log)] = 0. Then sweep s from 0 to len(log) - k while maintaining ones_before = length of the run of 1s ending at s - 1 (0 for s = 0), and take the maximum of ones_before + k + ones_from[s + k].

Invariant: at the top of iteration s, ones_before equals the number of consecutive 1s ending at position s - 1 in the original log; it is reset to 0 at each 0 and incremented at each 1.

Correctness: the repair only turns 0s into 1s, so it never shortens any run, and running it is never worse than skipping it. In the repaired log, a run that does not contain the window is an original run. An original run of length m >= k contains the legal window that starts at its first position, and the joined run for that window has length at least m; an original run of length m < k is shorter than every joined run, which is at least k. Hence the best joined run is the overall answer. Because ones_before and ones_from count only 1s outside the window, a window that lies inside an existing run is not double counted.

Edge cases: k = len(log) leaves exactly one window and the answer len(log); an all-0 log gives k; an all-1 log gives len(log); a length-1 log gives 1. The answer is at most 10^5, so 32-bit integers suffice.

Time complexity:
O(n), where n = len(log)
Space complexity:
O(n)