Implement Luhn-based card validation and inference
Company: Stripe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
##### Question
Implement a set of utilities for credit-card validation and inference using the Luhn checksum algorithm and standard brand patterns.
**Brand patterns:**
- **VISA** — 16 digits, starts with `4`
- **MASTERCARD** — 16 digits, starts with `51`, `52`, `53`, `54`, or `55`
- **AMEX** — 15 digits, starts with `34` or `37`
**Tasks:**
1. Given a digit-only card-number string, return whether it passes the Luhn checksum and, if valid, which brand it belongs to. Possible outputs: `["INVALID_CHECKSUM", "VISA", "MASTERCARD", "AMEX"]`.
2. Extend task 1 so that a number passing the Luhn check but matching none of the three known brand patterns is labeled `"UNKNOWN"`.
3. Allow the input to contain `*` wildcards, each standing for any single digit (e.g., `"****424242424242"`). Return the count of possible valid card numbers per brand, formatted as a list of `"BRAND,count"` pairs (e.g., `["VISA,1", "MASTERCARD,10"]`). A single pattern may be consistent with more than one brand, so report a count for every brand it could represent. Note: once a brand is fixed, the number of valid completions equals `10^(number_of_asterisks - 1)`, because Luhn fixes one degree of freedom.
4. Error-correction: given an observed string whose trailing `?` indicates that exactly one error occurred to the preceding digits — one of {changed digit, removed digit, added digit, or transposition of two adjacent digits} (e.g., `"4333220284765319?"`) — enumerate every original card number (and its brand) that was valid before the error and that could have produced the observed string.
Overview: A Stripe software-engineer take-home that builds up a credit-card validation suite using the Luhn checksum and VISA/MASTERCARD/AMEX brand patterns. It progresses from exact validation and brand identification to an UNKNOWN fallback, analytic wildcard counting per brand, and single-error correction that enumerates all valid original numbers.
Luhn Card Validation + Brand Identification
Given a digit-only card-number string, return whether it passes the Luhn checksum and, if it passes, which of the three known brands it belongs to.
Brand patterns:
- VISA: 16 digits, starts with 4
- MASTERCARD: 16 digits, starts with 51, 52, 53, 54, or 55
- AMEX: 15 digits, starts with 34 or 37
Luhn checksum: walking the digits right-to-left, double every second digit; if a doubled value exceeds 9, subtract 9. The number is valid iff the total is divisible by 10.
Return one of: "INVALID_CHECKSUM", "VISA", "MASTERCARD", "AMEX". A number that fails Luhn, OR passes Luhn but matches none of the three brand patterns, returns "INVALID_CHECKSUM" in this task.
Constraints
- Input contains only ASCII digit characters 0-9.
- Length is not guaranteed to be 15 or 16; non-matching lengths simply fail the brand check.
- Empty string is Luhn-valid (sum 0) but matches no brand -> INVALID_CHECKSUM.
Examples
Input: ('4242424242424242',)
Expected Output: 'VISA'
Explanation: 16 digits, starts with 4, Luhn-valid -> VISA (a real Visa test card).
Input: ('5555555555554444',)
Expected Output: 'MASTERCARD'
Explanation: 16 digits, starts with 55, Luhn-valid -> MASTERCARD.
Hints
- Write a reusable luhn_ok(t) helper first; tasks 2-4 all reuse it.
- Process digits right-to-left and double every second one, subtracting 9 when the doubled digit exceeds 9.
- Brand identification only happens AFTER Luhn passes. A Luhn-valid number with an unknown prefix/length is still INVALID_CHECKSUM in this first task.
Card Validation with UNKNOWN Fallback
Extend the previous classifier: a number that PASSES the Luhn checksum but matches none of the three known brand patterns (VISA / MASTERCARD / AMEX) should be labeled "UNKNOWN" rather than rejected.
Return one of: "INVALID_CHECKSUM", "VISA", "MASTERCARD", "AMEX", "UNKNOWN".
- Fails Luhn -> "INVALID_CHECKSUM".
- Passes Luhn and matches a brand -> that brand.
- Passes Luhn but matches no brand -> "UNKNOWN".
Constraints
- Input contains only ASCII digit characters 0-9.
- The only behavioral change from task 1 is the final fallthrough: UNKNOWN instead of INVALID_CHECKSUM when Luhn passes but no brand matches.
Examples
Input: ('4242424242424242',)
Expected Output: 'VISA'
Explanation: Brand match takes precedence over the UNKNOWN fallback.
Input: ('5555555555554444',)
Expected Output: 'MASTERCARD'
Explanation: Starts with 55, 16 digits, Luhn-valid -> MASTERCARD.
Hints
- This is task 1 with a single line changed: the final return becomes 'UNKNOWN' instead of 'INVALID_CHECKSUM'.
- INVALID_CHECKSUM is reserved exclusively for numbers that FAIL the Luhn check.
- A 16-digit Luhn-valid number starting with 6 (e.g. a Discover card) is UNKNOWN here, since only VISA/MASTERCARD/AMEX patterns are recognized.
Wildcard Card Counting (Analytic, Not Brute Force)
The input may contain '*' wildcards, each standing for any single digit (e.g. "****424242424242"). Return the count of possible Luhn-valid card numbers per brand, as a list of "BRAND,count" pairs (e.g. ["VISA,1", "MASTERCARD,10"]).
A single pattern may be consistent with more than one brand, so report a count for every brand it could represent. Emit brands in the order VISA, MASTERCARD, AMEX, skipping any brand with a count of 0.
Do NOT brute-force 10^k completions. Count analytically:
- A pattern can only be a given brand if its length matches and every FIXED prefix digit is compatible with that brand's prefix rule.
- A wildcard in a prefix position is constrained to the allowed prefix values (e.g. VISA's leading '*' has exactly 1 choice: '4'); multiply those choices together.
- Among the remaining FREE wildcard positions, the Luhn constraint fixes one degree of freedom: the number of completions = (product of prefix-wildcard choices) * 10^(free_wildcards - 1), provided at least one wildcard is free.
- If there are zero free wildcards, the count is the number of prefix-wildcard fills whose fully-determined number is Luhn-valid (1 if the single completion is valid, else 0).
Constraints
- Input contains digits 0-9 and '*' wildcards only.
- Number of wildcards can be large; 10^(free-1) must be computed analytically, never enumerated.
- Counts can exceed 32-bit range; Python ints are unbounded, but Java/C++ solutions would need BigInteger for very large patterns.
- Brands are emitted in fixed order VISA, MASTERCARD, AMEX; zero-count brands are omitted.
Examples
Input: ('****424242424242',)
Expected Output: ['VISA,100', 'MASTERCARD,50']
Explanation: 16-long, 4 leading stars. VISA: pos0 star -> 1 choice (4), 3 free -> 1*10^2=100. MASTERCARD: pos0 -> 1 (5), pos1 -> 5 (1-5), 2 free -> 5*10^1=50. AMEX needs length 15, excluded.
Input: ('4*4242424242424*',)
Expected Output: ['VISA,10']
Explanation: Fixed first digit 4 -> only VISA. 2 stars, pos0 fixed; one star is a free non-prefix position -> 10^(2-1)=10. Only the last star is free (the second char is a non-prefix position too) so f=2 -> 10.
Hints
- Treat each brand independently: first check the length matches, then check every fixed prefix digit is compatible.
- A wildcard inside the prefix region is NOT free: it is limited to the brand's allowed prefix values (VISA leading '*' -> 1 choice; MasterCard second '*' -> 5 choices).
- Luhn is a single linear (mod-10) constraint, so it removes exactly one degree of freedom: with f free wildcards the valid completions number 10^(f-1). With zero free wildcards, just enumerate the (tiny) prefix-wildcard fills and Luhn-check each.
Single-Error Card Reconstruction
An observed string ends with a trailing '?' meaning exactly one error happened to the preceding digits. The error is one of: changed digit, removed digit, added digit, or transposition of two adjacent digits (e.g. "4333220284765319?").
Enumerate every ORIGINAL card number that (a) was Luhn-valid and matched a real brand (VISA / MASTERCARD / AMEX) before the error, and (b) could have produced the observed string via exactly one such error.
Invert each operation against the observed digits (drop the trailing '?'):
- Changed digit: at each position, try the other 9 digits.
- Removed digit (original was one longer): insert each of 10 digits at every gap.
- Added digit (original was one shorter): delete each position.
- Adjacent transposition: swap each adjacent pair back.
Deduplicate the candidates, keep only those that are Luhn-valid AND map to a brand, and return them sorted ascending as "NUMBER,BRAND" strings.
Constraints
- The observed string ends with a single trailing '?'.
- Exactly one error occurred; the candidate generator inverts all four edit types and deduplicates (different edits can yield the same original).
- Only Luhn-valid candidates that map to a real brand (VISA/MASTERCARD/AMEX) survive; UNKNOWN-shaped numbers are discarded.
- Results are sorted ascending by the numeric string and formatted as "NUMBER,BRAND".
Examples
Input: ('4242424242424252?',)
Expected Output: ['4242424242424242,VISA', '4242424242424259,VISA', '4242424242424952,VISA', '4242424242427252,VISA', '4242424242494252,VISA', '4242424242724252,VISA', '4242424249424252,VISA', '4242424272424252,VISA', '4242424942424252,VISA', '4242427242424252,VISA', '4242494242424252,VISA', '4242724242424252,VISA', '4249424242424252,VISA', '4272424242424252,VISA', '4942424242424252,VISA']
Explanation: A near-valid 16-digit observed string; the true original 4242424242424242 is recovered by a single changed-digit inversion, alongside other VISA originals one edit away.
Input: ('371449635398431?',)
Expected Output: ['371449635398431,AMEX']
Explanation: The observed (minus '?') is already a valid 15-digit AMEX; the only branded Luhn-valid reconstruction within one edit is itself.
Hints
- Strip the trailing '?' first, then generate candidates for all four inverse operations into a set so duplicates collapse.
- Insertion (to undo a removed digit) and deletion (to undo an added digit) change the length by one - that is how a 15-digit AMEX or 16-digit VISA original can emerge from an off-by-one observed string.
- Re-validate each candidate with the SAME Luhn + brand rules from tasks 1-2; keep only the ones that are both Luhn-valid and brand-matched.
Community answers
Answer by prasadkirpekar96
Here is my code for the question
visaPrefix = {"4"}
mastercardPrefix = {"51", "52", "53", "54", "55"}
amexPrefix = {"34", "37"}
INVALID_CHECKSUM = "INVALID_CHECKSUM"
VISA = "VISA"
MASTERCARD = "MASTERCARD"
AMEX = "AMEX"
UNKNOWN = "UNKNOWN"
def classifyCard(s):
if len(s) == 16 and s[:1] in visaPrefix:
return VISA
if len(s) == 16 and s[:2] in mastercardPrefix:
return MASTERCARD
if len(s) == 15 and s[:2] in amexPrefix:
return AMEX
return UNKNOWN
def checkLuhn(s):
total = 0
change = False
for i in range(len(s) - 1, -1, -1):
val = int(s[i])
if change:
val *= 2
if val > 9:
val -= 9
total += val
change = not change
return total % 10 == 0
def classifyCardOrUnknown(s):
if not checkLuhn(s):
return INVALID_CHECKSUM
return classifyCard(s)
def wildcardBrandCounts(s):
wildCount = s.count("*")
res = []
# VISA
if len(s) == 16 and s[0] in "4*":
prefix_wildcards = s[0] == "*"
free_wildcards = wildCount - prefix_wildcards
if free_wildcards:
count = 10 ** (free_wildcards - 1)
else:
count = checkLuhn("4" + s[1:])
if count:
res.append(f"{VISA},{count}")
# MASTERCARD
if len(s) == 16:
prefix_choices = 0
prefix_wildcards = 0
if s[:2] == "**":
prefix_choices = 5
prefix_wildcards = 2
elif s[:2] == "5*":
prefix_choices = 5
prefix_wildcards = 1
elif s[:2] in mastercardPrefix:
prefix_choices = 1
if prefix_choices:
free_wildcards = wildCount - prefix_wildcards
if free_wildcards:
count = prefix_choices 10 (free_wildcards - 1)
else:
count = sum(
checkLuhn(prefix + s[2:])
for prefix in mastercardPrefix
)
if c