Binary XOR Coding | Dataford Interview Questions

Binary XOR Coding

MediumPython

Problem

While validating diagnostic bitmasks for a Western Digital WD_BLACK SN850X device, implement binary XOR directly on strings. Return the result once with an iterative algorithm and once with a recursive algorithm, without converting the complete inputs to integers.

Formal Specification

Implement binary_xor(a, b, recursive=False):

a and b are non-empty strings containing only '0' and '1'.
Align both strings by their rightmost bit, padding the shorter string on the left with zeros.
XOR corresponding bits and return a binary string with no leading zeros, except that zero must be returned as '0'.
When recursive is False, use an iterative implementation.
When recursive is True, use a recursive implementation. The recursive version should avoid one recursive call per bit so it remains practical for long inputs.

Do not use Python integer conversion on the complete binary strings, such as int(a, 2).

Constraints

1 <= len(a), len(b) <= 100000
Each input contains only '0' and '1'
Inputs may contain leading zeros
The result must contain no leading zeros unless it is exactly '0'
Do not convert the complete strings to integers

Function Signature

def binary_xor(a, b, recursive=False):

Formal Specification

Implement binary_xor(a, b, recursive=False):

a and b are non-empty strings containing only '0' and '1'.
Align both strings by their rightmost bit, padding the shorter string on the left with zeros.
XOR corresponding bits and return a binary string with no leading zeros, except that zero must be returned as '0'.
When recursive is False, use an iterative implementation.
When recursive is True, use a recursive implementation. The recursive version should avoid one recursive call per bit so it remains practical for long inputs.

Do not use Python integer conversion on the complete binary strings, such as int(a, 2).