Facebook Interview Question for Android Engineers


Country: UK, London
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

My naive implementation. (Kotlin)

fun addBinary(addendumLeft: String, addendumRight: String): String {
var i = addendumLeft.length-1
var j = addendumRight.length-1
/* Handling edge cases */
if(addendumLeft.isEmpty() && addendumRight.isNotEmpty())
return addendumRight
else if(addendumRight.isEmpty() && addendumLeft.isNotEmpty())
return addendumLeft
else if(addendumLeft.isEmpty() && addendumRight.isEmpty())
return ""

/* Implementation */
val result = StringBuilder()
var carryOn = false
while (i >= 0 || j >= 0) {
if(i < 0 || j < 0)
{
val bin = if(j < 0) addendumLeft[i] else addendumRight[j]
if(carryOn) {
if(bin == '1')
result.insert(0,'0')
else {
result.insert(0,'1')
carryOn = false
}
} else
result.insert(0, bin)

} else {
if(addendumLeft[i] == '0' && addendumRight[j] == '1' ||
addendumLeft[i] == '1' && addendumRight[j] == '0') {
if(carryOn)
result.insert(0, '0')
else
result.insert(0, '1')
}
else if(addendumLeft[i] == '1' && addendumRight[j] == '1') {
if(carryOn)
result.insert(0, '1')
else {
carryOn = true
result.insert(0, '0')
}
}
else {
if(carryOn) {
result.insert(0, '1')
carryOn = false
} else
result.insert(0,'0')
}
}

if(i >= 0)
i--
if(j >= 0)
j--
}

if(carryOn)
result.insert(0, '1')

return result.toString()
}

Any more elegant solution?

- fruktoed August 14, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Improved solution

fun addBinary(addendumLeft: String, addendumRight: String): String {
var i = addendumLeft.length-1
var j = addendumRight.length-1
/* Handling edge cases */
if(addendumLeft.isEmpty() && addendumRight.isNotEmpty())
return addendumRight
else if(addendumRight.isEmpty() && addendumLeft.isNotEmpty())
return addendumLeft
else if(addendumLeft.isEmpty() && addendumRight.isEmpty())
return ""

/* Implementation */
val result = StringBuilder()
var sum = 0
while (i >= 0 || j >= 0 || sum == 1) {

sum += if(i >= 0) addendumLeft[i] - '0' else 0
sum += if(j >= 0) addendumRight[j] - '0' else 0

result.insert(0, sum % 2)

sum /= 2

if(i >= 0)
i--
if(j >= 0)
j--
}

return result.toString()
}

Thanks to GeeksforGeeks

- fruktoed August 14, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here.

def bin_add( n1, n2 ){
  /* 
  n1 digit, n2 digit, carry digit from previous ->
  carry, resulting digit 
  */
  RULES = { '000' : '00', 
            '001' : '01', 
            '010' : '01',
            '011' : '10',
            '100' : '01', 
            '101' : '10',
            '110' : '10',
            '111' : '11' }
  min_size = size(n2)
  max_size = size(n1)
  if ( max_size < min_size ){
    #(n2,n1) = [n1, n2] // swap 
  }
  carry = '0'
  result = ""
  // when both are same size 
  i = min_size -1
  j = max_size -1
  while ( i >=0 ){
    input = str("%s%s%s", n1[j],n2[i], carry)
    i -= 1 
    j -= 1
    output = RULES[input]
    carry = output[0]
    result = str( "%s%s", output[1],  result )
  }
  while ( j >= 0) {
    input = str("%s0%s", n1[j],carry) 
    j -= 1
    output = RULES[input]
    carry = output[0]
    result = str( "%s%s", output[1],  result )
  }
  if ( carry == '1' ){
    result = str("1%s", result)
  }
  result // return 
}

println( bin_add('1101','1') )

- NoOne August 15, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * @author allwin.s
 */
public class BinarySum {

	public static void main(String[] args) {

		String s1 = "1";// "0000100";// "110";// "1011"; // "101";
		String s2 = "10";// "101";// "1000"; // "100";

		String res = "";
		res = add(s1.toCharArray(), s2.toCharArray(), s1.length() - 1, s2.length() - 1, 0, res);

		System.out.println(s1 + " + " + s2 + " = " + res);

	}

	private static String add(char[] A, char[] B, int i, int j, int carry, String result) {

		if (i < 0 && j < 0) {
			return (carry > 0 ? carry : "") + result;
		}

		int a = (i >= 0 ? A[i] - '0' : 0);
		int b = (j >= 0 ? B[j] - '0' : 0);
		int sum = a + b + carry;
		result = sum % 2 + result;

		return add(A, B, i - 1, j - 1, sum / 2, result);
	}
}

- Allwin S August 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* @Prashant
*/
const binaryAddition = (str1, str2) => {
if (!str1 && !str2) {
return '';
}
if (!str1) {
return str2;
} else if (!str2) {
return str1;
}


let result = '';

const limit = str1.length >= str2.length ? str1.length : str2.length;

let carry = '0';
for(let i = limit - 1; i >= 0; --i) {
let val1 = '';
if (i > (str1.length - 1)) {
val1 = '0';
} else {
val1 = str1[i];
}

let val2 = '';

if (i > (str2.length - 1)) {
val2 = '0';
} else {
val2 = str2[i];
}

if (val1 === '1' && val2 === '1' && carry === '0') {
result = '0' + result;
carry = '1';
} else if (val1 === '1' && val2 === '1' && carry === '1') {
result = '1' + result;
carry = '1';
} else if (val1 === '1' && val2 === '0' && carry === '0') {
result = '1' + result;
carry = '0';
} else if(val1 === '1' && val2 === '0' && carry === '1') {
result= '0' + result;
carry = '1';
} else if(val1 === '0' && val2 === '1' && carry === '0') {
result = '1' + result;
carry = '0';
} else if(val1 === '0' && val2 === '1' && carry === '1') {
result = '0' + result;
carry = '1';
} else if ((val1 === '0' && val2 === '0' && carry === '0') ) {
result = '0' + result;
carry = '0';
} else if ((val1 === '0' && val2 === '0' && carry === '1') ) {
result = '1' + result;
carry = '0';
}
}

if (carry === '1') {
result= '1' + result ;
}

return result;
}

- Prashant August 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		
		String first = "101";
		String second = "111";
		
		System.out.print("result: " + first + " + " + second);
		int plus = 0;
		ArrayList<String> res = new ArrayList<>();
		
		for (int i = first.length(); i > 0; i--) {
			
			int start = i - 1;
			int end = i;
			String firstSub = first.substring(start, end);
//			System.out.println(i + firstSub);
			
			String secondSub = second.substring(start, end);
//			System.out.println(i + secondSub);
			
			if (firstSub.equals(secondSub) && firstSub.equals("1")) {
				
				if (plus == 1) {
					res.add("1");
				} else {
					res.add("0");
				}
				
				plus = 1;
				
			} else if (firstSub.equals(secondSub) && firstSub.equals("0")) {
				
				if (plus == 1) {
					res.add("1");
				} else {
					res.add("0");
				}
				
				plus = 0;
				
			} else {
				
				if (plus == 1) {
					res.add("0");
					plus = 1;
				} else {
					res.add("1");
					plus = 0;
				}
			}
			
		}
		
		if (plus == 1) {
			res.add("1");
		}
		
		StringBuilder result = new StringBuilder();
		
		for (int i = (res.size() - 1); i >= 0; i--) {
			result.append(res.get(i));
		}
		
		System.out.print(" = " + result);
	}

- zgr.dmr August 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String add(String s1, String s2) {
        int len = Math.max(s1.length(), s2.length()) + 1;
        final StringBuilder result = new StringBuilder(len);

        int carryOver=0;
        int pos=0;

        for(int s1Iter = s1.length()-1, s2Iter = s2.length()-1; s1Iter>=0 || s2Iter>=0; s1Iter--, s2Iter--, pos++){
            final int s1Val = s1Iter >=0 ? s1.charAt(s1Iter)-'0': '0', s2Val = s2Iter >=0 ? s2.charAt(s2Iter)-'0' : '0';
            final int subsum = s1Val + s2Val + carryOver;

            result.append(subsum % 2);
            carryOver = subsum/2;
        }

        if(carryOver==1) result.append(carryOver);

        return reverse(result.toString());
    }

- Yev August 25, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is more space-efficient. Running time O(n).

public static String add(String s1, String s2) {
        int len = Math.max(s1.length(), s2.length()) + 1;
        final StringBuilder result = new StringBuilder(len);

        int carryOver=0;
 

        for(int s1Iter = s1.length()-1, s2Iter = s2.length()-1; s1Iter>=0 || s2Iter>=0; s1Iter--, s2Iter--){
            final int s1Val = s1Iter >=0 ? s1.charAt(s1Iter)-'0': '0', s2Val = s2Iter >=0 ? s2.charAt(s2Iter)-'0' : '0';
            final int subsum = s1Val + s2Val + carryOver;

            result.append(subsum % 2);
            carryOver = subsum/2;
        }

        if(carryOver==1) result.append(carryOver);

        return reverse(result.toString());
    }

- Yev August 25, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution, O(n) no type cast or conversion:

public static String add(String s1, String s2) {
        StringBuilder result = new StringBuilder();
        char carry = '0';

        int i = s1.length() -1;
        int j = s2.length() -1;

        while(i >= 0 && j >= 0) {
            char a = s1.charAt(i);
            char b = s2.charAt(j);

            if (a == '0' && b == '0') {
                if (carry == '0') {
                    result.append("0");
                    carry = '0';
                }
                else {
                    result.append("1");
                    carry = '0';
                }
            }
            else if (a == '0' && b == '1' || a == '1' && b == '0') {
                if (carry == '0') {
                    result.append("1");
                    carry = '0';
                }
                else {
                    result.append("0");
                    carry = '1';
                }
            }
            else if (a == '1' && b == '1') {
                if (carry == '0') {
                    result.append("0");
                    carry = '1';
                }
                else {
                    result.append("1");
                    carry = '1';
                }
            }

            i--;
            j--;
        }

        while( i >= 0) {
            char a = s1.charAt(i);

            if (a == '0' && carry == '0') {
                result.append("0");
            }
            else if (a == '0' && carry == '1' || a == '1' && carry == '0') {
                result.append("1");
                carry = '0';
            }
            else if (a == '1' && carry == '1') {
                result.append("0");
                carry = '1';
            }

            i--;
        }

        while(j >= 0) {
            char a = s2.charAt(j);

            if (a == '0' && carry == '0') {
                result.append("0");
            }
            else if (a == '0' && carry == '1' || a == '1' && carry == '0') {
                result.append("1");
                carry = '0';
            }
            else if (a == '1' && carry == '1') {
                result.append("0");
                carry = '1';
            }

            j--;
        }

        if (carry == '1')
            result.append("1");

        return result.reverse().toString();
    }

- Freddy August 31, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution, O(n) with no type conversion:

public static String add(String s1, String s2) {
        StringBuilder result = new StringBuilder();
        char carry = '0';

        int i = s1.length() -1;
        int j = s2.length() -1;

        while(i >= 0 && j >= 0) {
            char a = s1.charAt(i);
            char b = s2.charAt(j);

            if (a == '0' && b == '0') {
                if (carry == '0') {
                    result.append("0");
                    carry = '0';
                }
                else {
                    result.append("1");
                    carry = '0';
                }
            }
            else if (a == '0' && b == '1' || a == '1' && b == '0') {
                if (carry == '0') {
                    result.append("1");
                    carry = '0';
                }
                else {
                    result.append("0");
                    carry = '1';
                }
            }
            else if (a == '1' && b == '1') {
                if (carry == '0') {
                    result.append("0");
                    carry = '1';
                }
                else {
                    result.append("1");
                    carry = '1';
                }
            }

            i--;
            j--;
        }

        while( i >= 0) {
            char a = s1.charAt(i);

            if (a == '0' && carry == '0') {
                result.append("0");
            }
            else if (a == '0' && carry == '1' || a == '1' && carry == '0') {
                result.append("1");
                carry = '0';
            }
            else if (a == '1' && carry == '1') {
                result.append("0");
                carry = '1';
            }

            i--;
        }

        while(j >= 0) {
            char a = s2.charAt(j);

            if (a == '0' && carry == '0') {
                result.append("0");
            }
            else if (a == '0' && carry == '1' || a == '1' && carry == '0') {
                result.append("1");
                carry = '0';
            }
            else if (a == '1' && carry == '1') {
                result.append("0");
                carry = '1';
            }

            j--;
        }

        if (carry == '1')
            result.append("1");

        return result.reverse().toString();
    }

- Freddy August 31, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function binaryAdd(numStr1, numStr2) {
    if (!numStr1) {
        return numStr2;
    } else if (!numStr2) {
        return numStr1;
    }
    
    let result = '';
    let longOne = numStr1.length >= numStr2.length ? numStr1 : numStr2;
    let shortOne = longOne === numStr1 ? numStr2 : numStr1;
    while (shortOne.length < longOne.length) {
        shortOne = '0' + shortOne;
    }
    let carry = 0;
    for (let i=longOne.length-1; i>=0; i--) {
        result  = ((parseInt(longOne[i]) + parseInt(shortOne[i]) + carry) % 2).toString() + result;
        carry = parseInt((parseInt(longOne[i]) + parseInt(shortOne[i]) + carry) / 2);
    }
    if (carry === 1) {
        result = '1' + result;
    }
    return result;
}

- Yoalnda August 31, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def binary_add(s1, s2):
    if len(s1) != len(s2):
        #TODO: left pad with zeros
        raise
    # should probably check if all digits are '1' or '0'

    carryon = '0'
    i = len(s1) - 1
    res = ""
    while i >= 0:
        num_zeros = sum(map(lambda i: is_zero(i), [s1[i], s2[i], carryon]))
        if num_zeros > 1:
            carryon = "0"
        else:
            carryon = "1"

        if num_zeros == 0 or num_zeros == 2:
            res = "1" + res
        else:
            res = "0" + res
        i = i - 1
    if carryon != "0":
        return "1" + res
    return res

- Rachel August 31, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Bute Force: Iterate over each pair of numbers and add them O(S1 + S2 + (MaxSize(S1, S2) + 1)) => O(MaxSize(S1,S2))
 * Pointer starts from last char and go over the string (index as a pointer)
 * And save carry value to be added in the next iteration
 * If I reach the end o the string and I still a carried value a need to add them to the final
 * That way the length of the result could be bigger than string
 * So, I need to reverse the string in the end
 * 
 * Optimization: I can compute the size of the small until I have a carried value, after that copy the last of bigger string
 * I can optimize my space, doing the sum in place, i.e., I can use the bigger string O(S1+2)
 * 
 */

function sum(s1, s2) {

  let p2 = s2.size - 1;
  let p1 = s1.size - 1;

  if (p1 > p2) {
    return add(s2, s1, p2, p1, 0);
  }
  return add(s1, s2, p1, p2, 0);
}

function add(s1, s2, p1, p2, carried) {
  if (p1 < 0  && carried === 0) {
    return s2;
  }
  const result = addNumber(s1[p1], s2[p2], carried);
  s2[p2] = result.value;

  add(s1, s2, p1--, p2--, result.carried);
}

/*
* 1 + 1 + 1 = 1 1
  1 + 0 + 1 = 0 1
  0 + 0 + 1 = 1 0
*/

function addNumber(char1=0, char2, c) {
  let value = 0;
  let carried = 0;
  const n1 = Number(char1);
  const n2 = Number(char2);
  if (n1 === 1 && n2 === 1) {
    value = c;
    carried = 1;
  }
  else if (n1 !== n2) {
    value = c === 1 ? 0 : 1;
  } else {
    value = c;
  }
  return {
    value,
    carried
  }
}

- Keilla September 05, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Brute force: Iterate over each pair of numbers and add them O(S1 + S2 + (MaxSize(S1, S2) + 1)) => O(MaxSize(S1,S2))
 * Pointer starts from last char and go over the string (index as a pointer)
 * And save carry value to be added in the next iteration
 * If I reach the end o the string and I still a carried value a need to add them to the final
 * That way the length of the result could be bigger than string
 * So, I need to reverse the string in the end
 * 
 * Optimization: I can compute the size of the small until I have a carried value, after that copy the last of bigger string
 * I can optimize my space, doing the sum in place, i.e., I can use the bigger string O(S1+2)
 * 
 */

function sum(s1, s2) {

  let p2 = s2.size - 1;
  let p1 = s1.size - 1;

  if (p1 > p2) {
    return add(s2, s1, p2, p1, 0);
  }
  return add(s1, s2, p1, p2, 0);
}

function add(s1, s2, p1, p2, carried) {
  if (p1 < 0  && carried === 0) {
    return s2;
  }
  const result = addNumber(s1[p1], s2[p2], carried);
  s2[p2] = result.value;

  add(s1, s2, p1--, p2--, result.carried);
}

/*
* 1 + 1 + 1 = 1 1
  1 + 0 + 1 = 0 1
  0 + 0 + 1 = 1 0
*/

function addNumber(char1=0, char2, c) {
  let value = 0;
  let carried = 0;
  const n1 = Number(char1);
  const n2 = Number(char2);
  if (n1 === 1 && n2 === 1) {
    value = c;
    carried = 1;
  }
  else if (n1 !== n2) {
    value = c === 1 ? 0 : 1;
  } else {
    value = c;
  }
  return {
    value,
    carried
  }
}

- keilla September 05, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# PYTHON PROGRAM

binary1 = "101101"
binary2 = "111011"
binary_sum = []

# Use a dictionary with all possible addends
# and their sum and remainders
# key = "prev_remainder, b1, b2"
# value = "curr_remainder, curr_sum"
d = {}
d['0','0','0'] = ['0','0']
d['0','0','1'] = ['0','1']
d['0','1','0'] = ['0','1']
d['0','1','1'] = ['1','0']

d['1','0','0'] = ['0','1']
d['1','0','1'] = ['1','0']
d['1','1','0'] = ['1','0']
d['1','1','1'] = ['1','1']

prev_remainder = '0'
for b1, b2 in zip(binary1, binary2):
curr_remainder, curr_sum = d[prev_remainder,b1,b2]
binary_sum.append(curr_sum)
prev_remainder = curr_remainder

binary_sum.append(prev_remainder)
binary_sum.reverse()
print(''.join(map(str,binary_sum)))

- Naveen September 08, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Implementation using Dictionary:

binary1 = "101101"
binary2 = "111011"
binary_sum = []

# Use a dictionary with key = addends and 
# values as remainder and sum
# key = "prev_remainder, b1, b2"
# value = "curr_remainder, curr_sum"
d = {}
d['0','0','0'] = ['0','0']
d['0','0','1'] = ['0','1']
d['0','1','0'] = ['0','1']
d['0','1','1'] = ['1','0']

d['1','0','0'] = ['0','1']
d['1','0','1'] = ['1','0']
d['1','1','0'] = ['1','0']
d['1','1','1'] = ['1','1']

prev_remainder = '0'
for b1, b2 in zip(binary1, binary2):
    curr_remainder, curr_sum = d[prev_remainder,b1,b2]
    binary_sum.append(curr_sum)
    prev_remainder = curr_remainder

binary_sum.append(prev_remainder)
binary_sum.reverse()
print(''.join(map(str,binary_sum)))

- Naveen September 08, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const numberOne = '11';
const numberTwo = '11';

function sumBin(num1, num2, position1, position2, carry = 0) {

    if(position1 < 0 && position2 < 0) {
        return carry > 0 ? carry : '';
    }
    const bin1 = num1.charAt(position1) - 0;
    const bin2 = num2.charAt(position2) - 0;
    const sum = bin1 + bin2 + carry;
    const result = sum % 2;

    return sumBin(num1, num2, position1 - 1, position2 - 1, sum > 1 ? 1 : 0) + `${result}`;
}

const result = sumBin(numberOne, numberTwo, numberOne.length - 1, numberTwo.length - 1);

- Dorin September 10, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String calculate(String a, String b) {
		int aLen = a.length();
		int bLen = b.length();
		if(aLen < bLen) {
			int diffCount = bLen - aLen;
			a = "0".repeat(diffCount) + a;
		} else if(aLen > bLen) {
			int diffCount = aLen - bLen;
			b = "0".repeat(diffCount) + b;
		}

		Stack<String> xNum = new Stack<>();
		Stack<String> yNum = new Stack<>();
		for (char c : a.toCharArray()) {
			xNum.add(String.valueOf(c));
		}
		for (char c : b.toCharArray()) {
			yNum.add(String.valueOf(c));
		}

		return result = add("", xNum, yNum, "0");
	}

public String add(String result, Stack<String> num1, Stack<String> num2, String carry) {
		if(num1.isEmpty()) {
			return result + carry;
		}
		String bit1 = num1.pop();
		String bit2 = num2.pop();
		long numberOfOnes = (bit1 + bit2 + carry).chars().filter(c -> c == '1').count();
		String newCarry = null;
		String tempResult = null;
		if(numberOfOnes == 0) {
			newCarry = "0";
			tempResult = "0";
		} else if(numberOfOnes == 1) {
			newCarry = "0";
			tempResult = "1";
		} else if(numberOfOnes == 2) {
			newCarry = "1";
			tempResult = "0";
		} else if(numberOfOnes == 3) {
			newCarry = "1";
			tempResult = "1";
		}
		return add(tempResult, num1, num2, newCarry) + result;
	}

- esoner.sezgin September 13, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <algorithm>

std::string bsum(std::string str1, std::string str2) {
    
    std::string result;
    
    int acc =  0;
    auto it1 = str1.rbegin();
    auto it2 = str2.rbegin();
    
    for (; it1 != str1.rend() && it2 != str2.rend(); it1++, it2++) {
        if (*it1 == *it2) {
            if (*it1 == '1') {
                (acc == 0) ? result.push_back('0') : result.push_back('1');
                acc = 1;
            }
            else {
                (acc == 1) ? result.push_back('1') : result.push_back('0');
                acc = 0;
            }
        }
        else {
            if (*it1 != *it2) {
                if (acc == 1) {
                    result.push_back('0');
                    acc = 1;
                }
                else {
                    result.push_back('1');
                    acc = 0;
                }
            }
        }
    }
    
    if (it1 != str1.rend()) {
        while (it1 != str1.rend()) {
            if (*it1 == '1') {
                (acc == 0) ? result.push_back('1') : result.push_back('0');
            }
            else {
                (acc == 0) ? result.push_back('0') : result.push_back('1');
                acc = 0;
            }
            it1++;
        }
    }
    else {
        if (it2 != str2.rend()) {
            while (it2 != str2.rend()) {
                if (*it2 == '1') {
                    (acc == 0) ? result.push_back('1') : result.push_back('0');
                }
                else {
                    (acc == 0) ? result.push_back('0') : result.push_back('1');
                    acc = 0;
                }
                it2++;
            }
        }
    }
    
    if (acc) {
        result.push_back('1');
    }
  
    std::reverse(result.begin(), result.end());
  
    return result;
}

- arturocu81 October 11, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function sum(a, b, carry) {
    const aN = a === '0' ? 0 : 1;
    const bN = b === '0' ? 0 : 1;
    return aN + bN + carry;
}

function addBinary(A, B) {
    let result = '';
    let aIdx = A.length -1;
    let bIdx = B.length -1;
    let carry = 0;
    while (aIdx >=0 || bIdx >=0) {
        const aDigit = aIdx >=0 ? A[aIdx] : '0';
        const bDigit = bIdx >=0 ? B[bIdx] : '0';
        aIdx--;
        bIdx--;
        const total = sum(aDigit, bDigit, carry);
        const digit = (total%2 === 0) ? 0 : 1;
        carry = (total>1) ? 1 : 0;
        
        result = digit + result;
    }
    if (carry) result = carry + result;
    return result;
}

- Pablo October 19, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// /*
// * implement binary additions of two strings
// * s1 = "1010011"
// * s2 = " 101"
// */


char add_char (char c1, char c2, char *c) {
int c1N = c1 == '0' ? 0 : 1;
int c2N = c2 == '0' ? 0 : 1;
int carryN = *c == '0' ? 0 : 1;
char sum = (c1N + c2N + carryN)%2 ? '1' : '0';

*c = (c1N + c2N + carryN)/2 ? '1' : '0';
return sum;

}

char * add_binary (char *s1, char *s2)
{
char * result = NULL;
int l1 = strlen(s1);
int l2 = strlen(s2);
int len;
if (l1 == 0)
return s2;

if (l2 == 0)
return s1;

if (l1 >= l2) {
result = calloc(l1, sizeof(char));
len = l1;
} else {
result = calloc(l2, sizeof(char));
len = l2;
}

if (result == NULL)
return NULL;

char carry = '0';
int index1 = strlen(s1);
int index2 = strlen(s2);
int rindex = len;

while (rindex > 0) {
result[--rindex] = add_char(
(index1 > 0) ? s1[--index1] : '0',
(index2 > 0) ? s2[--index2] : '0',
&carry);
}

return result;

}


int main(void)
{
char * result = add_binary("1010011", "101");
printf("%s\n", result);
free(result);
return 0;
}

- Anonymous October 20, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
public static void main(String[] args) {
System.out.println(add("01", "1101"));
}

public static String add(String s1, String s2) {
StringBuilder result = new StringBuilder();
char carry = '0';

int i = s1.length() -1;
int j = s2.length() -1;

if(i > j)
{
int diff = i-j;
int x =0;
for(x=0; x<diff; x++){
s2 = '0' + s2;
}
}else{
int diff = j-i;
int x =0;
for(x=0; x<diff; x++){
s1 = '0' + s1;
}
}
System.out.println("s1: " + s1 +"\n");
System.out.println("s2: " + s2 +"\n");

i = s1.length() -1;
j = s2.length() -1;

while(i >= 0 && j >= 0) {
char a = s1.charAt(i);
char b = s2.charAt(j);

if (a == '0' && b == '0') {
if (carry == '0') {
result.append("0");
carry = '0';
}
else {
result.append("1");
carry = '0';
}
}
else if (a == '0' && b == '1' || a == '1' && b == '0') {
if (carry == '0') {
result.append("1");
carry = '0';
}
else {
result.append("0");
carry = '1';
}
}
else if (a == '1' && b == '1') {
if (carry == '0') {
result.append("0");
carry = '1';
}
else {
result.append("1");
carry = '1';
}
}

i--;
j--;

System.out.println("result: " + result +"\n");
}

if(carry !='0')
return '1' + result.reverse().toString();
else
return result.reverse().toString();
}
}

- AJ October 23, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
  public static void main(String[] args) {
    System.out.println(add("01", "1101"));
  }
  
  public static String add(String s1, String s2) {
        StringBuilder result = new StringBuilder();
        char carry = '0';

        int i = s1.length() -1;
        int j = s2.length() -1;
    
        if(i > j)
        {
          int diff = i-j;
          int x =0;
          for(x=0; x<diff; x++){
            s2 = '0' + s2;
          }
        }else{
          int diff = j-i;
          int x =0;
          for(x=0; x<diff; x++){
            s1 = '0' + s1;
          }
        }
        System.out.println("s1: " + s1 +"\n");
        System.out.println("s2: " + s2 +"\n");
    
        i = s1.length() -1;
        j = s2.length() -1;

        while(i >= 0 && j >= 0) {
            char a = s1.charAt(i);
            char b = s2.charAt(j);

            if (a == '0' && b == '0') {
                if (carry == '0') {
                    result.append("0");
                    carry = '0';
                }
                else {
                    result.append("1");
                    carry = '0';
                }
            }
            else if (a == '0' && b == '1' || a == '1' && b == '0') {
                if (carry == '0') {
                    result.append("1");
                    carry = '0';
                }
                else {
                    result.append("0");
                    carry = '1';
                }
            }
            else if (a == '1' && b == '1') {
                if (carry == '0') {
                    result.append("0");
                    carry = '1';
                }
                else {
                    result.append("1");
                    carry = '1';
                }
            }

            i--;
            j--;
          
          System.out.println("result: " + result +"\n");
        }
    
        if(carry !='0')
          return '1' + result.reverse().toString();
        else
          return result.reverse().toString();
    }
}

- AJ October 23, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n1="101101"
n2="111101"
n3=""
i=len(n1)
c=0
while i>=0:
    if (n1[i-1]=="0" and n2[i-1]=="0" and c==0): #0
        c=0
        n3="0" +n3
    elif (n1[i-1]=="1" and n2[i-1]=="0" and c==0) or (n1[i-1]=="0" and n2[i-1]=="1" and c==0) or (n1[i-1]=="0" and n2[i-1]=="0" and c==1):#1
        n3="1"+n3
        c=0
    if (n1[i-1]=="1" and n2[i-1]=="1" and c==0) or (n1[i-1]=="1" and n2[i-1]=="0" and c==1) or (n1[i-1]=="0" and n2[i-1]=="1" and c==1):#2
        c=1
        n3="0"+n3
    elif (n1[i-1]=="1" and n2[i-1]=="1" and c==1):#3
        c=1
        n3="1"+n3
    i=i-1

print(n3)

- Alok October 27, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from itertools import zip_longest

def add(a, b):
    def gen_add():
        c = 0
        for i, j in zip_longest(reversed(a), reversed(b), fillvalue='0'):
            n = (ord(i) - ord('0')) + (ord(j) - ord('0')) + c
            yield chr(ord('0') + n % 2)
            c = n // 2
        if c:
            yield chr(ord('0') + c)
    
    return ''.join(reversed(list(gen_add())))

print(add('101101', '111101'))

- ne0 October 27, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript

var addBinary = function(a, b) {
     var loop = Math.max(a.length, b.length)
     var carry = 0
     let result = []
     let arrA = a.split('')
     let arrB = b.split('')
    for (var i = 0 ; i <= loop ; i++)  {
        const pos = parseInt(arrA.pop() || 0) + parseInt(arrB.pop() || 0) + carry
        carry = pos >= 2 ? 1 : 0
        if (pos === 1 || pos === 3) {
          result.unshift(1)
        } else if (pos === 2 || (pos === 0 && (i < loop - 1))) {
          result.unshift(0)
        }
    }
    return result.join('') || '0'
};

- rwu October 30, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const helperObject = {
    0: [0, 0],
    1: [1, 0],
    2: [0, 1],
    3: [1, 1]
};
function sumBinary(str1, str2) {
    //todo: edge cases
    let maxLength = Math.max(str1.length, str2.length);
    let result = '';
    let carry = '';

    for (let i = 0; i < maxLength; i++) {
        const sum = +(str1[str1.length - i - 1] ?? 0) + +(str2[str2.length - i - 1] ?? 0) + carry;
        let newChar = '';
        [newChar, carry] = helperObject[sum];
        result = newChar + result;
    }
    return carry === 1 ? carry + result : result;
}

- Mehrdad November 12, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const helperObject = {
    0: [0, 0],
    1: [1, 0],
    2: [0, 1],
    3: [1, 1]
};
function sumBinary(str1, str2) {
    const len1 = str1.length;
    const len2 = str2.length
    let maxLength = Math.max(len1, len2);
    let result = '';
    let carry = '';

    for (let i = 0; i < maxLength; i++) {
        const sum = +(str1[len1 - i - 1] ?? 0) + +(str2[len2 - i - 1] ?? 0) + carry;
        let newChar = '';
        [newChar, carry] = helperObject[sum];
        result = newChar + result;
    }
    return carry === 1 ? carry + result : result;
}

- Mehrdad November 12, 2020 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More