Find earliest time password becomes irrecoverable
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given a password string of length n and an attack order array attackOrder[1..n], a permutation of 1..n. At second i (1-indexed), the virus replaces the character at position attackOrder[i] with a malicious character '*'. A substring is contiguous. The password becomes irrecoverable when the number of substrings containing at least one '*' is >= m. Find the minimum time t (1 <= t <= n) after which the password is irrecoverable. Special rule: if the password is considered irrecoverable at the start, report 1. Constraints: 1 <= n <= 8e5; password is lowercase letters; 1 <= attackOrder[i] <= n; 0 <= m <= n*(n+
1)/2.
Quick Answer: This question evaluates understanding of combinatorics, string processing, and algorithmic data structures for efficiently tracking dynamic intervals and counting contiguous substrings as characters are corrupted over time.
You are given a password string of length n and an array attack_order[1..n], a permutation of 1..n. At second i (1-indexed), the character at position attack_order[i] is replaced by '*'. A substring is contiguous. The password is irrecoverable when the number of substrings containing at least one '*' is at least m. Find the minimum t (1 <= t <= n) such that after t seconds the password is irrecoverable. Special rule: if m == 0, return 1.
Constraints
- 1 <= n <= 8e5
- password consists of lowercase English letters
- attack_order is a permutation of 1..n (1-indexed positions)
- 0 <= m <= n*(n+1)/2
- Return the minimal t in [1..n]; if m == 0, return 1
Hints
- The number of substrings containing '*' is non-decreasing over time; use binary search on t.
- For a fixed t, positions attacked by time t split the array into clean segments; substrings without '*' are the sum over segments of len*(len+1)/2.
- Precompute the attack time for each position to check any t in O(n).