Start from brute force
The obvious approach splits the text on whitespace, tests each token against each pattern with a full match, swaps matching tokens for their placeholder, and joins the tokens back with single spaces. It works for values that stand alone between spaces, and it costs O(n · p) time for p patterns and O(n) space for the token list. But it is wrong in exactly the ways that leak data: a space-grouped card such as 4111 1111 1111 1111 becomes four tokens, none of which is a card; (joe@x.io) carries its parentheses, so the full match fails; and joining with single spaces silently rewrites newlines and tabs in the text that was supposed to pass through unchanged.
The approach
Each kind of PII has a fixed textual shape, so a regular expression can find every occurrence anywhere in the string, in one left-to-right scan per pattern, and replace just the match while keeping the text around it. The \b word boundaries around the SSN, card and phone patterns anchor them to whole runs of digits, so a fragment of a longer number is not mistaken for one. The order that matters is email first: an address such as 123-45-6789@x.com contains a run of digits shaped exactly like an SSN, and replacing those digits first would leave the domain behind. With these patterns the SSN, card and phone shapes cannot overlap one another, so their relative order is a safety habit rather than a requirement.
The reference solution is four reassignments: text = re.sub(pattern, placeholder, text) for email, SSN, card and phone, then return text. The invariant after each pass is that every match of that pattern has become its placeholder, and because [EMAIL] and the others contain no digits and no @, later passes cannot match inside them.
Walk through an example
Trace the first example through the four passes, in the order the reference applies them.
| step | pass | matches | text afterward |
|---|
| 1 | input | — | mail a@b.com ssn 123-45-6789 ph 555-123-4567 |
| 2 | email | a@b.com | mail [EMAIL] ssn 123-45-6789 ph 555-123-4567 |
| 3 | SSN | 123-45-6789 | mail [EMAIL] ssn [SSN] ph 555-123-4567 |
| 4 | card | nothing: no 16-digit run | unchanged |
| 5 | phone | 555-123-4567 | mail [EMAIL] ssn [SSN] ph [PHONE] |
Complexity
Optimal: four re.sub passes, each O(n) on ordinary text, and O(n) space for the rebuilt strings. The email pattern can backtrack: on a long run of letters and digits with no @, every start position rescans the run, which is O(n²). Brute force (split on whitespace, test each token): O(n · p) time and O(n) space, but it misses values that span or touch other characters.
Edge cases to test
- Email first matters:
"123-45-6789@x.com" → "[EMAIL]", but running the SSN pass first gives "[SSN]@x.com", which leaks the domain. - Digits glued to letters:
"SSN123-45-6789" and "_123-45-6789" come back unchanged, because \b treats letters, digits and underscore alike, so there is no boundary before the 1. "ID:123-45-6789" → "ID:[SSN]". - Formats the patterns do not cover pass straight through:
"(555) 123-4567", "5551234567", the 15-digit Amex layout "3782 822463 10005" and a dot-grouped card are all returned unchanged. - A false positive:
"order 1234567890123456" → "order [CARD]", because nothing checks the Luhn digit. For redaction that is usually the safer error. - Unicode digits: Python’s
\d matches Arabic-Indic digits, so "١٢٣-٤٥-٦٧٨٩" becomes "[SSN]", while JavaScript’s \d is ASCII-only and leaves it unchanged. - Punctuation after an address survives:
"mail joe@x.io." → "mail [EMAIL].", because the domain part backtracks until the final label is letters only.
Common mistakes
- Over-broad regexes that redact things that are not PII (false positives).
- Missing formats — international phone numbers, obfuscated emails, spaced-out card numbers.
- Redacting after the data has already been logged instead of before it leaves your boundary.
- Running a digit pattern before the email pattern, so part of an address is replaced and the rest of it leaks.
Follow-ups an interviewer asks next
- How would you cut false positives on card numbers?
- Validate each candidate with the Luhn checksum before replacing it: starting with the second digit from the right, double every other digit, subtract 9 from any result above 9, and add up all the digits; a valid number totals a multiple of 10. In Python, pass a function as the replacement to
re.sub and return [CARD] only when the check passes, or the original text otherwise. - How do you redact names and addresses, which have no fixed format?
- Patterns cannot find them. Use a named-entity recognition model, or a PII detection library such as Microsoft Presidio, which combines pattern-based recognizers, context words and NER models, each with a confidence score. Run it alongside the regexes rather than instead of them: regexes are exact and fast for structured identifiers, and the model covers the free-form ones.
- Analysts still need to join records on the redacted email. What changes?
- Replace each value with a stable pseudonym instead of one fixed token, such as
[EMAIL_3f2a] derived from a keyed hash (an HMAC) of the value. The same address always maps to the same token, so joins and counts still work, and keeping the key inside your boundary stops anyone from reversing tokens by hashing a list of known addresses. - How would you make it fast and safe on large inputs?
- Combine the four patterns into one alternation with named groups and a replacement function, so the text is scanned once instead of four times; put the email alternative first, because at each position the first alternative that matches wins. Then bound the backtracking: cap the local part, for example at
{1,64} characters, so a long run of letters with no @ cannot make the scan quadratic.
Where this shows up
PII redaction is a compliance necessity wherever user data flows into logs, analytics, or LLM prompts — you scrub before the data crosses your trust boundary. It is especially critical when feeding user text to third-party AI tools, which is exactly the “never leak customer data” rule from working with AI safely.
Reference solution
Reference solution — Python
import re
def redact(text):
text = re.sub(r"[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}", "[EMAIL]", text)
text = re.sub(r"\b\d{3}-\d{2}-\d{4}\b", "[SSN]", text)
text = re.sub(r"\b\d{4}[- ]?\d{4}[- ]?\d{4}[- ]?\d{4}\b", "[CARD]", text)
text = re.sub(r"\b\d{3}[-.]\d{3}[-.]\d{4}\b", "[PHONE]", text)
return text
print(redact("mail a@b.com ssn 123-45-6789 ph 555-123-4567")) # -> mail [EMAIL] ssn [SSN] ph [PHONE]
Reference solution — TypeScript
function redact(text: string): string {
text = text.replace(/[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}/g, "[EMAIL]");
text = text.replace(/\b\d{3}-\d{2}-\d{4}\b/g, "[SSN]");
text = text.replace(/\b\d{4}[- ]?\d{4}[- ]?\d{4}[- ]?\d{4}\b/g, "[CARD]");
text = text.replace(/\b\d{3}[-.]\d{3}[-.]\d{4}\b/g, "[PHONE]");
return text;
}
console.log(redact("mail a@b.com ssn 123-45-6789 ph 555-123-4567")); // -> mail [EMAIL] ssn [SSN] ph [PHONE]