Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
My little try with JS:
sumBinaryNumbers = function (b1, b2) {
var i1 = b1.length - 1;
var i2 = b2.length - 1;
var sum = [];
var carry = 0;
while (i1 >= 0 || i2 >= 0) {
var bit1 = i1 >= 0 ? parseInt(b1[i1--]) : 0;
var bit2 = i2 >= 0 ? parseInt(b2[i2--]) : 0;
var bitSum = bit1 + bit2 + carry;
var bit = 0;
switch (bitSum) {
case 3:
bit = 1;
carry = 1;
break;
case 2:
bit = 0;
carry = 1;
break;
case 1:
bit = 1;
carry = 0;
break;
default:
bit = 0;
carry = 0;
break;
}
sum.push(bit);
}
if (carry > 0) {
sum.push(carry);
}
return (sum.reverse().join(""));
};
std::string addTwoBinaryStrings(std::string a, std::string b)
{
size_t i = a.length() - 1;
size_t j = b.length() - 1;
int carry = 0;
int size = i > j? i+2: j+2;
int index = size - 1;
char * result = new char[size];
while(i >= 0 || j >= 0)
{
int m = i >= 0? a[i--] - '0' : 0;
int n = j >= 0? b[j--] - '0' : 0;
result[index--] = m ^ n ^ carry + '0';
carry = m & n || m & carry || n & carry;
}
result[index] = carry + '0';
return string(result);
}
public String addBinaryNumbers(String num1, String num2) {
int carryflag = 0, i1 = num1.length() - 1, i2 = num2.length() - 1;
StringBuilder sum = new StringBuilder();
while (i1 >= 0 || i2 >= 0) {
int c1 = i1 >= 0 ? Character.digit(num1.charAt(i1--), 2) : 0;
int c2 = i2 >= 0 ? Character.digit(num2.charAt(i2--), 2) : 0;
int next_bit = c1 ^ c2 ^ carryflag;
carryflag = (c1 & c2 & ~carryflag) | (~c1 & c2 & carryflag) | (c1 & ~c2 & carryflag) | (c1 & c2 & carryflag);
sum.append(next_bit == 1 ? '1' : '0');
}
if (carryflag == 1) {
sum.append('1');
}
return sum.reverse().toString();
}
/**
* Write a program to sum two binary numbers represented as strings.
* Input: "110", "01101"
* Output: "10011"
* Method signature:
* public String addBinaryNumbers(String num1, String num2);
*
*/
public class BinarySum {
private static final int[] binaryValues = { 1, 2, 4, 8, 16, 32, 64, 128 };
public static void main(String[] args) {
String num1 = "110";
String num2 = "01101";
System.out.println("Add " + num1 + " to " + num2);
String answer = addBinaryNumbers(num1, num2);
System.out.println("Answer: " + answer);
}
private static String addBinaryNumbers(String num1, String num2) {
char[] charNum1 = num1.toCharArray();
char[] charNum2 = num2.toCharArray();
int intAnswer = addBinaryNumbers(charNum1, charNum2);
String binaryAnswer = convertToBinaryString(intAnswer);
return binaryAnswer;
}
private static int addBinaryNumbers(char[] num1, char[] num2) {
int totalNum1 = toBinaryValue(num1);
int totalNum2 = toBinaryValue(num2);
System.out.println("Add " + totalNum1 + " to " + totalNum2);
int total = totalNum1 + totalNum2;
System.out.println("Answer: " + total);
return total;
}
private static int toBinaryValue(char[] num) {
int total = 0;
for (int i = 0; i < num.length; i++) {
if (num[(num.length - 1) - i] == '1') {
total += binaryValues[i];
}
}
return total;
}
private static String convertToBinaryString(int value) {
StringBuilder binaryString = new StringBuilder();
for (int i = binaryValues.length - 1; i >= 0; i--) {
int binaryValue = binaryValues[i];
if ((value - binaryValue) >= 0) {
value -= binaryValue;
binaryString.append("1");
} else {
binaryString.append("0");
}
}
return binaryString.toString();
}
}
Very Lucky Fellow to get this question @ FB... Here it goes
1> Reverse Each String . O(n) + O(m)
2> Pointer p1 and p2 to string 1 and 2 respectively.
3> Set Overflow = 0;
4> string *s;
5> Loop until each string finishes
{
s=*p1+*p2+overflow;
overflow=*p1+*p2;
if(overflow==2)
overflow =1;
else
overflow=0;
p1++;
p2++;
s++;
}
Total Time = O(n)+O(m)+O(m or n {which ever is higher})
Dryrun for this algo:
a. reverse string(110) 011
b. reverse string(01101) 10110
P and Q are two pointers pointing to *start* of 'a' string and 'b' string respectively.
So adding 011 + 10110 => 11001
Need to reverse this string again to get the result.This is missing from algorithm mentioned above.
Easy said than done! Anyone can say step 1 do this, step 2 do that. But what the interviewers expect is a clean code. A bug free code catching all the corner cases. Have you ever heard of white paper coding ? If so, its time you go and learn a few more. He is not the lucky guy, you might get bumped out with this question.
Well thanks for the aggressive response but fellow if U can't code what U designed. Perhaps U should learn how to code than.. We in here are pretty much fluent in coding with more than 5 years of product development experience feels little bit more challenge to put correct algo before code.
With your expression it seems U are Fresher so yea U need to learn to code first before attempting anything stupid.. Happy Learning
std::string addTwoBinaryStrings(std::string a, std::string b)
{
int len1=a.size(), len2=b.size();
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int t=min(len1, len2);
int carry=0;
string res="";
for (int i=0; i<t; ++i) {
int m=a[i]-'0';
int n=b[i]-'0';
int p=m+n+carry;
switch (p) {
case 3:
res+="1";
carry=1;
break;
case 2:
res+="0";
carry=1;
break;
case 1:
res+="1";
carry=0;
break;
case 0:
res+="0";
carry=0;
break;
default:
break;
}
}
char num[10];
if (len1>t) {
for (int i=t; i<len1; ++i) {
int m=a[i]-'0';
if (m+carry>1) {
res+="1"; carry=1;
}
else {
itoa(m+carry, num, 10);
res+=num;
carry=0;
}
}
}
if (len2>t) {
for (int i=t; i<len2; ++i) {
int m=b[i]-'0';
if (m+carry==2) {
res+="0"; carry=1;
}
else if (m+carry==3) {
res+="1"; carry=1;
}
else {
itoa(m+carry, num, 10);
res+=num;
carry=0;
}
}
}
reverse(res.begin(), res.end());
return res;
}
correct the code
std::string addTwoBinaryStrings(std::string a, std::string b)
{
int len1=a.size(), len2=b.size();
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int t=min(len1, len2);
int carry=0;
string res="";
for (int i=0; i<t; ++i) {
int m=a[i]-'0';
int n=b[i]-'0';
int p=m+n+carry;
switch (p) {
case 3:
res+="1";
carry=1;
break;
case 2:
res+="0";
carry=1;
break;
case 1:
res+="1";
carry=0;
break;
case 0:
res+="0";
carry=0;
break;
default:
break;
}
}
char num[10];
if (len1>t) {
for (int i=t; i<len1; ++i) {
int m=a[i]-'0';
if (m+carry>1) {
res+="1"; carry=1;
}
else {
itoa(m+carry, num, 10);
res+=num;
carry=0;
}
}
}
if (len2>t) {
for (int i=t; i<len2; ++i) {
int m=b[i]-'0';
if (m+carry==2) {
res+="0"; carry=1;
}
else if (m+carry==3) {
res+="1"; carry=1;
}
else {
itoa(m+carry, num, 10);
res+=num;
carry=0;
}
}
}
if (carry==1) res+="1";
reverse(res.begin(), res.end());
return res;
}
public static String addBinaryNumbers(String num1, String num2){
char [] chleft=num1.toCharArray();
char [] chright=num2.toCharArray();
StringBuilder sb=new StringBuilder();
int p1=chleft.length-1;
int p2=chright.length-1;
int next=0;
int sum=0;
while (p1>=0||p2>=0){
sum=0;
if (p1>=0){
sum+=getDec(chleft[p1]);
p1--;
}
if (p2>=0){
sum+=getDec(chright[p2]);
p2--;
}
sum+=next;
if (sum>=2){
sum=sum-2;
next=1;
}else{
next=0;
}
sb.append(sum);
}
if (next>0){
sb.append(next);
}
return sb.reverse().toString();
}
public static int getDec(char ch){
return ch-'0';
}
public static String AddBinaryNumbers(String s1, String s2) {
if (s1 == null && s2 == null)
return null;
while (s1.length() != s2.length()) {
if (s1.length() > s2.length()) {
s2 = "0" + s2;
} else
s1 = "0" + s1;
}
int len = s1.length() - 1;
char c1[] = s1.toCharArray();
char c2[] = s2.toCharArray();
String result = "";
int carry = 0;
while (len != -1) {
int temp = (c1[len] - '1' + 1 ^ c2[len] - '1' + 1) ^ carry;
carry = (c1[len] - '1' + 1 & c2[len] - '1' + 1) ^ carry;
result = temp + result;
len = len - 1;
}
System.out.print(result);
return result;
}
This is super easy to implement in python:
s1 = "110"
s2 = "01101"
def max_len(s1, s2)
[a, b] = [s1, s2] if len(s1) >= len(s2) else [s2, s1]
b = "".join(['0']*(len(a)-len(b)))+b
i = len(a) - 1
j = len(b) - 1
c = '0'
result = []
while i >= 0:
s = 0
for x in [a[i], b[j], c]:
if x == '1':
s = s + 1
c = '1' if s >=2 else '0'
result.insert(0, ('0' if s % 2 == 0 else '1'))
i = i - 1
j = j - 1
return "".join(result)
public static String add(String bin1, String bin2) {
String result = "";
String longer = bin1.length() > bin2.length() ? bin1 : bin2;
String smaller = bin1.length() > bin2.length() ? bin2 : bin1;
int diff = longer.length() - smaller.length();
result = result.concat(longer.substring(0, diff));
longer = longer.substring(diff, longer.length());
for (int i = 0; i < smaller.length(); i++) {
result = result.concat((Character.getNumericValue(longer.charAt(i))| Character.getNumericValue(smaller.charAt(i)))+"");
}
return result;
}
private static String addBitStrings(String num1, String num2){
if(num1.length() > num2.length()){
num2 = makeEqualLength(num2, num1.length()-num2.length());
}
else{
num1 = makeEqualLength(num1, num2.length()-num1.length());
}
String output = calculateSum(num1, num2);
return output;
}
private static String calculateSum(String num1, String num2){
StringBuilder output = new StringBuilder();
char carry = '0';
for(int i = num1.length()-1;i>=0;i--){
char c1 = num1.charAt(i);
char c2 = num2.charAt(i);
if(c1!=c2){
output.append("1");
carry = '0';
}
else if(c1 == c2){
output.append(carry);
carry = c1;
}
}
if(carry>'0')
output.append(carry);
return output.reverse().toString();
}
private static String makeEqualLength(String num, int len){
while(len>0){
num = "0"+num;
len--;
}
return num;
}
private static String addBitStrings(String num1, String num2){
if(num1.length() > num2.length()){
num2 = makeEqualLength(num2, num1.length()-num2.length());
}
else{
num1 = makeEqualLength(num1, num2.length()-num1.length());
}
String output = calculateSum(num1, num2);
return output;
}
private static String calculateSum(String num1, String num2){
StringBuilder output = new StringBuilder();
char carry = '0';
for(int i = num1.length()-1;i>=0;i--){
char c1 = num1.charAt(i);
char c2 = num2.charAt(i);
if(c1!=c2){
output.append("1");
carry = '0';
}
else if(c1 == c2){
output.append(carry);
carry = c1;
}
}
if(carry>'0')
output.append(carry);
return output.reverse().toString();
}
private static String makeEqualLength(String num, int len){
while(len>0){
num = "0"+num;
len--;
}
return num;
}
//to add two binary equivalent
import java.io.*;
import java.util.*;
public class adtbin
{ static Scanner sc=new Scanner(System.in);
public void fun(int n1)
{
int i=0;
int sum[]=new int[20];
while(n1>0)
{
sum[i]=n1%2;
n1=n1/2;
i++;
}
for(int a=i-1;a>=0;a--)
{
System.out.print(sum[a]);
}
}
public static void main()
{
int m,n,add;
adtbin ob=new adtbin();
System.out.println("enter the value of m and n");
m=sc.nextInt();
n=sc.nextInt();
add=m+n;
ob.fun(add);
}
}
public String addBinaryNumbers(String num1, String num2) {
String longestNumber = num1.length() > num2.length() ? num1 : num2;
int padCount = longestNumber == num1 ? num1.length() - num2.length() : num2.length() - num1.length();
String pad = "";
for(int i = 0; i < padCount; i++)
pad += "0";
if(longestNumber == num1)
{
num2 = pad + num2;
}
else
{
num1 = pad + num1;
}
String result = "";
int carry = 0;
for(int i = longestNumber.length() - 1; i >= 0; i--)
{
int num1Int = Integer.parseInt(num1.charAt(i)+"");
int num2Int = Integer.parseInt(num2.charAt(i)+"");
int currentSum = num1Int + num2Int + carry;
if(currentSum >= 2)
{
carry = 1;
if(currentSum == 2)
result += "0";
else
result += "1";
}
else
{
carry = 0;
result += currentSum;
}
}
if(carry == 1)
result += carry;
String finalResult = "";
for(int i = result.length() - 1; i >= 0; i--)
finalResult += result.charAt(i);
return finalResult;
}
string decimal_to_binary_string(unsigned int n) {
string num = "";
while(n) {
num = ((n%2) ? "1":"0") + num;
n /= 2;
}
num += (!num.size() ? "0":"");
return num;
}
string binary_sum(string num1, string num2) {
return decimal_to_binary_string(strtoul(num1.c_str(), NULL, 2) +
strtoul(num2.c_str(), NULL, 2));
}
/**
*
* N = max(num1.length, num2.length)
*
* time: O(N))
* space: O(N)
*
* @param num1
* @param num2
* @return
*/
public static String addBinaryNumbers( String num1, String num2 ){
if( num1 == null || num2 == null ){
throw new IllegalArgumentException("NULL string passed");
}
if( "".equals(num1.trim()) || "".equals(num2.trim()) ){
throw new IllegalArgumentException("EMPTY string passed");
}
final int length1 = num1.length();
final int length2 = num2.length();
final StringBuilder buf = new StringBuilder( Math.max(length1, length2) + 1 );
int carry = 0;
int index = 0;
int digit1, digit2, res;
while( index < length1 || index < length2 ){
digit1 = index < length1 ? (num1.charAt(index) - ZERO_CH_VALUE) : 0;
if( digit1 != 0 && digit1 != 1 ){
throw new IllegalArgumentException("Not a binary string: '" + num1 + "'");
}
digit2 = index < length2 ? (num2.charAt(index) - ZERO_CH_VALUE) : 0;
if( digit2 != 0 && digit2 != 1 ){
throw new IllegalArgumentException("Not a binary string: '" + num2 + "'");
}
res = digit1 + digit2 + carry;
buf.append( res & 1 );
carry = res >>> 1;
++index;
}
if( carry > 0 ){
buf.append( carry );
}
return buf.toString();
}
This solution assumes the strings are stored as the reverse of how they're stored according the problem description. Solution looks right at least conceptually aside from that.
changing to this will work: no need to reverse the string
at line 33
digit1 = index < length1 ? (num1.charAt(length1 - 1 - index) - ZERO_CH_VALUE) : 0;
at line 39
digit2 = index < length2 ? (num2.charAt(length2 - 1 - index) - ZERO_CH_VALUE) : 0;
public static String returnZero(int len){
String str="";
for(int i=0;i<len;i++){
str+="0";
}
return str;
}
public static String addBinaryNumbers(String s1,String s2){
String result = "";
int carry = 0;
if(s1.length()>s2.length()){
s2= CompairString.returnZero(s1.length()-s2.length())+s2;
}else{
s1= CompairString.returnZero(s2.length()-s1.length())+s1;
}
for(int i=s1.length()-1;i>=0;i--){
int num1Int = Integer.parseInt(s1.charAt(i)+"");
int num2Int = Integer.parseInt(s2.charAt(i)+"");
int currentSum = num1Int + num2Int + carry;
if(currentSum >= 2)
{
carry = 1;
if(currentSum == 2)
result += "0";
else
result += "1";
}
else
{
carry = 0;
result += currentSum;
}
}
if(carry == 1)
result += carry;
String finalResult = "";
for(int i = result.length() - 1; i >= 0; i--)
finalResult += result.charAt(i);
return finalResult;
}
string AddBinaryNum(string s1, string s2) {
string s3 = "";
int carry =0;
int l1 = s1.length()-1;
int l2 = s2.length()-1;
while(l1 >=0 || l2 >=0)
{
int sum = carry + (l1>=0? s1[l1--]-'0': 0 )+ (l2>=0 ? s2[l2--]-'0': 0);
if(sum == 3 || sum ==1) {
s3.insert(s3.begin(), 1, '1');
}
else s3.insert(s3.begin(), 1, '0');
if(sum >= 2) carry = 1;
else carry = 0;
}
if(carry) s3.insert(s3.begin(), 1, '1');
return s3;
}
static void Main(string[] args) { String a1 = "00000000"; String a2 = "00000"; String a3=null; char Res = '\0'; char carry = '0'; int a1Len = a1.Length; int a2Len = a2.Length; if (a2Len>a1Len) { for (int i =0; i<(a2Len - a1Len); i++) { a1 = "0" + a1; } } if (a1Len > a2Len) { for (int i =0; i<(a1Len -a2Len); i++) { a2 = "0" + a2; } } for ( int i = a1.Length-1; i >=0 ; i--) //a1/Length now contains original length { if (a1[i].Equals('0') && a2[i].Equals('0') && carry.Equals('0')) { Res = '0'; carry = '0'; } else if (a1[i].Equals('0') && a2[i].Equals('1') && carry.Equals('0')) { Res = '1'; carry = '0'; } else if (a1[i].Equals('1') && a2[i].Equals('0') && carry.Equals('0')) { Res = '1'; carry = '0'; } else if (a1[i] == '1' && a2[i]=='1' && carry == '0') { Res = '0'; carry = '1'; } else if (a1[i] == '0' && a2[i]=='0' && carry == '1') { Res = '1'; carry = '0'; } else if (a1[i] == '0' && a2[i]=='1' && carry == '1') { Res = '0'; carry = '1'; } else if (a1[i] == '1' && a2[i]=='0' && carry == '1') { Res = '0'; carry = '1'; } else if (a1[i] == '1' && a2[i]=='1' && carry == '1') { Res = '1'; carry = '1'; } a3 = Res + a3; Res = '0'; } if (carry == '1') a3=carry+a3; Console.WriteLine(a3); Console.ReadLine(); } }}/*
std::string addTwoBinaryStrings(std::string a, std::string b)
{
size_t i = a.length() - 1;
size_t j = b.length() - 1;
int carry = 0;
char * result = new char[i > j? i+2: j+2];
while(i >= 0 && j >= 0)
{
int m = a[i] - '0';
int n = b[j] - '0';
*result++ = m ^ n ^ carry + '0';
carry = m & n || m & carry || n & carry;
i--;
j--;
}
while(i >= 0)
{
int m = a[i] - '0';
*result++ = m ^ carry + '0';
carry = m & carry;
i--;
}
while(j >= 0)
{
int n = b[j] - '0';
*result++ = n ^ carry + '0';
carry = n & carry;
j--;
}
*result = carry + '0';
std::string str_to_return(result);
return str_to_return;
}
std::string add(std::string a, std::string b)
{
size_t i = a.length();
size_t j = b.length();
int carry = 0;
int size = i > j? i+1: j+1;
int index = size;
char * result = new char[size];
while(i > 0 || j > 0)
{
int m = i > 0? a[--i] - '0' : 0;
int n = j > 0? b[--j] - '0' : 0;
result[--index] = m ^ n ^ carry + '0';
carry = m & n || m & carry || n & carry;
}
result[--index] = carry + '0';
std::string rstr(result);
return rstr;
}
My try.........
I learnt a lot while trying this code..........
string is not immuttable and about string buffer and string builder etc...........
import java.io.*;
import java.lang.*;
class Binadd
{
public static void main(String a[])
{
String n1,n2;
StringBuffer n3;
char c='0';
int l1,l2,i,j,l;
DataInputStream dis=new DataInputStream(System.in);
try
{
System.out.println("Enter the 2 numbers");
n1=dis.readLine();
n2=dis.readLine();
l1=n1.length();
l2=n2.length();
if(l1>=l2)
{
n3=new StringBuffer(n1);
l=l1-1;
}
else
{
n3=new StringBuffer(n2);
l=l2-1;
}
for(i=l1-1,j=l2-1;(i>=0)&&(j>=0);i--,j--)
{
if(c=='0')
{
if((n1.charAt(i)=='1')&&(n2.charAt(j)=='1'))
{
n3.setCharAt(l--,'0');
c='1';
}
else if((n1.charAt(i)=='0')&&(n2.charAt(j)=='0'))
{
n3.setCharAt(l--,'0');
c='0';
}
else
{
n3.setCharAt(l--,'1');
c='0';
}
}
else
{
if((n1.charAt(i)=='1')&&(n2.charAt(j)=='1'))
{
n3.setCharAt(l--,'1');
c='1';
}
else if((n1.charAt(i)=='0')&&(n2.charAt(j)=='0'))
{
n3.setCharAt(l--,'1');
c='0';
}
else
{
n3.setCharAt(l--,'0');
c='1';
}
}
}
for(;i>=0;i--)
if((n1.charAt(i)=='1')&&(c=='1'))
{
n3.setCharAt(l--,'0');
c='1';
}
else if((n1.charAt(i)=='0')&&(c=='0'))
{
n3.setCharAt(l--,'0');
c='0';
}
else
{
n3.setCharAt(l--,'1');
c='0';
}
for(;j>=0;j--)
if((c=='1')&&(n2.charAt(j)=='1'))
{
n3.setCharAt(l--,'0');
c='1';
}
else if((c=='0')&&(n2.charAt(j)=='0'))
{
n3.setCharAt(l--,'0');
c='0';
}
else
{
n3.setCharAt(l--,'1');
c='0';
}
if(c=='1')
{
n2='1'+n3.toString();
System.out.println(n2);
}
else
System.out.println(n3);
}
catch(IOException e)
{
System.out.println(e);
}
}
}
My solution:
- anonymous February 12, 2013public static String addBinaryNumbers(String num1, String num2) { int p1 = num1.length() - 1; int p2 = num2.length() - 1; StringBuilder buf = new StringBuilder(); int carry = 0; while (p1 >= 0 || p2 >= 0) { int sum = carry; if (p1 >= 0) { sum += num1.charAt(p1) - '0'; p1--; } if (p2 >= 0) { sum += num2.charAt(p2) - '0'; p2--; } carry = sum >> 1; sum = sum & 1; buf.append(sum == 0 ? '0' : '1'); } if (carry > 0) { buf.append('1'); } buf.reverse(); return buf.toString(); }