PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Pinterest
  • Coding & Algorithms
  • Software Engineer

Implement string-based big integer multiplication

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question Implement `multiplyStrings(a, b)` to multiply two non-negative integers given as decimal strings and return their product as a decimal string. You may **not** convert the full inputs to a built-in big-integer or fixed-width integer type, nor use any arbitrary-precision arithmetic library. Your solution must: 1. Correctly multiply two non-negative integers represented as decimal strings and return the product as a string. 2. Handle edge cases: `"0"` (and any product that is zero), `"1"`, inputs of very different lengths, leading zeros in the inputs, and many trailing zeros. The result must not carry spurious leading zeros (e.g. `"00"` should never be returned). 3. Scale efficiently to very large inputs (e.g. strings up to a few thousand digits, or up to ~10^5 total digits) while managing carries correctly and avoiding quadratic *memory* blowups. 4. Discuss the algorithmic options and their trade-offs: grade-school long multiplication (`O(n·m)` time), Karatsuba (`O(n^1.585)`), and FFT/NTT-based convolution (`O(n log n)`). Implement at least one approach. 5. State the time and space complexity of your implementation. 6. Explain how you would test the solution, enumerating the edge cases above.

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.

Implement `multiplyStrings(a, b)` to multiply two non-negative integers given as decimal strings and return their product as a decimal string. You may NOT convert the full inputs to a built-in big-integer or fixed-width integer type, nor use any arbitrary-precision arithmetic library. Requirements: 1. Correctly multiply two non-negative integers represented as decimal strings and return the product as a string. 2. Handle edge cases: "0" (and any product that is zero), "1", inputs of very different lengths, leading zeros in the inputs, and many trailing zeros. The result must not carry spurious leading zeros (e.g. "00" should never be returned). 3. Scale efficiently to very large inputs (strings up to a few thousand digits) while managing carries correctly and avoiding quadratic memory blowups. Approach: grade-school long multiplication on digit arrays. Digit i of `a` (from the right) times digit j of `b` contributes to position i+j of the result. Accumulate every partial product di*dj into a result buffer of size n+m, then do a single carry-propagation pass, then trim leading zeros. Examples: - multiplyStrings("123", "4567") -> "561741" - multiplyStrings("0", "123") -> "0" - multiplyStrings("007", "08") -> "56" - multiplyStrings("99", "99") -> "9801"

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

  1. 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.
  2. 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.
  3. 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.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • First Word Matching Each Prefix Query - Pinterest (medium)
  • Hierarchical Access Control for an Advertising Platform - Pinterest (medium)
  • Maximize Boxes Stored Through One Entrance - Pinterest (medium)
  • Solve Multiple Coding Interview Problems - Pinterest (medium)
  • Implement a Sparse Matrix Class - Pinterest (medium)