Fraction Addition and Subtraction

Fraction Addition and Subtraction

What is this problem about?

The Fraction Addition and Subtraction interview question requires you to evaluate a string representing an expression of fraction additions and subtractions. You must return the result as an irreducible fraction in string format. The input might look like "-1/2+1/2" or "1/3-1/2". If the result is an integer, it should still be formatted as a fraction with a denominator of 1 (e.g., "3/1").

Why is this asked in interviews?

Companies like Goldman Sachs, Meta, and Amazon ask the Fraction Addition and Subtraction coding problem to assess a candidate's string parsing abilities and fundamental mathematical knowledge. It tests if you know how to extract numbers from a string, handle signs, find the Least Common Multiple (LCM) or Greatest Common Divisor (GCD) to add fractions, and then simplify the final result.

Algorithmic pattern used

This problem relies on a String Parsing and Math Simulation pattern.

1. Parse: Use string splitting or a regular expression to extract each fraction (numerator and denominator) along with its sign.
2. Accumulate: Maintain a running total represented by a current_numerator and current_denominator (initially 0/1).
3. Add: For each new fraction num/den, the new numerator is current_numerator * den + num * current_denominator, and the new denominator is current_denominator * den.
4. Simplify: Find the GCD of the new numerator and denominator and divide both by it to keep the numbers small and irreducible.

Example explanation

Expression: "1/3-1/2"

1. Start: 0/1.
2. Parse "1/3": num = 1, den = 3.
   • New num: 0*3 + 1*1 = 1. New den: 1*3 = 3.
   • GCD(1, 3) = 1. Current: 1/3.
3. Parse "-1/2": num = -1, den = 2.
   • New num: 1*2 + (-1)*3 = 2 - 3 = -1.
   • New den: 3*2 = 6.
   • GCD(-1, 6) = 1. Current: -1/6. Final result: "-1/6".

Common mistakes candidates make

• Parsing Errors: Failing to correctly associate the negative sign with the numerator, or struggling to split the string when the first fraction is positive (no leading sign).
• Integer Overflow: If you don't simplify the fraction after every addition, the denominator product can quickly exceed 32-bit integer limits.
• Negative GCD: Modulo operations with negative numbers can yield negative GCDs in some languages, leading to signs in the denominator (e.g., 1/-6 instead of -1/6).

Interview preparation tip

Practice implementing Euclid's algorithm for GCD (def gcd(a, b): return a if b == 0 else gcd(b, a % b)). Also, learn how to use string splitting with multiple delimiters or regex to easily extract signed integers from a mixed string.