Amazon·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

Jun 2026

Summary

Amazon OA for a SWE role. One problem, string manipulation with some security flavor baked in. The problem statement was dense and I spent way too long just parsing what 'irrecoverable' even meant before writing a single line.

Questions Asked (1)

Given a password string and an attack order permutation, a virus replaces characters with a special character one per second following the permutation. A password becomes irrecoverable when the number of substrings containing at least one corrupted character reaches or exceeds a given threshold m. Find the minimum time (in seconds) after which the password becomes irrecoverable.

Algorithms & Data Structures

Author's notes

The problem description was a wall of text and the example image they referenced was blurry so I genuinely wasn't sure what the corrupted character was supposed to be.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a monotonic predicate: after t seconds, the number of substrings containing at least one corrupted character is non-decreasing. Use binary search on t (from 0 to n) and for each t, efficiently compute the count of corrupted substrings using the positions of corrupted characters. The minimum t where the count >= m is the answer.

Pro tip: Clarify that 'substrings containing at least one corrupted character' means any contiguous substring that includes at least one corrupted index. Also, mention that the total number of substrings is n*(n+1)/2, so if m exceeds that, it's impossible.

1. Understand the problem and define the predicate

Restate the problem: given a permutation of indices, after t seconds the first t indices in the permutation are corrupted. Define f(t) = number of substrings containing at least one corrupted character. The password becomes irrecoverable when f(t) >= m. Since f(t) is non-decreasing, we can binary search for the smallest t.

2. Design an efficient way to compute f(t)

For a given set of corrupted positions, the number of substrings with at least one corrupted character equals total substrings minus substrings with no corrupted characters. Substrings with no corrupted characters are those entirely within gaps between corrupted positions (including ends). Compute gap lengths and sum gap*(gap+1)/2.

3. Implement binary search

Binary search t in [0, n]. For each mid, compute f(mid) using the gap method. If f(mid) >= m, search left; else search right. Return the smallest t that satisfies the condition, or -1 if even t=n does not reach m.

4. Analyze complexity and edge cases

Computing f(t) takes O(n) time by scanning the string and tracking gaps. Binary search adds O(log n) factor, giving O(n log n) overall. Handle edge cases: m=0 (answer 0), m > total substrings (answer -1), and n=1.

5. Test with examples and explain

Walk through a small example (e.g., password 'abc', permutation [1,0,2], m=3) to verify the approach. Explain how the gap method works and why binary search is valid due to monotonicity.

Key Points to Mention

Monotonicity of the predicate: as more characters are corrupted, the number of substrings containing at least one corrupted character never decreases.
Total substrings formula: n*(n+1)/2, and the complement method to count corrupted substrings.
Gap method: substrings with no corrupted characters are exactly those within contiguous segments of uncorrupted characters.
Binary search on time t from 0 to n, with O(n) check per step, leading to O(n log n) time complexity.
Edge cases: m=0, m greater than total substrings, and n=1.
Space complexity: O(n) to store the permutation and track corrupted positions.

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