PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Instacart
  • Coding & Algorithms
  • Software Engineer

Validate password strength and repair

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given a password policy—length between 8 and 20 characters; must include at least one lowercase letter, one uppercase letter, and one digit; and must not contain any character repeated three or more times consecutively—write a function that (a) validates whether an input string is compliant and (b) if not, returns the minimum number of edits (insert, delete, replace) needed to make it compliant along with one valid corrected password. Describe your algorithm, consider large inputs, and analyze time/space complexity.

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.

A password is **compliant** when ALL of the following hold: 1. Its length is between 8 and 20 characters (inclusive). 2. It contains at least one lowercase letter, at least one uppercase letter, and at least one digit. 3. No character is repeated three or more times **consecutively** (e.g. `aaa` is not allowed). Write `solution(password)` that returns a pair `[is_valid, min_edits]` where: - `is_valid` is `True` if `password` is already compliant, otherwise `False`. - `min_edits` is the **minimum number of single-character edits** — insert, delete, or replace — needed to transform `password` into a compliant one (0 when it is already compliant). A valid corrected password can always be produced alongside `min_edits` (see the worked explanations), but because many distinct repairs achieve the same minimum, only the deterministic `[is_valid, min_edits]` pair is graded. **Algorithm.** This is an adaptation of the classic *Strong Password Checker* greedy: - If `len < 8`: every insertion both lengthens the string and can break a run or add a missing character type, so the answer is `max(8 - len, missing_types)`. - If `8 <= len <= 20`: only replacements help. A run of `L` equal chars needs `L // 3` replacements to break, and a replacement can simultaneously satisfy a missing type, giving `max(missing_types, sum(L_i // 3))`. - If `len > 20`: you must delete `len - 20` characters. Spend those deletions greedily on runs first (`run % 3 == 0` saves a replacement per 1 deletion, `== 1` per 2, `== 2` per 3), then add `max(missing_types, remaining_replacements)`. Note in this problem `missing_types` is the count of the three required character classes that are absent. **Multi-language templates** return `[isValid, minEdits]` (the non-Python templates encode `isValid` as `1/0`).

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

  1. First classify by length: under 8 (insert-dominated), 8..20 (replace-only), or over 20 (must delete down to 20).
  2. 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)).
  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.
Last updated: Jun 25, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Fix the Broken Search Filter in a Book Catalog API - Instacart (medium)
  • Find Largest Adjacent Stock Price Change - Instacart (medium)
  • Implement an In-Memory File Storage System - Instacart (medium)
  • Decode an encoded string - Instacart (medium)
  • Evaluate an arithmetic expression - Instacart (medium)