Quick Overview

This question evaluates algorithmic problem-solving and implementation skills in string processing, checksum validation (Luhn), pattern matching, combinatorics for counting masked completions, and single-error recovery for payment-card numbers.

Implement Card Validation and Recovery System

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

##### Question Design and implement a payment-card validation system supporting: Basic VISA validation (16-digit numbers starting with 4) using the Luhn checksum. Multi-network validation for VISA, MASTERCARD (16 digits, prefixes 51- 55) and AMEX (15 digits, prefixes 34 or 37), returning UNKNOWN_NETWORK or INVALID_CHECKSUM when appropriate. Redacted cards containing 1-5 ‘*’ wildcards: count all valid completions per network and output counts sorted alphabetically by network. Corrupted cards ending in ‘?’ with exactly one error (one digit changed or two adjacent digits swapped): enumerate all possible original valid card numbers with their network names, sorted numerically. Follow all formatting and performance constraints described in the prompt.

Quick Answer: This question evaluates algorithmic problem-solving and implementation skills in string processing, checksum validation (Luhn), pattern matching, combinatorics for counting masked completions, and single-error recovery for payment-card numbers.

Part 1: Basic VISA Validation Using the Luhn Checksum

Implement a validator for basic VISA card numbers. A card is valid if it contains exactly 16 digits, starts with digit 4, and passes the Luhn checksum algorithm. Return True for a valid VISA number and False otherwise.

Constraints

  • 0 <= len(card_number) <= 32
  • card_number may contain digits or other characters
  • A valid VISA number must be exactly 16 characters, all digits, and start with 4

Examples

Input: ('4111111111111111',)

Expected Output: True

Explanation: This is a 16-digit number starting with 4 and it passes Luhn.

Input: ('4012888888881881',)

Expected Output: True

Explanation: Another valid VISA test number.

Hints

  1. For Luhn, process digits from right to left and double every second digit.
  2. If a doubled digit becomes greater than 9, subtract 9 from it before adding to the checksum.

Part 2: Multi-Network Card Validation

Implement validation for three payment-card networks: VISA, MASTERCARD, and AMEX. VISA cards have 16 digits and start with 4. MASTERCARD cards have 16 digits and prefixes 51 through 55. AMEX cards have 15 digits and prefixes 34 or 37. If the number does not match any supported network pattern, return UNKNOWN_NETWORK. If it matches a network pattern but fails Luhn, return INVALID_CHECKSUM. Otherwise return the network name.

Constraints

  • 0 <= len(card_number) <= 32
  • card_number may contain digits or other characters
  • Network matching is based on exact length and prefix
  • Checksum is evaluated only after a supported network pattern is matched

Examples

Input: ('4111111111111111',)

Expected Output: 'VISA'

Explanation: The number matches VISA rules and passes Luhn.

Input: ('5555555555554444',)

Expected Output: 'MASTERCARD'

Explanation: The prefix 55 and length 16 identify MASTERCARD, and the checksum is valid.

Hints

  1. Separate the network-detection logic from the Luhn checksum logic.
  2. If a number has an unsupported length or prefix, do not run checksum-based classification; return UNKNOWN_NETWORK.

Part 3: Redacted Card Wildcard Completion Counts

A redacted card number contains digits and between 1 and 5 wildcard characters, where each wildcard is written as *. Each * can be replaced by any digit from 0 to 9. Count how many completions produce a valid card for each supported network: AMEX, MASTERCARD, and VISA. Return counts for all three networks sorted alphabetically by network name.

Constraints

  • 1 <= len(redacted) <= 16
  • redacted contains only digits and * characters
  • 1 <= number of * characters <= 5
  • Supported networks use the same length, prefix, and Luhn rules as Part 2

Examples

Input: ('411111111111111*',)

Expected Output: [['AMEX', 0], ['MASTERCARD', 0], ['VISA', 1]]

Explanation: Only replacing * with 1 produces the valid VISA number 4111111111111111.

Input: ('41111111111111**',)

Expected Output: [['AMEX', 0], ['MASTERCARD', 0], ['VISA', 10]]

Explanation: The prefix and length force VISA; among the 100 endings, exactly 10 pass Luhn.

Hints

  1. With at most 5 wildcards, there are at most 100000 completions, which is small enough to enumerate directly.
  2. After filling the wildcards, reuse the same network-detection and Luhn validation steps.

Part 4: Corrupted Card Recovery

A corrupted card record is a string of digits followed by a trailing ? marker. The marker is not part of the card number. The digits before ? may differ from an original valid card in exactly one way: either one digit was changed to another digit, or two adjacent digits were swapped. Enumerate every possible original valid card number and its network name. Supported networks are AMEX, MASTERCARD, and VISA using the same rules as earlier parts.

Constraints

  • 1 <= len(corrupted) <= 17
  • corrupted ends with ?
  • All characters before ? are digits
  • The observed number length is expected to be 15 or 16 for recoverable cards
  • For a digit-change error, the original digit must be different from the observed digit
  • For an adjacent-swap error, the swap must change the observed string, so equal adjacent digits do not generate a candidate

Examples

Input: ('6111111111111111?',)

Expected Output: [['4111111111111111', 'VISA']]

Explanation: Changing the first digit from 6 back to 4 recovers a valid VISA number.

Input: ('4909000000000004?',)

Expected Output: [['4099000000000004', 'VISA'], ['4900900000000004', 'VISA'], ['4990000000000004', 'VISA']]

Explanation: Several adjacent swaps involving 0 and 9 produce valid VISA originals; results are sorted numerically.

Hints

  1. Generate candidates by trying every single-position digit replacement and every adjacent swap, then validate each candidate.
  2. Use a set or dictionary to avoid returning the same valid original more than once.

Loading coding console...