Handle palindrome & decimal addition
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 266. Palindrome Permutation Given two non-negative decimal number strings, implement addition that supports a decimal point.
https://leetcode.com/problems/palindrome-permutation/description/
Quick Answer: This question evaluates string manipulation and numeric representation skills, specifically handling decimal-point addition with arbitrary precision and reasoning about palindrome/permutation properties.
Given two non-negative decimal number strings a and b, return their sum as a normalized decimal string. The strings may contain at most one decimal point. Perform digit-wise addition; do not parse the entire strings as numeric types. Normalization rules for the output: remove leading zeros in the integer part (but keep a single '0' if the number is zero), remove trailing zeros in the fractional part, and omit the decimal point if the fractional part becomes empty.
Constraints
- 1 <= len(a), len(b) <= 100000
- a and b contain only digits and at most one '.'
- If '.' is present, there is at least one digit on both sides (matches regex: ^[0-9]+(\.[0-9]+)?$)
- No signs, spaces, or exponent notation
- Must not convert the entire strings to integers/floats/decimals; use digit-wise addition
- Return must be normalized as described
Examples
Input:
Expected Output: 13
Input:
Expected Output: 1000
Input:
Expected Output: 16
Input:
Expected Output: 0
Input:
Expected Output: 579.789
Input:
Expected Output: 0
Input:
Expected Output: 1.24
Input:
Expected Output: 1000
Solution
def add_decimal_strings(a: str, b: str) -> str:
def split_num(s: str):
if '.' in s:
i, f = s.split('.', 1)
else:
i, f = s, ''
return i, f
ai, af = split_num(a)
bi, bf = split_num(b)
maxf = max(len(af), len(bf))
if maxf > 0:
af_p = af.ljust(maxf, '0')
bf_p = bf.ljust(maxf, '0')
else:
af_p = ''
bf_p = ''
carry = 0
frac = ''
if maxf > 0:
fr = []
for idx in range(maxf - 1, -1, -1):
ssum = (ord(af_p[idx]) - 48) + (ord(bf_p[idx]) - 48) + carry
fr.append(chr(ssum % 10 + 48))
carry = ssum // 10
fr.reverse()
frac = ''.join(fr)
i = len(ai) - 1
j = len(bi) - 1
ir = []
while i >= 0 or j >= 0 or carry:
da = ord(ai[i]) - 48 if i >= 0 else 0
db = ord(bi[j]) - 48 if j >= 0 else 0
ssum = da + db + carry
ir.append(chr(ssum % 10 + 48))
carry = ssum // 10
i -= 1
j -= 1
ir.reverse()
integer = ''.join(ir)
k = 0
while k < len(integer) and integer[k] == '0':
k += 1
if k == len(integer):
integer = '0'
else:
integer = integer[k:]
if frac:
t = len(frac)
while t > 0 and frac[t - 1] == '0':
t -= 1
frac = frac[:t]
return integer if not frac else integer + '.' + frac
Explanation
Split each string into integer and fractional parts. Pad the shorter fractional part with trailing zeros and add the fractional digits right-to-left to obtain the fractional sum and a carry into the integer part. Then add the integer parts right-to-left including the carry. Normalize by removing leading zeros from the integer sum (leaving '0' if empty) and removing trailing zeros from the fractional sum; drop the decimal point if the fractional sum becomes empty.
Time complexity: O(n). Space complexity: O(n).
Hints
- Split each input around the decimal point into integer and fractional parts.
- Pad the shorter fractional part with trailing zeros so both fractions have equal length.
- Add fractional parts right-to-left, carrying into the integer part if needed.
- Add integer parts right-to-left, including any carry from the fractional sum.
- Trim trailing zeros from the fractional result and leading zeros from the integer result; remove the decimal point if the fractional part becomes empty.