Facebook Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
class Solution {
public:
string sumStrings(string a, string b) {
int i = a.size()-1;
int j = b.size()-1;
int carry = 0;
string res = "";
while(i>=0 || j>=0 || carry==1) {
carry += i>=0 ? a[i--] : 0;
carry += j>=0 ? b[j--] : 0;
res = char(carry%10 + '0') + res;
carry = carry/10;
}
return res;
}
}
The "too large for BigInteger" condition is there presumably to exclude the approach of converting the strings to BigIntegers and adding the BigIntegers. However, the BigInteger representation is in fact more compact, so if a number is too large for a BigInteger, it's definitely too large for a string.
#include <stdio.h>
#include<string.h>
#include<math.h>
#define MAX 10000
int main(void) {
int i = 0, k, len1, len2, sum, tmp, l1, l2, leng, a[MAX], b[MAX];
char string1[MAX], string2[MAX], ans[MAX];
printf("enter a number : ");
scanf("%s",&string1);
printf("enter another number : ");
scanf("%s",&string2);
//printf("\nThe 1st number is : ");
while(string1[i]){
a[i] = (int)string1[i]-48;
//printf("%d",a[i]);
i++;
}
i = 0;
//printf("\nThe 2nd number is : ");
while(string2[i]){
b[i] = (int)string2[i]-48;
//printf("%d",b[i]);
i++;
}
len1 = strlen(string1), len2 = strlen(string2);
printf("\nlengths are respectively : %d and %d", len1, len2);
if(len1 >= len2)
leng = len1;
else
leng = len2;
for(i = 0, l1 = len1-1, l2 = len2-1; i < leng; i++, l1--, l2--){
ans[i] = a[l1] + b[l2];
}
for(k = 0; k <= leng; k++){
sum = ans[k];
tmp = sum/10;
ans[k] = sum%10;
ans[k+1] += tmp;
}
for(i = leng; i>= 0;i--)
{
if(ans[i] > 0)
break;
}
printf("\nThe summation is : ");
for(k = i; k >= 0; k--){
printf("%d",ans[k]);
}
return 0;
}
class Solution {
public:
string sumStrings(string a, string b) {
int i = a.size()-1;
int j = b.size()-1;
int carry = 0;
string res = "";
while(i>=0 || j>=0 || carry==1) {
carry += i>=0 ? a[i--] : 0;
carry += j>=0 ? b[j--] : 0;
res = char(carry%10 + '0') + res;
carry = carry/10;
}
return res;
}
}
My answer in Java would be like this
private static String addNumbers(String no1, String no2)
{
String sum = "";
int bal = 0;
int max = no1.length() > no2.length() ? no1.length() : no2.length();
for (int count = 1; count <= max || bal > 0; count++) {
if (count <= max){
if (no1.length() - count >= 0)
bal += (no1.charAt(no1.length() - count) - '0');
if (no2.length() - count >= 0)
bal += (no2.charAt(no2.length() - count) - '0');
}
sum = "" + (bal % 10) + sum;
bal /= 10;
}
return sum;
}
private static void GetSumOfLargeNumbers(string value1, string value2)
{
List<char> summation = new List<char>();
value1 = value1.PadLeft(15, '0');
value2 = value2.PadLeft(15, '0');
int carryOver = 0;
for (int i = value1.Length - 1; i > 0; i--)
{
int value = carryOver + Convert.ToInt32(value1[i].ToString()) + Convert.ToInt32(value2[i].ToString());
if (value > 9)
{
carryOver = Convert.ToInt32(value.ToString()[0]);
summation.Add(value.ToString()[1]);
}
else
summation.Add(value.ToString()[0]);
}
summation.Reverse();
Console.WriteLine(string.Join("", summation));
}
private static void GetSumOfLargeNumbers(string value1, string value2)
{
List<char> summation = new List<char>();
value1 = value1.PadLeft(15, '0');
value2 = value2.PadLeft(15, '0');
int carryOver = 0;
for (int i = value1.Length - 1; i > 0; i--)
{
int value = carryOver + Convert.ToInt32(value1[i].ToString()) + Convert.ToInt32(value2[i].ToString());
if (value > 9)
{
carryOver = Convert.ToInt32(value.ToString()[0]);
summation.Add(value.ToString()[1]);
}
else
summation.Add(value.ToString()[0]);
}
summation.Reverse();
Console.WriteLine(string.Join("", summation));
}
Ruby
-> (a, b) {
zero = '0'.ord
[a, b].
sort_by(&:length).
reverse.
map(&:bytes).
map(&:reverse).
reduce(&:zip).
reduce(result: [], overflow: 0) { |prev, (adig, bdig)|
ov, digs = ((adig || zero) + (bdig || zero) - 2 * zero + prev[:overflow]).divmod 10
{overflow: ov, result: prev[:result] << digs}
}.
tap { |prev| prev[:result] << 1 if prev[:overflow] == 1 }[:result].
reverse.join
}
golang:
package main
import (
"fmt"
"math"
)
func main() {
fmt.Println(sum("1989", "39900"))
fmt.Println(1989+39900)
}
func sum(a, b string) int64 {
aSize := len(a)
bSize := len(b)
maxLen := math.Max(float64(aSize), float64(bSize))
result := 0
tmp := 0
x := 1
for i := 0; i < int(maxLen); i++ {
digitA := 0
digitB := 0
if aSize - i >= 1 {
digitA = int(a[aSize - i - 1]-'0')
}
if bSize - i >= 1 {
digitB = int(b[bSize - i - 1]-'0')
}
if digitA > 9 || digitA < 0 || digitB > 9 || digitB < 0 {
return -1
}
sum := digitA + digitB + tmp
tmp = sum/10
sum %= 10
result += sum * x
x *= 10
}
if tmp == 0 {
return int64(result)
}
return int64(result+x)
}
golang:
package main
import (
"fmt"
"math"
)
func main() {
fmt.Println(sum("1989", "39900"))
fmt.Println(1989+39900)
}
func sum(a, b string) int64 {
aSize := len(a)
bSize := len(b)
maxLen := math.Max(float64(aSize), float64(bSize))
result := 0
tmp := 0
x := 1
for i := 0; i < int(maxLen); i++ {
digitA := 0
digitB := 0
if aSize - i >= 1 {
digitA = int(a[aSize - i - 1]-'0')
}
if bSize - i >= 1 {
digitB = int(b[bSize - i - 1]-'0')
}
if digitA > 9 || digitA < 0 || digitB > 9 || digitB < 0 {
return -1
}
sum := digitA + digitB + tmp
tmp = sum/10
sum %= 10
result += sum * x
x *= 10
}
if tmp == 0 {
return int64(result)
}
return int64(result+x)
}
package main
import (
"fmt"
"math"
)
func main() {
fmt.Println(sum("1989", "39900"))
fmt.Println(1989+39900)
}
func sum(a, b string) int64 {
aSize := len(a)
bSize := len(b)
maxLen := math.Max(float64(aSize), float64(bSize))
result := 0
tmp := 0
x := 1
for i := 0; i < int(maxLen); i++ {
digitA := 0
digitB := 0
if aSize - i >= 1 {
digitA = int(a[aSize - i - 1]-'0')
}
if bSize - i >= 1 {
digitB = int(b[bSize - i - 1]-'0')
}
if digitA > 9 || digitA < 0 || digitB > 9 || digitB < 0 {
return -1
}
sum := digitA + digitB + tmp
tmp = sum/10
sum %= 10
result += sum * x
x *= 10
}
if tmp == 0 {
return int64(result)
}
return int64(result+x)
}
public static String sum(String num1, String num2) {
String result = "";
int carry = 0;
for (int i = 0; i < Math.max(num1.length(), num2.length()); i++) {
if (i < num1.length() && i < num2.length()) {
int sum = carry + sumSingleChar(num1.charAt(num1.length() - i - 1), num2.charAt(num2.length() - i - 1));
if (sum > 10) carry = 1;
else carry = 0;
result = sum % 10 + result;
} else {
if (num1.length() > i) {
int sum = carry + Character.getNumericValue(num1.charAt(num1.length() - i - 1));
if (sum > 10) carry = 1;
result = sum % 10 + result;
} else {
int sum = carry + Character.getNumericValue(num2.charAt(num2.length() - i - 1));
if (sum > 10) carry = 1;
result = sum % 10 + result;
}
}
}
return result;
}
package main
import "fmt"
import "os"
import "strconv"
func main() {
var shortestStringLen int
var outputString string
var longerString string
str1 := os.Args[1]
str2 := os.Args[2]
fmt.Println("Str1: ", str1)
fmt.Println("Str2: ", str2)
str1len := len(str1)
str2len := len(str2)
if str2len < str1len {
shortestStringLen = str2len
longerString = str1
} else {
shortestStringLen = str1len
longerString = str2
}
var carryTheOne bool
var outDigit int
carryTheOne = false
for i:=1; i<=shortestStringLen; i++ {
str1digit,_ := strconv.Atoi(string(str1[str1len - i]))
str2digit,_ := strconv.Atoi(string(str2[str2len - i]))
strSum := str1digit+str2digit
if carryTheOne {
strSum += 1
}
outDigit = strSum%10
carryTheOne = strSum>=10
outputString = strconv.Itoa(outDigit) + outputString
}
for a:=shortestStringLen; a<len(longerString); a++ {
extDigit, _ := strconv.Atoi(string(longerString[(len(longerString)-1) - a]))
if carryTheOne {
extDigit += 1
}
outDigit = extDigit%10
carryTheOne = extDigit>10
outputString = strconv.Itoa(outDigit) + outputString
}
if carryTheOne {
outputString = strconv.Itoa(1) + outputString
}
fmt.Println("Sum of Str1 and Str2: ", outputString)
}
String sumTwoStrings(String s1, String s2) {
String sum = "";
int len1 = s1.length() - 1;
int len2 = s2.length() - 1;
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int carry = 0;
for(int i=len1, j=len2; i>=0 || j>=0 ; i--, j--) {
int digit1 = i<0 ? 0 : str1[i]-'0';
int digit2 = j<0 ? 0 : str2[j]-'0';
int sumDig = digit1 + digit2 + carry;
sum = sumDig%10 + sum;
carry = sumDig/10;
}
if(carry > 0) {
sum = carry + sum;
}
return sum;
}
# python
def SumOfStringNums(s1,s2):
output = ""
lens1 = len(s1)
lens2 = len(s2)
if lens1 > lens2:
addition = lens1 - lens2
s2 = addition*"0" + s2
else:
addition = lens2 - lens1
s1 = addition*"0" + s1
s1 = s1[::-1]
s2 = s2[::-1]
t = 0
c = 0
i = 0
for i in range(len(s1)):
t = int(s1[i]) + int(s2[i]) + c
if t < 10:
output += str(t)
c = 0
else:
t = t - 10
output += str(t)
c = 1
if c == 1:
output += "1"
output = output[::-1]
print output
#test
ss1 = "139"
ss2 = "113"
SumOfStringNums(ss1,ss2)
public class Solution {
static public void main(String[] args) {
String a = "29023902397403472034", b = "8372283473748173";
String out = AddVeryLargeNumbers(a, b);
System.out.println(out);
}
static String AddVeryLargeNumbers(String a, String b) {
StringBuilder out = new StringBuilder();
int max_len = a.length() >= b.length()? a.length() : b.length();
int i = a.length() - 1, j = b.length()-1;
int carry = 0;
while (max_len > 0) {
int tmp = 0;
if (i >= 0)
tmp += (int) a.charAt(i) - '0';
if (j >= 0)
tmp += (int) b.charAt(j) - '0';
if (carry == 1) {
tmp += carry;
}
// handling carry
if (tmp >= 10) {
carry = 1;
out.insert(0, tmp-10);
} else {
carry = 0;
out.insert(0, tmp);
}
i--;
j--;
max_len--;
}
if (carry == 1)
out.insert(0, String.valueOf(1));
return out.toString();
}
}
class Solution{
public static void main(String[] args){
String a,b, c;
a = "123456876";
b = "3598002";
//c= 127054878
int i,j;
i = a.length()-1;
j = b.length()-1;
c ="";
int sum=0;
while(i>=0 || j>=0 || sum>0){
if(i>=0) {
sum +=a.charAt(i)-'0';
i--;
}
if(j>=0) {
sum +=b.charAt(j)-'0';
j--;
}
c = (sum%10) + c;
sum = sum/10;
//System.out.println(""+i+" "+j+" "+sum+" "+c);
}
}
}
public class StringAdd{
public static void main (String args[]){
String x= "2112";
String y= "881";
int xLen= x.length()-1;
int yLen= y.length()-1;
int carryOver=0;
StringBuilder sb = new StringBuilder();
while (xLen>=0|| yLen>=0){
int sum=(xLen>=0?Character.getNumericValue(x.charAt(xLen)):0) +
(yLen>=0?Character.getNumericValue(y.charAt(yLen)):0)+carryOver;
if(sum>=10){
sb.insert(0, sum % 10);
carryOver=sum /10;
}else{
sb.insert(0, sum );
carryOver=0;
}
xLen--;
yLen--;
}
if(carryOver>0) sb.insert(0,carryOver);
System.out.println(sb);
}
}
public static void main(String[] args) {
String num1 = "199234565454544900";
String num2 = "7339999333907533808";
int len1 = num1.length() - 1;
int len2 = num2.length() - 1;
int carry = 0;
String result = "";
for (int i = len1, j = len2; i >= 0 || j >= 0; i--, j--) {
int d1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int d2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = d1 + d2 + carry;
int rd = sum > 9 ? sum % 10 : sum;
carry = sum > 9 ? 1 : 0;
result = String.valueOf(rd).concat(result);
}
}
A small fix in the above code..
- datta.pm July 08, 2018