Validate password strength and repair
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates string-processing, constraint-satisfaction, and algorithm-design skills by requiring validation against multiple password rules and computation of the minimal edits (insert, delete, replace) needed for compliance.
Constraints
- 0 <= len(password) <= 10^5
- password consists of printable ASCII characters (letters, digits, symbols).
- Required character classes are lowercase [a-z], uppercase [A-Z], and digit [0-9]; symbols count toward length only.
- A 'consecutive repeat' is three or more identical characters in a row.
Examples
Input: ("",)
Expected Output: [False, 8]
Explanation: Empty string: too short. Need 8 insertions which also supply the 3 required character types, so min edits = max(8-0, 3) = 8.
Input: ("aA1bB2cC",)
Expected Output: [True, 0]
Explanation: Length 8, has lower/upper/digit, no triple repeats -> already compliant, 0 edits.
Input: ("a",)
Expected Output: [False, 7]
Explanation: Length 1, missing upper and digit. Need 7 insertions to reach length 8 (which can also add the 2 missing types). max(8-1, 2) = 7.
Input: ("aaa111",)
Expected Output: [False, 2]
Explanation: Length 6 (<8), missing uppercase. Insertions to reach length 8 also break the two triple runs and add the missing type: max(8-6, 1) = 2.
Input: ("1337C0d3",)
Expected Output: [True, 0]
Explanation: Length 8, has lower ('d'), upper ('C'), digit, no triple -> compliant, 0 edits.
Input: ("aaaAAA111bbb",)
Expected Output: [False, 4]
Explanation: Length 12 (in range). Four runs of length 3 -> 4 replacements; no missing types. max(0,4)=4.
Input: ("aaaaaaaaaaaaaaaaaaaaa",)
Expected Output: [False, 7]
Explanation: Length 21 (>20), all 'a': delete 1 to reach 20, missing upper+digit. Run 21%3==0 so the deletion removes one replacement; replacements on 20 chars = 6 (>=missing 2). 1 + 6 = 7.
Input: ("Abcdefg1",)
Expected Output: [True, 0]
Explanation: Length 8, lower/upper/digit present, no triple -> compliant, 0 edits.
Input: ("ABCDEFGH123IJKLMNOP456QRSTU",)
Expected Output: [False, 8]
Explanation: Length 27 (>20), no lowercase (missing 1), no triple runs. Delete 7 to reach 20; one replacement fixes the missing lowercase. 7 + max(1,0) = 8.
Input: ("password",)
Expected Output: [False, 2]
Explanation: Length 8, missing uppercase and digit, no triple. In-range so only replacements: max(missing=2, replace=0) = 2.
Hints
- First classify by length: under 8 (insert-dominated), 8..20 (replace-only), or over 20 (must delete down to 20).
- A run of L identical characters needs floor(L/3) replacements to break; a single replacement can also supply a missing character type, so the in-range answer is max(missing_types, sum of floor(L/3)).
- When len > 20, spend the forced deletions to remove replacements as cheaply as possible: a run with length % 3 == 0 loses a replacement after 1 deletion, % 3 == 1 after 2, % 3 == 2 after 3 — handle those buckets in that order.