Find minimum time for irrecoverable password
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
A password is a string s of length n. A virus attacks positions in a 1-indexed order given by a permutation attackOrder[1..n]. At second t (1 <= t <= n), the character at position attackOrder[t] is replaced by a malicious character '*'. The password is irrecoverable once the number of substrings containing at least one '*' is >= m. Find the minimum time t after which the password becomes irrecoverable; if it is irrecoverable at the start, return 1. Implement findMinimumTime(password, attackOrder, m) and state the algorithm and its time and space complexity.
Quick Answer: This question evaluates string-processing skills, combinatorial counting of substrings, simulation of time-based state changes, and algorithmic complexity analysis.
Return the first attack time when the number of substrings containing at least one star reaches m.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('abc', [1,2,3], 4)
Expected Output: 2
Explanation: After two attacks, at least four substrings contain a star.
Input: ('abcd', [2,4,1,3], 7)
Expected Output: 2
Explanation: Segment splitting tracks recoverable substrings.
Input: ('abc', [1,2,3], 0)
Expected Output: 1
Explanation: Already irrecoverable threshold returns 1.
Hints
- Track intact segments between attacked positions.
- Substrings with a star equal total substrings minus all-clean substrings.