Binary String Addition | Dataford Interview Questions

A Hudson River Trading market-data component represents certain compact counters as binary strings. Given two non-negative binary strings, return their sum as a binary string without converting either input to a built-in integer type.

Process the strings from right to left, maintaining a carry. The inputs contain no leading zeroes unless the value is exactly "0".

Formal Specification

Implement add_binary(a, b):

Input: Two non-empty strings a and b, each containing only the characters 0 and 1.
Output: A string containing the binary representation of a + b, with no leading zeroes unless the result is "0".

Constraints

1 <= len(a), len(b) <= 100000
a and b contain only the characters 0 and 1
Neither input has leading zeroes unless it is exactly "0"
The output must have no leading zeroes

Function Signature

def add_binary(a, b):

Your question is Binary String Addition. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem