Quick Overview

This question evaluates a candidate's ability to implement and reason about the Luhn checksum, multi-network payment card format validation, combinatorial completion for redacted digits, single-error correction models, and efficient search/pruning with deterministic duplicate avoidance.

Implement multi-network card validator with Luhn

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Design and implement a payment card validation module that supports multiple networks and error scenarios. Requirements: 1) Luhn checksum - Implement the Luhn algorithm: starting from the rightmost non-check digit, double every second digit; if the result > 9 subtract 9; sum all digits; valid if sum % 10 == 0. 2) Card networks - VISA: 16 digits, prefix 4 - MASTERCARD: 16 digits, prefixes 51–55 - AMEX: 15 digits, prefixes 34 or 37 3) Part 1 — Basic VISA - Input: a 16-digit string starting with 4 - Output: "VISA" if Luhn-valid; otherwise "INVALID_CHECKSUM" 4) Part 2 — Multi-network - Input: a 15- or 16-digit string - Output: the network name (VISA/MASTERCARD/AMEX) if prefix/length match and Luhn-valid; "INVALID_CHECKSUM" if prefix/length match but Luhn fails; otherwise "UNKNOWN_NETWORK" 5) Part 3 — Redacted cards - Input: a card string containing 1–5 asterisks (*) that replace digits - Task: count how many concrete completions are valid per network, considering prefix/length rules and Luhn. Output one line per network that has at least one valid completion, sorted alphabetically by network: "AMEX,<count>", "MASTERCARD,<count>", "VISA,<count>". 6) Part 4 — Corrupted cards - Input: a card string ending with '?' indicating exactly one error was introduced in an originally valid card, where the error is either (a) one digit changed to another digit, or (b) a swap of two adjacent digits - Task: enumerate all possible original valid cards consistent with that model (respecting network rules and Luhn). Output each as "<card_number>,<NETWORK>", sorted numerically by card number. General constraints and expectations - Treat inputs as strings; use exact output tokens. - For Parts 3 and 4, design efficient search with pruning using prefix constraints and Luhn properties; handle large search spaces. - Specify data structures, algorithms, and time/space complexity for each part. - Describe edge cases (wrong lengths, invalid prefixes, leading zeros in redactions, multiple '*' placement, duplicate reconstructions in Part 4) and how you avoid duplicates and ensure determinism. - Provide test strategy and sample cases for each part.

Quick Answer: This question evaluates a candidate's ability to implement and reason about the Luhn checksum, multi-network payment card format validation, combinatorial completion for redacted digits, single-error correction models, and efficient search/pruning with deterministic duplicate avoidance.

Part 1: Basic VISA Validator

Write a function that validates a basic VISA card number using the Luhn checksum. A valid card for this problem must be a 16-character string of digits, must start with '4', and must satisfy the Luhn rule. Return 'VISA' if it is valid; otherwise return 'INVALID_CHECKSUM'. For robustness, malformed inputs are also treated as invalid.

Constraints

  • Treat the input as a string.
  • A valid VISA candidate for this part has exactly 16 digits and starts with '4'.
  • Any non-digit input, wrong length, or wrong prefix should be treated as invalid.
  • Use the Luhn checksum exactly as specified.

Examples

Input: '4111111111111111'

Expected Output: 'VISA'

Explanation: This is a standard valid 16-digit VISA test number.

Input: '4111111111111112'

Expected Output: 'INVALID_CHECKSUM'

Explanation: It has the correct VISA prefix and length, but the checksum fails.

Hints

  1. Traverse the number from right to left and alternate whether a digit is doubled.
  2. When doubling a digit produces a number greater than 9, subtract 9 from it.

Part 2: Multi-network Card Validator

Write a function that validates a payment card against three supported networks: VISA, MASTERCARD, and AMEX. First identify whether the card matches a supported network by prefix and length. If it matches and passes the Luhn checksum, return the network name. If it matches a supported network but fails Luhn, return 'INVALID_CHECKSUM'. Otherwise return 'UNKNOWN_NETWORK'.

Constraints

  • Treat the input as a string.
  • Supported networks: VISA = 16 digits starting with '4'; MASTERCARD = 16 digits starting with 51-55; AMEX = 15 digits starting with 34 or 37.
  • If prefix/length do not match any supported network, return 'UNKNOWN_NETWORK'.
  • If prefix/length match a supported network but Luhn fails, return 'INVALID_CHECKSUM'.

Examples

Input: '4111111111111111'

Expected Output: 'VISA'

Explanation: Valid VISA number.

Input: '5555555555554444'

Expected Output: 'MASTERCARD'

Explanation: Valid MASTERCARD number with prefix 55.

Hints

  1. Separate the problem into two steps: identify the network by prefix/length, then run Luhn only on supported candidates.
  2. Because the network rules are disjoint here, at most one network can match a given input.

Part 3: Count Valid Networks for Redacted Cards

A card number is partially redacted: some digits are replaced by '*' characters. Each '*' stands for exactly one digit from 0 to 9. Count how many concrete completions are valid for each supported network, using both the network rules and the Luhn checksum. Return one entry per network that has at least one valid completion, formatted as 'NETWORK,count', sorted alphabetically by network name. Return an empty list if no completion is valid for a supported network.

Constraints

  • Treat the input as a string.
  • The input may contain digits and '*' only.
  • There are at most 5 '*' characters.
  • Only lengths 15 and 16 can match supported networks; all other lengths return an empty list.

Examples

Input: '411111111111111*'

Expected Output: ['VISA,1']

Explanation: Only one check digit makes this VISA number Luhn-valid.

Input: '4111111111111***'

Expected Output: ['VISA,100']

Explanation: The first 13 digits force VISA. The last two non-check digits can be any 00-99, and each choice determines exactly one valid check digit.

Hints

  1. Filter by length and prefix compatibility first; unsupported prefixes can be rejected before exploring every completion.
  2. If only the final check digit is unknown, every fixed prefix/body determines exactly one valid check digit.

Part 4: Reconstruct Valid Cards from One Corruption

You are given a corrupted card record as a string that ends with '?'. The '?' is only a marker and is not part of the card number; the preceding digits are the observed corrupted number. Exactly one error was introduced into an originally valid supported card, and the error was either: (1) one digit changed to another digit, or (2) one swap of two adjacent digits. Enumerate every possible original valid card consistent with that model. Return each result as '<card_number>,<NETWORK>', sorted numerically by card number. Return an empty list if there are no valid reconstructions.

Constraints

  • Treat the input as a string.
  • The input must end with '?'; otherwise there are no reconstructions.
  • Only VISA, MASTERCARD, and AMEX are supported, using the same length/prefix rules as earlier parts.
  • Avoid duplicate reconstructions: the same original card may be reachable by more than one error explanation.

Examples

Input: '1411111111111111?'

Expected Output: ['4111111111111111,VISA']

Explanation: Swapping the first two digits reconstructs a valid VISA card.

Input: '738282246310005?'

Expected Output: ['378282246310005,AMEX']

Explanation: Swapping the first two digits reconstructs the valid AMEX number.

Hints

  1. Because there was exactly one error, every candidate original card is either one digit substitution away from the observed number or one adjacent swap away.
  2. Use a set to deduplicate candidates before sorting the final answers.

Loading coding console...