Multiply strings: multiply two big numbers given as text

Multiply two non-negative integers given as decimal strings and return the product as a string. Do not convert the inputs to built-in integers or use a big-number library.

Interface

Unless you agree on a different interface with the interviewer, assume:

• multiply(num1: str, num2: str) -> str — both inputs are digit strings with no leading zeros, except "0" itself. The result has no leading zeros.

Example

multiply("123", "456")  ->  "56088"
multiply("0", "52")     ->  "0"
multiply("99", "99")    ->  "9801"

Constraints

• 1 <= len(num1), len(num2) <= 200.
• Only the digits 0 to 9.

Clarifying questions

• Can the inputs have leading zeros or a sign?
• When I add products into a digit position, can a temporary value exceed 9, and am I allowed to carry once at the end?
• Is "0" a possible input, and how should the result look then?

What a strong answer covers

• Grade-school multiplication into an array of len(num1) + len(num2) positions: the product of digits i and j lands at positions i + j and i + j + 1.
• Carry handling: either carry on each addition, or accumulate raw sums (which can exceed 9) and normalise in one pass from the right.
• Stripping leading zeros and returning "0" for a zero product.
• O(m * n) time, O(m + n) space; mention Karatsuba as the asymptotically faster option.
• Tests: zero, one-digit inputs, all nines, very different lengths.

Follow-ups

• Add two number strings, then subtract them.
• Support negative numbers.
• Support decimal points in the inputs.