How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Pinterest during technical interviews.

Insert parentheses to minimize expression value

Quick Overview

This question evaluates string parsing, arithmetic expression modeling, and combinatorial optimization skills by requiring reasoning about how digit concatenation and parentheses placement alter multiplicative factors and the final numeric value.

Company: Pinterest

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

You are given a string expression of the form `A+B`, where `A` and `B` are non-empty strings of digits (no digit is `'0'`). You must insert exactly one pair of parentheses `(` and `)` into the expression such that: - The parentheses form a valid expression and **must include the plus sign**. - Any digits **outside** the parentheses remain adjacent to the parentheses and are interpreted as **multiplication** with the parenthesized sum. More precisely, choose a split of `A` into `A = L1 + L2` (concatenation) and a split of `B` into `B = R1 + R2` such that the resulting value is: - If `L1` is empty, treat it as multiplicative factor 1; otherwise factor is integer value of `L1`. - If `R2` is empty, treat it as multiplicative factor 1; otherwise factor is integer value of `R2`. Resulting value = `factor(L1) * (int(L2) + int(R1)) * factor(R2)`. Return the expression string with parentheses inserted that yields the **minimum** possible value. If multiple answers tie, return any one. Example: input `"435+122"` could become something like `"4(35+12)2"` (not necessarily optimal).

Quick Answer: This question evaluates string parsing, arithmetic expression modeling, and combinatorial optimization skills by requiring reasoning about how digit concatenation and parentheses placement alter multiplicative factors and the final numeric value.

You are given a string `expression` of the form `A+B`, where `A` and `B` are non-empty strings of digits and no digit is `'0'`. You must insert exactly one pair of parentheses `(` and `)` so that: - The parentheses form a valid sub-expression and **must enclose the `+` sign** (so the inside looks like `L2+R1`). - Any digits left **outside** the parentheses stay adjacent to them and are interpreted as **multiplication** with the parenthesized sum. Formally, split `A` into a prefix `L1` and a non-empty suffix `L2` (`A = L1 + L2`), and split `B` into a non-empty prefix `R1` and a suffix `R2` (`B = R1 + R2`). The resulting value is: ``` factor(L1) * (int(L2) + int(R1)) * factor(R2) ``` where `factor(s)` is `int(s)` if `s` is non-empty, otherwise `1` (an empty outside part contributes a multiplicative factor of 1). Return the expression string with the chosen parentheses inserted (format `L1(L2+R1)R2`) that yields the **minimum** possible value. If several insertions tie, return any one of them. Example: for `"435+122"`, the answer `"4(35+12)2"` gives `4 * (35 + 12) * 2 = 376`.

Constraints

expression has the form A+B with exactly one '+'.
A and B are non-empty strings of digits.
No digit is '0'.
L2 (suffix of A inside the parens) and R1 (prefix of B inside the parens) are non-empty; the prefix L1 of A and suffix R2 of B may be empty (factor 1).
1 <= |A|, |B| (typical OA sizes are small, e.g. up to a few dozen digits).

Examples

Input: ("1+1",)

Expected Output: (1+1)

Explanation: Both sides are single digits, so L1 and R2 must be empty; the only option is (1+1), value 1*(1+1)*1 = 2.

Input: ("435+122",)

Expected Output: 4(35+12)2

Explanation: Pull '35' and '12' inside: 4 * (35 + 12) * 2 = 4 * 47 * 2 = 376, the minimum over all splits.

Input: ("9+9",)

Expected Output: (9+9)

Explanation: Single digits both sides; (9+9) = 18 is the only valid insertion.

Input: ("12+34",)

Expected Output: 1(2+3)4

Explanation: Best split leaves '1' and '4' outside as factors: 1 * (2 + 3) * 4 = 20, smaller than e.g. (12+34)=46 or 1*(2+34)... etc.

Input: ("5+5",)

Expected Output: (5+5)

Explanation: Single-digit boundary case: only (5+5) = 10 is possible.

Hints

The parentheses always enclose the '+', so the inside is (L2 + R1) where L2 is a suffix of A and R1 is a prefix of B; everything else (L1 before, R2 after) becomes a multiplicative factor.
An empty outside part contributes a factor of 1, NOT 0 — pulling more digits inside the parens often lowers the value because it removes a large multiplier.
The input is tiny, so brute force over all (L1/L2) and (R1/R2) splits is fine: O(|A|*|B|) candidates. For '435+122' the best is 4*(35+12)*2 = 376.
Build the answer string as L1 + '(' + L2 + '+' + R1 + ')' + R2 for the split that gives the minimum value.

Quick Overview