Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
Interesting what was the point of that question. To check if you know and remember advanced multiplication algorithms or your ability to implement very boring but well known one?
School algorithm. Its really ugly:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Xunit;
namespace MultiplyLargeNumbers
{
public class MultiplyLargeNumbersShould
{
[Theory]
[InlineData("5", "6", "30")]
[InlineData("15", "6", "90")]
[InlineData("6", "15", "90")]
[InlineData("52", "16", "832")]
[InlineData("16", "52", "832")]
[InlineData("52", "10", "520")]
[InlineData("10", "52", "520")]
[InlineData("123456", "76543", "9449692608")]
[InlineData("76543", "123456", "9449692608")]
public void Multiply(string a, string b, string expected)
{
var actual = Multiply(a, b);
Assert.Equal(expected, actual);
}
public string Multiply(string a, string b)
{
var res = new List<int>();
int shift = 0;
var aN = a.Length;
var bN = b.Length;
for (int i = bN-1; i >= 0; i--)
{
var bi = int.Parse(b[i].ToString());
int remember = 0;
int k=0;
for (int j = aN-1; j >=0; j--, k++)
{
var aj = int.Parse(a[j].ToString());
var product = bi * aj + remember;
var digit = product%10;
remember = (product - digit) / 10;
int p = shift+k;
if (p >= 0 && p < res.Count)
{
var sum = res[p]+digit;
var s1 = sum % 10;
if (sum > 9)
remember += 1;
res[p] = s1;
}
else
{
res.Add(digit);
}
}
if (remember > 0)
{
res.Add(remember);
}
shift++;
}
var sb = new StringBuilder();
for (int r=res.Count()-1; r>=0; r--)
{
sb.Append(res[r]);
}
return sb.ToString();
}
}
}
Get the input in the form of Strings.Manipulate each character from both the strings from right to left to number and perform multiplication and return the answer as String.
- Madhumitha Karthikeyan September 12, 2017