Luhn Checksum
Asked of: Software Engineer
Last updated

What's being tested
These prompts test checksum implementation, string validation, and bounded combinatorial search around payment-card numbers. Interviewers look for clean isValidLuhn, brand/network rule handling, wildcard completion, and single-digit recovery without brute-forcing unnecessarily.
Patterns & templates
-
Luhn checksum — scan right-to-left, double every second digit, subtract
9if over9; valid whensum % 10 == 0. -
Check digit derivation — compute partial sum excluding final digit, then
check = (10 - partial % 10) % 10; avoid trialing0..9. -
Network validation — model card brands as
{name, lengths, prefixes}; validate digits, length, prefix, then checksum in a predictable order. -
Wildcard enumeration — for small
?counts, DFS over digits; for larger counts, use modulo-DP over positions with statesum_mod_10. -
Counting completions — dynamic program
dp[i][mod]inO(n * 10 * choices)time andO(10)space; apply brand constraints first. -
Single-error correction — try replacing each digit with
0..9except itself, then re-run format and checksum; complexityO(n * 10 * n)naïvely, reducible with precomputed contributions. -
Input hygiene — normalize spaces/dashes only if allowed; otherwise reject non-digits early and keep leading zeros meaningful.
Common pitfalls
Pitfall: Doubling parity is based on distance from the right, not absolute index; parity changes when length changes.
Pitfall: Passing Luhn alone is not enough; a number can satisfy the checksum but fail brand prefix or length rules.
Pitfall: Wildcard brute force explodes at
10^k; switch to modulo counting whenkis more than a few digits.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Implement multi-network card validator with LuhnStripe · Software Engineer · Take-home Project · Medium
- Implement Luhn-based card validation and inferenceStripe · Software Engineer · Take-home Project · Medium
- Validate and infer credit cards with LuhnStripe · Software Engineer · Take-home Project · Medium
- Implement Card Validation and Recovery SystemStripe · Software Engineer · Take-home Project · Medium
- Validate Credit Card Numbers and CorrectionsStripe · Software Engineer · Take-home Project · Medium
Related concepts
- Payment Systems: Ledgers, Idempotency, and Reconciliation
- Money-Safe Financial ComputationCoding & Algorithms
- Payment Processing And Ledger SystemsSystem Design
- Wallets, Payments, And Refund LedgersSystem Design
- Banking Ledgers And Cashback OperationsSystem Design
- ML Evaluation, Uncertainty, And Safety GuardrailsML System Design