Katkat
Back

Implement multi-network card validator with Luhn

StripeSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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.
  1. Card networks
  • VISA: 16 digits, prefix 4
  • MASTERCARD: 16 digits, prefixes 51–55
  • AMEX: 15 digits, prefixes 34 or 37
  1. Part 1 — Basic VISA
  • Input: a 16-digit string starting with 4
  • Output: "VISA" if Luhn-valid; otherwise "INVALID_CHECKSUM"
  1. 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"
  1. 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>".
  1. 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
  1. and how you avoid duplicates and ensure determinism.
  • Provide test strategy and sample cases for each part.