## Facebook Interview Question for Member Technical Staffs

Team: Infrastructure
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

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();
}

Node* product = head->create_node();
return product;
}``````

Implementation for DNode:

``````struct 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;
}

if (!previous) return this;
}

Node* create_node() {
Node* node = new Node();
node->value = value;
node->next = next ? next->create_node() : NULL;
return node;
}
};``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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 ???

Comment hidden because of low score. Click to expand.
0

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 :)

Comment hidden because of low score. Click to expand.
0

Where is the link between result & curr_result.

I see you are assigning the result to curr_result. But where is result updated to curr_result?

Comment hidden because of low score. Click to expand.
2
of 4 vote

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, Multiplication = 456, Multiplication = 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 = 456*3 = 1368
for 2, sum = sum*10 + Multiplication = 13680 + 912 = 14592
for 1, sum = sum*10 + Multiplication = 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)

Comment hidden because of low score. Click to expand.
0

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, Multiplication = 456, Multiplication = 456*2 ...

Copy paste error: Multiplication is 456 and not 1368
>>for 1, sum = sum*10 + Multiplication = 145920+456 = 146376

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Nice idea...and accounting for boundary conditions as well. The only issue that may be raised is the level of recursion vs stack space running out if the number/list has many many numbers/nodes.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++]);

while (pos < lenBuffer)
{
node->next = new ListNode(buffer[pos++]);
node = node->next;
}
}

delete buffer;
lenBuffer = 0;
buffer = NULL;

}

// 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().

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another way to do this may be traverse the list and save the numbers in a long long type and multiply them and create a new result linked list.
eg: Multiply 123456789 and 23454343

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
else
return result;
}
else
{
}
}

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);
}
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);
}

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);
int y = atoi(argv);

CalcResult X = make(x);
CalcResult Y = make(y);
CalcResult r = multi(X, Y);
print(r);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
a simple solution: allocate an array of size a.length + b.length - 1 loop a and b, vector[i + j] += a[i] * b[j] process carry {{{ #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); int y = atoi(argv); CalcResult X = make(x); CalcResult Y = make(y); CalcResult r = multi2(X, Y); print(r); return 0; }
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
int y = atoi(argv);

CalcResult X = make(x);
CalcResult Y = make(y);
CalcResult r = multi2(X, Y);
print(r);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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){
}
for (Integer i : a){
System.out.print(i);
}
System.out.println();``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
\$cur = \$cur->next;
while (\$cur) {
print \$cur->num . ' ';
\$cur = \$cur->next;
}
print "\n";
}
\$flag3 = \$head3 = new Num();
while (\$cur1) {
\$cur3 = \$flag3;
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();
\$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) {
}
}
\$head1 = createLink([1, 2, 3, 4, 5, 6, 7]);
\$head2 = createLink([2, 3, 4, 5, 6, 7, 8]);

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.