Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
#include <string>
#include <iostream>
#include <algorithm>
#include <sstream>
#undef min // windows
#undef max // windows
const int INT_RLEN = 2;
class DecString {
public:
DecString(const std::string& s, int e = 0) :mant_(s), exp_(e) {
}
std::ostream& print(std::ostream& strm) const {
for (int i = 0; i < mant_.size(); ++i) {
if (i != 0 && (mant_.size() - i) % 3 == 0)
strm << ",";
strm << mant_[i];
}
return strm << "+e" << exp_;
}
DecString leftHalf() const {
return DecString(mant_.substr(0, mant_.size() / 2 ), exp_ + (mant_.size()+1) / 2 );
}
DecString rightHalf() const {
return DecString(mant_.substr(mant_.size() / 2), exp_);
}
// summation
friend DecString operator +(const DecString& l, const DecString& r) {
int minExp = std::min(l.exp_, r.exp_);
int l_start = l.exp_ == minExp ? 0 : l.exp_ - r.exp_;
int l_stop = l_start + l.mant_.size();
int r_start = r.exp_ == minExp ? 0 : r.exp_ - l.exp_;
int r_stop = r_start + r.mant_.size();
int maxlen = std::max(l_stop, r_stop);
int l_len = l.mant_.size();
int r_len = r.mant_.size();
std::stringstream mant;
int carry = 0;
for (int i = 0; i < maxlen; i++) {
int l_idx = i - l_start;
int r_idx = i - r_start;
int dig = carry;
if (l_idx >= 0 && l_idx < l_len)
dig += l.mant_[l_len - l_idx -1] - 48;
if (r_idx >= 0 && r_idx < r_len)
dig += r.mant_[r_len - r_idx -1] - 48;
carry = dig / 10;
mant << dig % 10;
}
if (carry > 0)
mant << carry;
std::string m(mant.str());
std::reverse(m.begin(), m.end());
return DecString(m, minExp);
}
// multiplication: simple half split O(l.size * r.size)
friend DecString operator *(const DecString& l, const DecString& r) {
if (l.mant_.size() <= INT_RLEN && r.mant_.size() <= INT_RLEN){
// when strings short enough use int arithmetic
int il, ir;
std::istringstream (l.mant_) >> il;
std::istringstream(r.mant_) >> ir;
return DecString( ((std::stringstream&)(std::stringstream() << il* ir)).str(), l.exp_ + r.exp_);
}
if (l.mant_.size() > INT_RLEN && r.mant_.size() > INT_RLEN) {
// split both in ~half
// (l0 + l1) * (r0 + r1) = (l0 * r0) + (l0 * r1) + (l1 * r0) + (l1 * r1)
DecString l0(l.leftHalf()), l1(l.rightHalf()), r0(r.leftHalf()), r1(r.rightHalf());
return (l0 * r0) + (l0 * r1) + (l1 * r0) + (l1 * r1);
}
// no split on short
const DecString& longMant = l.mant_.size() > r.mant_.size() ? l : r;
const DecString& shortMant = &longMant == &l ? r : l;
// (lg0 + lg1) * shrt
return (longMant.leftHalf() * shortMant) + (longMant.rightHalf() * shortMant);
}
private:
const std::string mant_;
const int exp_;
};
std::ostream& operator << (std::ostream& s, const DecString& ds) {
return ds.print(s);
}
void StrMathAdd() {
std::cout << DecString("9999", 2) + DecString("9999", 1) << "\n";
std::cout << DecString("9", 0) * DecString("9999", 0);
}
Create an arraylist of integers and multiply one string by each digit of the second string, starting with rightmost digit. Store the result in the arraylist and add the carry to the next step. Build string by reversing the arraylist.
Ex: string1 = "12345"
string2 = "423"
* = old number
^ = new number
` = carry
First Pass (multiply each digit in string1 by 3, store starting at index 0) :
[5, 3, 0, 7, 3]
Second Pass (multiply each digit in string1 by 2, store starting at index 1):
[5*, 3 (3* + 10^), 9 (0* + 8^ + 1`), 3 (7* + 6^), 8 (3* + 4^ + 1`), 2^]
easier to read: [5, 3, 9, 3, 8, 2]
Third Pass (multiply each digit in string1 by 4, store starting at index 2):
[5*, 3*, 9 (9* + 20^), 1^ (3* + 16^ + 2`), 2 (8* + 12^ + 2`), 2 (2* + 8^ + 2`), 5 (4^ + 1`)]
or [5, 3, 9, 1, 2, 2, 5]
Reverse to get the correct product: 5,221,935.
public String getProduct (String string1, String string2){
ArrayList<Integer> prodBuilder = new ArrayList<Integer>();
String prodString = "";
int partial, carry = 0, remainder, index = 0, startIndex = 0;
for (int i = string2.length() - 1; i >= 0; i--){
index = startIndex;
for (int j = string1.length() - 1; j >= 0; j--){
partial = Character.getNumericValue(string2.charAt(i))
* Character.getNumericValue(string1.charAt(j));
partial += carry;
if (i == string2.length() - 1){
if (index < prodBuilder.size() && prodBuilder.get(index) > 0){
partial = prodBuilder.get(index) + partial;
}
if (partial > 9){
carry = partial / 10;
remainder = partial % 10;
prodBuilder.add(remainder);
} else {
carry = 0;
prodBuilder.add(partial);
}
} else {
if (index < prodBuilder.size() && prodBuilder.get(index) > 0){
partial = prodBuilder.get(index) + partial;
}
if (index == prodBuilder.size()){
if (partial > 9){
carry = partial / 10;
remainder = partial % 10;
prodBuilder.add(remainder);
} else {
prodBuilder.add(partial);
carry = 0;
}
} else {
if (partial > 9){
carry = partial / 10;
remainder = partial % 10;
prodBuilder.set(index, remainder);
} else {
prodBuilder.set(index, partial);
carry = 0;
}
}
}
index++;
}
startIndex++;
if (carry != 0){
prodBuilder.add(carry);
carry = 0;
}
}
for (int k = prodBuilder.size() - 1; k >=0; k--){
prodString = prodString + Integer.toString(prodBuilder.get(k));
}
System.out.println("Result: " + prodString);
return prodString;
}
Mimic the multiplication process as you would do by hand:
Multiple each digit from the second string with the first string and sum up the results (taking into consideration the "carried")
#include "CommonHeader.h"
// Convert ASCII char to number (0 ASCII is 48)
static int char_to_num(char ch) { return ch - 48; }
std::string MultipleHelper(const std::string& num, int multipleBy, size_t depth)
{
int carried = 0;
std::string resString = std::string(depth, '0');
for(size_t i = num.length() - 1; i != std::string::npos; --i) {
int res = (char_to_num(num[i]) * multipleBy) + carried;
int n = res % 10;
carried = res / 10;
resString.insert(0, std::to_string(n));
}
if(carried != 0) {
resString.insert(0, std::to_string(carried));
}
return resString;
}
void MultipleStrings(const std::string& num1, const std::string& num2)
{
if(num1.empty()) return;
if(num2.empty()) return;
int depth = 0;
std::vector<std::string> arr;
size_t maxStrLen = 0;
for(size_t i = (num2.length() - 1); i != std::string::npos; --i) {
arr.push_back(MultipleHelper(num1, char_to_num(num2[i]), depth));
maxStrLen = arr.back().length();
depth++;
}
// Pad the strings so they will have the same length
std::string outputString;
int carried = 0;
for(size_t i = (maxStrLen - 1); i != std::string::npos; --i) {
int curSum = 0;
for(size_t j = 0; j < arr.size(); ++j) {
std::string& curstr = arr[j];
if(curstr.length() != maxStrLen) {
curstr.insert(0, std::string(maxStrLen - curstr.length(), '0'));
}
curSum += char_to_num(curstr[i]);
}
int n = curSum % 10 + carried;
carried = curSum / 10;
outputString.insert(0, std::to_string(n));
}
if(carried != 0) {
outputString.insert(0, std::to_string(carried));
}
std::cout << num1 << " * " << num2 << " = " << outputString << std::endl;
}
int main(int argc, char** argv)
{
MultipleStrings("4385", "345"); // an example
return 0;
}
I would break the multiplication into a set of separate sums, In that case you only need to store the result as an int. You might have to use a big decimal library depending on the language, the solution I am proposing is in python and the language takes care of that detail. Given x the length of the first number and y the length of the second number there are x * y sums.
Code in python
- Fernando August 16, 2017