Facebook Interview Question Member Technical Staffs
Team: Infrastructure
Country: United States
Interview Type: In-Person
Your solution is nice but there is a missing linkage between
cur_result
and
result
shouldn't you be updating
result
at the end of the second While loop by adding all values in cur_result to the accumulative result ???
amazing solution! How long did it take you to come up with this solution? Because what I would have done would be
Add B to itself A number of times..
I wonder how will I solve such a question when faced during an interview.. Thanks for the person who shared it! and the solution :)
Well, I think there might be a simpler solution. As an example, let's say you need to find 456*321
For first number 456, using trick of adding two linked list numbers on the fly without reversing it (you can find that online. Trick is to remember consecutive nodes with sum =9 and propagate carry 1 if it ended in a node whose sum was >=10 because at most you have 1 carry),
Find out all possible multiplication that is for 456*0, 456*1, 456*2, 456*3, ... 456*9 ( here 456*4 is simply adding 456 to itself 3 times). Cost is 9*N = O(N) where N is length of number.
- Once you have this, the problem simply becomes iterating over second number and keep on adding (after multiplying by maintained sum by 10)
Algorithm:
1) First, find 456*1, 456*2, ... , 456*9 in O(N) and store it in int64 [] of 9 elements.
e.g. Multplication[0] = 0, Multiplication[1] = 456, Multiplication[2] = 456*2 ...
2) Maintain int64 sum as answer, scan second number left to right, for the current digit in the second link list, find its multiplication value from first array, multiply sum by 10 and add it. This will give you a rolling multiplication
e.g. while scanning second number 321, left to right
sum = 0
for 3, sum = sum*10 + Multiplication[3] = 456*3 = 1368
for 2, sum = sum*10 + Multiplication[2] = 13680 + 912 = 14592
for 1, sum = sum*10 + Multiplication[1] = 145920+1368 = 146376
Step 1) cost is O(N) where N is length of first number step 2) cost is O(M) where M is length of second number. So total cost is O(N+M)
Correction: Off by one error. int64[] of 10 element because it is 0 to 9
>>1) First, find 456*1, 456*2, ... , 456*9 in O(N) and store it in int64 [] of 9 elements.
>>e.g. Multplication[0] = 0, Multiplication[1] = 456, Multiplication[2] = 456*2 ...
Copy paste error: Multiplication[1] is 456 and not 1368
>>for 1, sum = sum*10 + Multiplication[1] = 145920+456 = 146376
use recursion
let the two numbers be a , b:
include 3 cases
1 length of a > length of b
2 length of a < length of b
3 length of a = length of b
What I was thinking is: convert the linked lists to a stack. Here, it becomes a reversed linked list, and we can pop the top item of each list, multiply the two, write the result to a new node (or reuse) and free up the two input nodes. Remember to carry over using a temp variable. This should consume the least space, but more cpu to convert to stack. What do you guys think?
Use an array of length (L1 + L2) to store the result, where L1 is the length of num1, while L2 is the length of num2.
// implemented in C++
// implementation of singly linked list node
class ListNode
{
public:
int val;
ListNode* next;
ListNode() {}
ListNode(int v) : val(v), next(NULL) {}
~ListNode() {}
};
// global array used to store result and its length
int* buffer = NULL;
int lenBuffer = 0;
ListNode* multiply(ListNode* num1, ListNode* num2)
{
if (num1 == NULL || num2 == NULL) return NULL;
int length1 = lengthOfNumber(num1);
int length2 = lengthOfNumber(num2);
if (length1 > length2) return multiply(num2, num1);
// initialize buffer
lenBuffer = length1 + length2;
buffer = new int[lenBuffer];
memset(buffer, 0, sizeof(int) * lenBuffer);
// multiply
int offset = 0;
ListNode* node = num1;
while (node)
{
multiplyHelper(node->val, num2, offset);
node = node->next;
offset++;
}
// transfer buffer to a linked list
ListNode* head = NULL;
int pos = 0;
while (pos < lenBuffer && buffer[pos] == 0) pos++;
if (pos < lenBuffer)
{
head = new ListNode(buffer[pos++]);
node = head;
while (pos < lenBuffer)
{
node->next = new ListNode(buffer[pos++]);
node = node->next;
}
}
delete buffer;
lenBuffer = 0;
buffer = NULL;
return head;
}
// multiply a single digit with a number
// called by multiply()
void multiplyHelper(int value, ListNode* head, int offset)
{
assert(value >= 0 && value <= 9 && head != NULL);
if (value == 0) return;
ListNode* node = head;
int pos = 0;
while (node)
{
int temp = value * node->val;
int ones = temp % 10;
if (ones != 0) addToBuffer(ones, offset + pos + 1);
int tens = temp / 10;
if (tens != 0) addToBuffer(tens, offset + pos);
node = node->next;
pos++;
}
}
// add a single digit to the buffer at place of index
// called by multiplyHelper()
void addToBuffer(int value, int index)
{
assert(value >= 0 && value <= 9);
while (value > 0 && index >= 0)
{
int temp = buffer[index] + value;
buffer[index] = temp % 10;
value = temp / 10;
index--;
}
}
int lengthOfNumber(ListNode* num)
{
assert(num != NULL);
ListNode* node = num;
int len = 0;
while (node)
{
len++;
node = node->next;
}
return len;
}
A relatively simple solution. The space complexity would be O(L1 + L2). The time complexity would be between O(n^2) and O(n^3). I'm not quite sure about that since I couldn't decide the time complexity of addToBuffer().
n^2 in time and n in space
// Increases the value at a position and move the tens to previous bit if
// necessary.
void increase(list<int>::iterator it, int value) {
*it += value;
while (*it > 9) {
// Adds up the previous bit if current one is bigger than 9.
value = *it / 10;
*it %= 10;
// TODO: this may be out of range if not handled by outer method correctly.
--it;
*it += value;
}
}
forward_list<int>* multiply(
const forward_list<int> &fl_a, const forward_list<int> &fl_b) {
if (fl_a.empty() || fl_b.empty()) {
// Checks that both of the input are not empty.
return NULL;
}
// Uses a doubly linked list to store the multiplied result.
list<int> result;
// There may be one extra MSB at the beginning, add it to avoid out of index.
result.push_back(0);
auto main_it = result.begin();
bool first_iteration = true;
for (auto &b : fl_b) {
result.push_back(0);
++main_it;
auto current_it = main_it;
for (auto &a : fl_a) {
increase(current_it, a * b);
if (first_iteration) result.push_back(0);
++current_it;
}
if (first_iteration) {
first_iteration = false;
result.pop_back();
}
}
// Removes the leading 0s.
forward_list<int>* return_result = new forward_list<int>;
auto it = result.begin();
//while (*it == 0 && it != result.end()) ++it;
if (it == result.end()) {
// the result is zero.
return_result->assign(1, 0);
} else {
return_result->insert_after(
return_result->before_begin(), it, result.end());
}
return return_result;
You could use Karatsuba's method to improve the usual O(n*m) to O(n^1.585) where n > m. However, you should also make sure that n ^ 1.585 >> n * m, because otherwise, the overhead of computing Karatsuba's method may not pay-off compared to doing it the traditional way (long multiplication).
When using Karatsuba's method, a few things I believe are worth considering:
- You need to traverse both lists once at the beginning to calculate their lengths.
- For big enough numbers, are the lengths small enough to fit in an unsigned long number each? This goes outside the scope of the question, since by being able to store the whole number as a linked list in one machine that means its length should also fit in a long (or even int) number type.
- The method doesn't generalize well (I think) for numbers of different lengths, so you need to pad with imaginary zeroes the number with smallest length in the implementation.
- Instead of handling base case of 1*1 digit-length numbers, use a reasonable size in which is better to use the traditional approach (long multiplication) and use it instead of dividing and conquering.
- Along with additions, Karatsuba's method require support for subtractions so when you're building a function that sums two lists, you may consider making it general enough to handle subtraction as well.
- Previous point makes more evident the fact that you will support for negative numbers, so, how should you represent a negative number in a linked list? Probably by making the internal number in each node signed so that it generalizes better.
- For big enough numbers, if instead of a singly linked list you use a circular doubly linked list, I think you could generalize the Karatsuba's method in a similar way as External Sorting and control the way you load nodes from disk into RAM. I mentioned a circular doubly linked list since you need to perform the addition (analogous to merge in External Sorting) backwards so that you can handle carryovers linearly without stack.
- For big enough numbers, you could potentially generalize the Karatsuba's method to use Map-Reduce technology, since divide and conquer naturally accommodates for it.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Node
{
public int val;
public Node next;
public Node(int val)
{
this.val = val;
}
}
class MultipleTwoLists
{
static int digitsPerNode = 2;
static Node result = null;
static Node resultp = result;
static Node resultp2 = result;
public static void mainFunc()
{
Node n1 = new Node(23);
Node n2 = new Node(65);
Node n3 = new Node(12);
n1.next = n2;
n2.next = n3;
Node n4 = new Node(34);
Node n5 = new Node(55);
n4.next = n5;
Multiply(n1, n4);
PrintResult(result);
}
static void Multiply(Node n1, Node n2)
{
if (n2.next != null)
{
Multiply(n1, n2.next);
}
Multiply2(n1, n2);
resultp2 = resultp = resultp.next;
}
static void Multiply2(Node n1, Node n2)
{
if (n1.next != null)
{
Multiply2(n1.next, n2);
}
if (resultp2 == null)
{
resultp2 = new Node(0);
result = resultp = resultp2;
}
int m = n1.val * n2.val + resultp2.val;
int carryon = (int)(m / Math.Pow(10, digitsPerNode));
resultp2.val = m % (int)Math.Pow(10, digitsPerNode);
if (carryon > 0)
{
if (resultp2.next == null)
{
resultp2.next = new Node(carryon);
}
else
{
resultp2.next.val += carryon;
}
}
resultp2 = resultp2.next;
}
static void PrintResult(Node p)
{
if (p == null)
return;
if (p.next != null)
{
PrintResult(p.next);
}
Console.Write(p.val);
}
}
}
a complex solution
#include <list>
#include <iostream>
#include <stdlib.h>
typedef std::list<int> NumberList;
struct CalcResult
{
CalcResult() : length(0) {;}
CalcResult(const CalcResult& other)
{
if (this == &other) return;
length = other.length;
numbers = other.numbers;
}
void push_back(int x)
{
numbers.push_back(x);
length++;
}
void push_front(int x)
{
numbers.push_front(x);
length++;
}
int pop_front()
{
int x = numbers.front();
numbers.pop_front();
--length;
return x;
}
NumberList numbers;
int length;
};
CalcResult add(CalcResult& a, CalcResult& b)
{
CalcResult result;
if (a.length >= b.length)
{
int diff = a.length - b.length;
for (int i = 0; i < diff; ++i)
{
result.push_back(a.pop_front());
}
CalcResult carry;
for (int i = 0; i < b.length; ++i)
{
int x = a.numbers.front();
int y = b.numbers.front();
int s = x + y;
a.numbers.pop_front();
b.numbers.pop_front();
if (s >= 10)
{
carry.push_back(1);
result.push_back(s % 10);
}
else
{
result.push_back(s);
if (carry.length > 0)
{
carry.push_back(0);
}
}
}
if (carry.length > 0)
{
carry.push_back(0);
return add(result, carry);
}
else
return result;
}
else
{
return add(b, a);
}
}
CalcResult multiply(int x, CalcResult numbers)
{
int y = numbers.numbers.front();
int d = x * y;
CalcResult result;
while (d > 0)
{
int n = d % 10;
result.push_front(n);
d /= 10;
}
int l = numbers.length;
for (int i = 0; i < l - 1; ++i)
{
result.push_back(0);
}
numbers.numbers.pop_front();
numbers.length--;
if (numbers.length >= 1)
{
CalcResult r = multiply(x, numbers);
return add(result, r);
}
else
return result;
}
CalcResult multi(CalcResult x, CalcResult y)
{
CalcResult r1;
if (x.length == 1)
return multiply(x.pop_front(), y);
if (y.length == 1)
return multiply(y.pop_front(), x);
int a = x.pop_front();
int b = y.pop_front();
int s = a * b;
while (s > 0)
{
r1.push_back(s % 10);
s /= 10;
}
int l = x.length + y.length;
for (int i = 0; i < l; ++i)
{
r1.push_back(0);
}
CalcResult r2 = multiply(a, y);
for (int i = 0; i < x.length; ++i)
{
r2.push_back(0);
}
CalcResult r3 = multiply(b, x);
for (int i = 0; i < y.length; ++i)
{
r3.push_back(0);
}
CalcResult r4 = multi(x, y);
CalcResult s1 = add(r1, r2);
CalcResult s2 = add(r3, r4);
return add(s1, s2);
}
void print(const CalcResult& r)
{
NumberList::const_iterator it = r.numbers.begin();
for (; it != r.numbers.end(); ++it)
{
std::cout << (*it);
}
}
CalcResult make(int x)
{
CalcResult r;
while (x > 0)
{
int d = x % 10;
r.push_front(d);
x /= 10;
}
return r;
}
int main(int argc, char* argv[])
{
int x = atoi(argv[1]);
int y = atoi(argv[2]);
CalcResult X = make(x);
CalcResult Y = make(y);
CalcResult r = multi(X, Y);
print(r);
return 0;
}
put it simple:
v[i + j] += a[i] * b[j], for each digit in a and b;
#include <list>
#include <iostream>
#include <stdlib.h>
#include <vector>
typedef std::list<int> NumberList;
struct CalcResult
{
CalcResult() : length(0) {;}
CalcResult(const CalcResult& other)
{
if (this == &other) return;
length = other.length;
numbers = other.numbers;
}
void push_back(int x)
{
numbers.push_back(x);
length++;
}
void push_front(int x)
{
numbers.push_front(x);
length++;
}
int pop_front()
{
int x = numbers.front();
numbers.pop_front();
--length;
return x;
}
NumberList numbers;
int length;
};
void print(const CalcResult& r)
{
NumberList::const_iterator it = r.numbers.begin();
for (; it != r.numbers.end(); ++it)
{
std::cout << (*it);
}
}
CalcResult make(int x)
{
CalcResult r;
while (x > 0)
{
int d = x % 10;
r.push_front(d);
x /= 10;
}
return r;
}
CalcResult multi2(const CalcResult& x, const CalcResult& y)
{
const int size = x.length - 1 + y.length;
std::vector<int> v(size + 1);
NumberList xlist = x.numbers;
NumberList ylist = y.numbers;
int i = x.length - 1;
while (xlist.size() > 0)
{
int a = xlist.front();
int j = y.length - 1;
for (NumberList::const_iterator it = ylist.begin(); it != ylist.end(); ++it)
{
int b = *it;
if (v[i + j])
{
v[i + j] += a * b;
}
else
{
v[i + j] = a * b;
}
--j;
}
xlist.pop_front();
--i;
}
int carry = 0;
for (int i = 0; i < size; ++i)
{
if (v[i] + carry >= 10)
{
int sum = v[i] + carry;
v[i] = sum % 10;
carry = sum / 10;
}
}
CalcResult result;
if (carry > 0)
{
result.push_back(carry);
}
for (int i = size - 1; i >= 0; --i)
{
result.push_back(v[i]);
}
return result;
}
int main(int argc, char* argv[])
{
int x = atoi(argv[1]);
int y = atoi(argv[2]);
CalcResult X = make(x);
CalcResult Y = make(y);
CalcResult r = multi2(X, Y);
print(r);
return 0;
}
public static void multiply(List<Integer> listA, List<Integer> listB){
List<Integer> a = null ;
List<Integer> b = null ;
if (listA.size() >= listB.size()){
a = listA ;
b = listB ;
}else{
a = listB ;
b = listA ;
}
int carrier = 0;
for (int i = a.size() - 1 ; i >= 0 ; --i){
for (int j = b.size() - 1 ; j >= 0 ; --j){
carrier = 0 ;
int product = b.get(j) * a.get(i) ;
a.set(i, product % 10 + carrier);
carrier = product / 10 ;
}
}
if (carrier > 0){
a.add(0, carrier) ;
}
for (Integer i : a){
System.out.print(i);
}
System.out.println();
}
I don't think we are allowed to create double links. So stick to single links.
<?php
class Num {
public $next;
public $num;
public function __construct($num = 0) {
$this->num = $num;
}
}
function createLink(array $numbers) {
$cur = $head = new Num();
foreach ($numbers as $number) {
$cur->next = new Num($number);
$cur = $cur->next;
}
return $head;
}
function printLink($cur) {
$cur = $cur->next;
while ($cur) {
print $cur->num . ' ';
$cur = $cur->next;
}
print "\n";
}
function multiply($head1, $head2) {
$flag3 = $head3 = new Num();
$cur1 = $head1->next;
while ($cur1) {
$cur3 = $flag3;
$cur2 = $head2->next;
while ($cur2) {
$cur3->next = $cur3->next === null ? new Num() : $cur3->next;
$cur3->next->num += $cur1->num * $cur2->num;
$cur3 =$cur3->next;
$cur2 = $cur2->next;
}
$flag3 = $flag3->next;
$cur1 = $cur1->next;
}
$found = true;
while ($found) {
$found = false;
$new = new Num();
$new->next = $head3;
$head3 = $new;
$cur = $head3;
$next = $cur->next;
while ($next !== null) {
if ($next->num >= 10) {
$cur->num += (int) ($next->num / 10);
$next->num = $next->num % 10;
$found = true;
}
$cur = $cur->next;
$next = $next->next;
}
}
while ($head3->next->num == 0) {
$head3->next = $head3->next->next;
}
return $head3;
}
$head1 = createLink([1, 2, 3, 4, 5, 6, 7]);
printLink($head1);
$head2 = createLink([2, 3, 4, 5, 6, 7, 8]);
printLink($head2);
$head3 = multiply($head1, $head2);
printLink($head3);
Another solution using recursion & stack. O(n*m) time complexity and O(n+m) space complexity
#include <iostream>
#include <functional>
#include <stack>
using namespace std;
struct node {
int v;
node* n;
node(int v, node* n = nullptr) : v(v), n(n) {}
};
auto multiply = [](node* n1, node* n2) {
function<int(node*,int,node*&)> inner_impl = [&](node* n1, int v, node*& o) {
if (!n1) {
return 0;
}
if (o) {
auto res = o->v + n1->v * v + inner_impl(n1->n, v, o->n);
o->v = res % 10;
return res / 10;
}
else {
node* next = nullptr;
auto res = n1->v * v + inner_impl(n1->n, v, next);
o = new node(res % 10, next);
return res / 10;
}
};
stack<int> s;
auto n2cur = n2;
while(n2cur) {
s.push(n2cur->v);
n2cur = n2cur->n;
}
auto out = new node(0, nullptr);
while(!s.empty()) {
out->v = inner_impl(n1, s.top(), out->n);
s.pop();
out = new node(0, out);
}
return out;
};
Use recursion
1. say the numbers are ABC (A->B->C) and XYZ (X->Y->Z)
2. for each digit D_i in ABC, multiply(D_i, X->Y->Z). Keep track of a counter that count the number of nodes in ABC. This can be done in a while loop
3. Use recursion to multiply Di and XYZ. Say the result is M_i
4.calculate M_1+10^1*M_2+...10^(counter-1)*M_counter. This can be done in a for loop since we know what counter is. The sum is the result
Save the result in a doubly linked list:
Node* multiply(Node* a, Node* b) { if (!a || !b) return NULL; DNode* result = new DNode(); Node* cur_a = a; while (cur_a) { Node* cur_b = b; DNode* cur_result = result; while (cur_b) { cur_result->increase(cur_a->value * cur_b->value); cur_b = cur_b->next; if (cur_b) cur_result = cur_result->get_next(); } cur_a = cur_a->next; if (cur_a) result = result->get_next(); } DNode* head = result->get_head(); Node* product = head->create_node(); delete head; return product; }Implementation for DNode:
- Linfuzki March 17, 2014struct Node { int value; Node* next; }; struct DNode { int value; DNode* next; DNode* previous; DNode() : value(0), next(NULL), previous(NULL) {} ~DNode() { delete next; } void increase(int a) { value += a; if (value >= 10) { int d = value /10; value %= 10; get_previous()->increase(d); } } DNode* get_next() { if (next) return next; next = new DNode(); next->previous = this; return next; } DNode* get_previous() { if (previous) return previous; previous = new DNode(); previous->next = this; return previous; } DNode* get_head() { if (!previous) return this; return previous->get_head(); } Node* create_node() { Node* node = new Node(); node->value = value; node->next = next ? next->create_node() : NULL; return node; } };