Implement string-based big integer multiplication
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: Implement multiplyStrings(a, b) to multiply two non-negative integers given as decimal strings, returning the product as a string without any big-integer or arbitrary-precision library. The solution covers grade-school O(n*m) long multiplication with linear memory, the Karatsuba and FFT/NTT scaling alternatives, correct carry and leading/trailing-zero handling, and a full edge-case test plan.
Constraints
- 1 <= len(a), len(b); inputs are non-empty decimal strings of digits 0-9.
- Inputs may contain leading zeros (e.g. "007").
- Inputs are non-negative; no sign characters.
- Do not convert the full inputs to a built-in big-integer or fixed-width integer type, and do not use any arbitrary-precision library.
- Output must not contain spurious leading zeros ("0" for a zero product, never "00").
Examples
Input: ("123", "4567")
Expected Output: "561741"
Explanation: Standard multi-digit multiply: 123 * 4567 = 561741.
Input: ("0", "123")
Expected Output: "0"
Explanation: Zero operand yields product "0" (no leading-zero padding).
Input: ("0", "0")
Expected Output: "0"
Explanation: Both zero -> "0", never "00".
Input: ("1", "99999")
Expected Output: "99999"
Explanation: Identity: multiplying by 1 returns the other operand.
Input: ("99", "99")
Expected Output: "9801"
Explanation: Carry-chain stress: 99 * 99 = 9801.
Input: ("007", "08")
Expected Output: "56"
Explanation: Leading zeros in input contribute 0 and fall out; 7 * 8 = 56 with no spurious leading zeros.
Input: ("100", "100")
Expected Output: "10000"
Explanation: Many trailing zeros handled correctly: 100 * 100 = 10000.
Input: ("9", "99999999")
Expected Output: "899999991"
Explanation: Very different operand lengths.
Input: ("999999999", "999999999")
Expected Output: "999999998000000001"
Explanation: Long carry propagation across the full buffer.
Hints
- Process digits from least-significant (rightmost) to most-significant. Digit a[i] (counted from the right) times b[j] lands at result position i+j with carry into i+j+1.
- The product of an n-digit and an m-digit number has at most n+m digits, so a buffer of size n+m never overflows.
- Defer carry handling: first accumulate all di*dj sums into the buffer, then do one left-to-right pass dividing by 10 and carrying. Finally strip leading zeros, returning "0" if everything is zero.