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

IntermediatePrefer not to say

May 2026

Summary

Amazon SWE online assessment, one algorithmic problem about simulating a malware attack on a password string. Pretty involved for an OA, not your typical easy array question.

Questions Asked (1)

Given a password string, a permutation array defining the order in which characters get corrupted to '', and an integer threshold m, find the minimum number of seconds before the password becomes 'unrecoverable' (i.e. the number of distinct substrings containing at least one '' reaches or exceeds m). Return 1 if it's already unrecoverable from the start.

Algorithms & Data Structures

Author's notes

This one took me a while to even parse.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

This is a binary search on the answer combined with an efficient method to count distinct substrings containing at least one '*'. For a given time t, mark the first t corrupted positions, then count distinct substrings that include at least one '*' using a suffix automaton or suffix array with LCP, and compare to m. Binary search the smallest t where the count >= m, handling the initial check separately.

Pro tip: Clarify that 'distinct substrings' means distinct strings, not occurrences, and that the count can be computed as total distinct substrings minus distinct substrings with no '*'. This reduces the problem to counting substrings avoiding a set of forbidden positions, which can be done with a suffix automaton by resetting the last state at each forbidden character.

1. Clarify the problem and edge cases

Confirm that 'unrecoverable' means the number of distinct substrings containing at least one '*' is >= m. Check if the initial string already meets this condition (return 1) and note that if m is 0, answer is 0.

2. Design a feasibility check for a given time t

Given t, mark the first t positions from the permutation as '*'. Count the number of distinct substrings that contain at least one '*'. This can be computed as total distinct substrings of the current string minus distinct substrings that contain no '*' (i.e., substrings entirely within segments of non-'*' characters).

3. Implement efficient counting of distinct substrings

Use a suffix automaton or suffix array to compute total distinct substrings. For substrings without '*', split the string by '*' and sum distinct substrings of each segment. Alternatively, build a suffix automaton and reset the last state at each '*' to count only substrings avoiding '*'.

4. Binary search the minimum time

Binary search t from 1 to n (or 0 to n-1 depending on indexing). For each mid, run the feasibility check. If count >= m, search left; else search right. Return the smallest t that satisfies the condition.

5. Analyze complexity and optimize

Each feasibility check takes O(n log n) or O(n) with suffix automaton. Binary search adds a log n factor, giving O(n log^2 n) or O(n log n). Discuss potential optimizations like incremental updates or using a segment tree to maintain counts.

Key Points to Mention

Binary search on the answer (time t) to find the minimum t where the condition holds.
Counting distinct substrings containing at least one '*' as total distinct substrings minus distinct substrings with no '*'.
Using a suffix automaton or suffix array with LCP to efficiently count distinct substrings.
Handling the initial check: if the original string already has >= m distinct substrings with '*', return 1.
Time complexity: O(n log n) per check, O(n log^2 n) overall, and space complexity O(n).
Edge cases: m=0, m larger than total possible substrings, and all characters corrupted.

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