## Facebook Interview Question for Interns

• 0

Country: United States

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

``````public class LinkedDigitsNumber {

public static void main(String[] args) {
sumUpRecursive(first, second, result, false);
System.out.print("Result: " + result);
}

if (first.isEmpty() && second.isEmpty()) {
return;
}
int sum = (first.isEmpty() ? 0 : first.pollLast()) + (second.isEmpty() ? 0 : second.pollLast()) + (carring ? 1 : 0);
result.addFirst(sum > 9 ? sum - 10 : sum);
sumUpRecursive(first, second, result, sum > 9);
}
}``````

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

Am I missing something here? I think this will add the wrong digit and produce the wrong result. For example, 4931 + 813, this will add 4 and 8. Unless you reverse both the linklists first, no?

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

@Dan LL is being polled from end (see pollLast)

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

PollLast is an O(n) operation at worst.

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

``````import java.io.*;
import java.util.*;

class MyCode {
public static void main (String[] args) {

for(Integer i: sum) {
System.out.print(i);
}
System.out.println("expected: " + (1394+33318));
}

Iterator<Integer> firstIterator = first.descendingIterator();
Iterator<Integer> secondIterator = second.descendingIterator();

int rest = 0;
while(firstIterator.hasNext() || secondIterator.hasNext()) {
Integer a = firstIterator.hasNext() ? firstIterator.next() : 0;
Integer b = secondIterator.hasNext() ? secondIterator.next() : 0;

rest = (a + b + rest) / 10;
}

return ret;
}
}``````

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

``````import java.util.*;
public class HelloWorld{

public static void main(String []args){
int maxlen,minlen;

if (obj1.size() <= obj2.size())
{
maxlen = obj1.size();
minlen = obj2.size();
}
else
{
maxlen = obj2.size();
minlen = obj1.size();
}

int carry = 0;
for(int i=maxlen-1;i>=0;i--)
{
int tmp1 = obj1.get(i);
int tmp2 = obj2.get(i);
int tmp3  = tmp1+tmp2+carry;
carry = 0;

if (tmp3 >= 10)
{
carry = (tmp3/10)%10;
tmp3 = tmp3%10;
}

}

if (obj1.size() > obj2.size())
{
for(int i =maxlen; i< minlen;i++)
{
int tmp1 = obj1.get(i);
int tmp2 = tmp1 +carry;
carry = 0;

if(tmp2 >= 10)
{
carry = (tmp2/10)%10;
tmp2 = tmp2%10;
}
}

if(carry !=0)
}
else if (obj1.size() < obj2.size())
{
for(int i =maxlen; i< minlen;i++)
{
int tmp1 = obj2.get(i);
int tmp2 = tmp1 +carry;
carry = 0;

if(tmp2 >= 10)
{
carry = (tmp2/10)%10;
tmp2 = tmp2%10;
}
}

if(carry !=0)
}
else if((obj1.size() == obj2.size()) && (carry !=0))
{
}

System.out.println("Result: " +res);
}
}``````

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

This could be made better of course but a linear algorithm thats easy I guess.

``````import java.util.*;
public class HelloWorld{

public static void main(String []args){
int maxlen,minlen;

if (obj1.size() <= obj2.size())
{
maxlen = obj1.size();
minlen = obj2.size();
}
else
{
maxlen = obj2.size();
minlen = obj1.size();
}

int carry = 0;
for(int i=maxlen-1;i>=0;i--)
{
int tmp1 = obj1.get(i);
int tmp2 = obj2.get(i);
int tmp3  = tmp1+tmp2+carry;
carry = 0;

if (tmp3 >= 10)
{
carry = (tmp3/10)%10;
tmp3 = tmp3%10;
}

}

if (obj1.size() > obj2.size())
{
for(int i =maxlen; i< minlen;i++)
{
int tmp1 = obj1.get(i);
int tmp2 = tmp1 +carry;
carry = 0;

if(tmp2 >= 10)
{
carry = (tmp2/10)%10;
tmp2 = tmp2%10;
}
}

if(carry !=0)
}
else if (obj1.size() < obj2.size())
{
for(int i =maxlen; i< minlen;i++)
{
int tmp1 = obj2.get(i);
int tmp2 = tmp1 +carry;
carry = 0;

if(tmp2 >= 10)
{
carry = (tmp2/10)%10;
tmp2 = tmp2%10;
}
}

if(carry !=0)
}
else if((obj1.size() == obj2.size()) && (carry !=0))
{
}

System.out.println("Result: " +res);
}
}``````

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

Fetching last node is not constant time operation until list is array list,.... Ur us linked list. So ur solution is o(n^2)

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

``````def addAsList(num1, num2):
#num1 = [1,2,3] as 123
ret = []
n1 = len(num1)
n2 = len(num2)
inc = 0
for i in range(n1):
v1 = num1[n1-i-1]
if n2-i <= 0:
num1[n1-i-1]+=inc
ret =num1[0:n1-i-1]+ret
inc = 0
break

v2 = num2[n2-i-1]

sum = v1+v2+inc
inc = sum/10
sum = sum%10
ret = [sum]+ret

if n2>n1:
num2[n2-n1]+=inc
ret = num2[0:n2-n1]+ ret
inc = 0

if inc > 0:
ret = [inc] + ret

return ret``````

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

``````public static LinkedList<Byte> sumOfLists(LinkedList<Byte> one, LinkedList<Byte> two) {

ListIterator<Byte> iterator1 = one.listIterator(one.size());
ListIterator<Byte> iterator2 = two.listIterator(one.size());
int rest = 0;
while (iterator2.hasPrevious() && iterator2.hasPrevious()) {
Byte number1 = iterator1.previous();
Byte number2 = iterator2.previous();
int sum = number1 + number2 + rest;
rest = sum / 10;
}

ListIterator<Byte> restIterator = null;
if (iterator1.hasPrevious()) {
restIterator = iterator1;
} else if (iterator2.hasPrevious()) {
restIterator = iterator2;
}

if (restIterator != null) {
while (restIterator.hasPrevious()) {
Integer sum = restIterator.previous() + rest;
rest = sum / 10;
}
}

if (rest > 0) {
}

return result;
}``````

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

Same as the problem 2.4 in Cracking the Coding Interview with the twist the most significant digit is "first" (I am assuming this means it is in the head of the list). Here it is my iterative version (instead of the recursive solution in the book):

``````class Node:
def __init__(self, value):
self.value = value
self.next = None

def gen_list(num):
last = Node(num[0])
start = last
for digit in num[1:]:
node = Node(digit)
last.next = node
last = node
return start

def print_list(num):
if num is None:
print('')
return
string = '{}'.format(num.value)
num = num.next
while num is not None:
string += ' -> {}'.format(num.value)
num = num.next
print(string)

def reverse_list(fwd):
last = None
while fwd is not None:
bwd = Node(fwd.value)
if last is not None:
bwd.next = last
last = bwd
fwd = fwd.next
return last

def sum_reverse_list(node1, node2):
c = 0
node = None
prev = None
while node1 is not None or\
node2 is not None:
a = node1.value if node1 is not None else 0
b = node2.value if node2 is not None else 0
x = a + b + c
if x > 9:
node = Node(x%10)
c = 1
else:
node = Node(x)
c = 0
node.next = prev
prev = node
if node1 is not None:
node1 = node1.next
if node2 is not None:
node2 = node2.next
if c == 1:
node = Node(1)
node.next = prev
return node

def sum_list(node1, node2):
node1 = reverse_list(node1)
node2 = reverse_list(node2)
return sum_reverse_list(node1, node2)

num1 = [9, 9, 9]
node1 = gen_list(num1)
print_list(node1)
print('+')
num2 = [1, 2, 3]
node2 = gen_list(num2)
print_list(node2)
print('-----')
print_list(sum_list(node1, node2))``````

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

///#include <iostream>

struct Node {
int data;
Node* next;
explicit Node(int d) : data{d}, next{nullptr} {}
Node(int d, Node* n) : data{d}, next{n} {}
};

int getNum(Node* n) {
int num = 0;
auto curr = n;
while(curr){
num = num*10 + curr->data;
curr = curr->next;
}
return num;
}

Node* getSum(Node* a, Node* b){
int a_d = getNum(a);
int b_d = getNum(b);

auto sum = a_d + b_d;

while(sum){
auto node = new Node(sum % 10, head);
sum = sum / 10;
}

}

void print(Node* n)
{
auto curr = n;
while(curr) {
std::cout << curr->data << " -> ";
curr = curr->next;
}
std::cout << "NULL\n";
}

int main(){
auto n3 = Node(2);
auto n2 = Node(3, &n3);
auto n1 = Node(4, &n2);

auto m3 = Node(3);
auto m2 = Node(9, &m3);
auto m1 = Node(5, &m2);

print(getSum(&n1, &m1));

return EXIT_SUCCESS;
}\\\

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

``````#include <iostream>

struct Node {
int data;
Node* next;
explicit Node(int d) : data{d}, next{nullptr} {}
Node(int d, Node* n) : data{d}, next{n} {}
};

int getNum(Node* n) {
int num = 0;
auto curr = n;
while(curr){
num = num*10 + curr->data;
curr = curr->next;
}
return num;
}

Node* getSum(Node* a, Node* b){
int a_d = getNum(a);
int b_d = getNum(b);

auto sum = a_d + b_d;

while(sum){
auto node = new Node(sum % 10, head);
sum = sum / 10;
}

}

void print(Node* n)
{
auto curr = n;
while(curr) {
std::cout << curr->data << " -> ";
curr = curr->next;
}
std::cout << "NULL\n";
}

int main(){
auto n3 = Node(2);
auto n2 = Node(3, &n3);
auto n1 = Node(4, &n2);

auto m3 = Node(3);
auto m2 = Node(9, &m3);
auto m1 = Node(5, &m2);

print(getSum(&n1, &m1));

return EXIT_SUCCESS;
}``````

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

Is it ok to use stacks? Itâ€™s much simpler with stacks as temp storage

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

``````LinkedList<Integer> addTwoIntegers(LinkedList l1, LinkedList l2){

ArrayList<Integer> result = new ArrayList<>();

Iterator<Integer> iterator1 = l1.descendingIterator();
Iterator<Integer> iterator2 = l2.descendingIterator();
int rest = 0;

while (iterator1.hasNext() && iterator2.hasNext()){
int d1 = iterator1.next();
int d2 = iterator2.next();

rest = (d1 + d2)/10;
}

while (iterator1.hasNext()){
int d1 = iterator1.next();
rest = ((d1 + rest))/10;
}

while (iterator2.hasNext()){
int d2 = iterator2.next();
rest = ((d2 + rest))/10;
}
if (rest != 0)

Collections.reverse(result);

}``````

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

``````public static LinkedList<Integer> addTwoIntegers(LinkedList l1, LinkedList l2){

ArrayList<Integer> result = new ArrayList<>();

Iterator<Integer> iterator1 = l1.descendingIterator();
Iterator<Integer> iterator2 = l2.descendingIterator();
int rest = 0;

while (iterator1.hasNext() && iterator2.hasNext()){
int d1 = iterator1.next();
int d2 = iterator2.next();

rest = (d1 + d2)/10;
}

while (iterator1.hasNext()){
int d1 = iterator1.next();
rest = ((d1 + rest))/10;
}

while (iterator2.hasNext()){
int d2 = iterator2.next();
rest = ((d2 + rest))/10;
}
if (rest != 0)

Collections.reverse(result);

}``````

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

{
int carry = 0;
int maxlen,minlen;
if(num1.size() >= num2.size())
{
maxlen = num1.size();
minlen = num2.size();
shorter = num2;
longer = num1;
}
else
{
maxlen = num2.size();
minlen = num1.size();
shorter = num1;
longer = num2;
}

int diff = maxlen - minlen;
for(int i=0; i<diff; i++)
{
}

for(int i=maxlen-1; i>=0; i--)
{
int temp1 = longer.get(i);
int temp2 = shorter.get(i);
int temp3 = temp1 + temp2 + carry;
carry = 0;

if(temp3 >= 10)
{
carry = (temp3/10)%10;
temp3 = temp3%10;
}
}

if(carry > 0)

return res;
}

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

``````LinkedList<Integer> addList(LinkedList<Integer> num1, LinkedList<Integer> num2)
{
int carry = 0;
int maxlen,minlen;
if(num1.size() >= num2.size())
{
maxlen = num1.size();
minlen = num2.size();
shorter = num2;
longer = num1;
}
else
{
maxlen = num2.size();
minlen = num1.size();
shorter = num1;
longer = num2;
}

int diff = maxlen - minlen;
for(int i=0; i<diff; i++)
{
}

for(int i=maxlen-1; i>=0; i--)
{
int temp1 = longer.get(i);
int temp2 = shorter.get(i);
int temp3 = temp1 + temp2 + carry;
carry = 0;

if(temp3 >= 10)
{
carry = (temp3/10)%10;
temp3 = temp3%10;
}
}

if(carry > 0)

return res;
}``````

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

``````static LinkedList<Integer> addList(LinkedList<Integer> num1, LinkedList<Integer> num2)
{
int carry = 0;
int maxlen,minlen;
if(num1.size() >= num2.size())
{
maxlen = num1.size();
minlen = num2.size();
shorter = num2;
longer = num1;
}
else
{
maxlen = num2.size();
minlen = num1.size();
shorter = num1;
longer = num2;
}

int diff = maxlen - minlen;
for(int i=0; i<diff; i++)
{
}

for(int i=maxlen-1; i>=0; i--)
{
int temp1 = longer.get(i);
int temp2 = shorter.get(i);
int temp3 = temp1 + temp2 + carry;
carry = 0;

if(temp3 >= 10)
{
carry = (temp3/10)%10;
temp3 = temp3%10;
}
}

if(carry > 0)

return res;
}``````

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

If the question does not specifically ask to use LinkedList and do the math, you can simply convert it to string -> integer -> string -> list

``````LinkedList<Integer> first = new LinkedList<>();
System.out.print("first: " + first);
System.out.println();
String firstString = first.toString().replaceAll("\\[", "").replaceAll("\\]", "").replaceAll(", ", "");
System.out.print("firstString: " + firstString);
System.out.println();
Integer firstInt = Integer.parseInt(firstString);

System.out.print("second: " + second);
System.out.println();
String secondString = second.toString().replaceAll("\\[", "").replaceAll("\\]", "").replaceAll(", ", "");
System.out.print("secondString: " + secondString);
System.out.println();
Integer secondInt = Integer.parseInt(secondString);

Integer resultInt = firstInt + secondInt;
System.out.print("resultInt: " + resultInt);
System.out.println();

String resultString = resultInt.toString();
System.out.print("resultString: " + resultString);
System.out.println();
for(char number: resultString.toCharArray())
{
}

System.out.print("resultIntList: " + resultIntList);
System.out.println();``````

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

``````void  Ch1LinkedLists::add2SingleLinkedLists(std::forward_list<int> &l1, std::forward_list<int> &l2, std::forward_list<int> &final)
{
int sum1 = 0;
for (auto it1 = l1.begin(); it1 != l1.end(); it1++) {
sum1 *= 10;
sum1 += *it1;

}
int sum2 = 0;
for (auto it2 = l2.begin(); it2 != l2.end(); it2++) {
sum2 *= 10;
sum2 += *it2;
}
int sum = sum1 + sum2;
int carry = 0;
while (sum) {
final.push_front(sum % 10);
sum = sum / 10;
}``````

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

``````var sumNormalizedLinkedListNumbers = (a, b) => {
if(a == null && b == null)
return null
if(a == null)
return b
if(b == null)
return a

const currentDigitSum = a.value + b.value
const nextDigitSum = restSums == null ? null : restSums.value

if(nextDigitSum == null || nextDigitSum < 10) {
return {
value: currentDigitSum,
next: restSums
}
}

return {
value: currentDigitSum + 1,
next: {
value: nextDigitSum % 10,
next: restSums.next
}
}

}

return 0
}

while(numberOfZeros > 0) {
value: 0,
}
numberOfZeros--
}
}

// main function , it normalizes numbers, calls sumNormalizedNumbers and checks if first digit should be prefixed
var sumLinkedListNumbers = (a, b) => {
const lengthOfA = getLengthOfLinkedList(a) // O(n)
const lengthOfB = getLengthOfLinkedList(b) // O(n)
const maxLength = Math.max(lengthOfA, lengthOfB)

let normalizedA = a
if(lengthOfA < maxLength)
normalizedA = prependLinkedListWithZeros(a, maxLength - lengthOfA) // O(n)

let normalizedB = b
if(lengthOfB < maxLength)
normalizedB = prependLinkedListWithZeros(b, maxLength - lengthOfB) // O(n)

const result = sumNormalizedLinkedListNumbers(normalizedA, normalizedB) // O(n)

if(result.value < 10)
return result
return {
value: 1,
next: {
value: result.value % 10,
next: result.next
}
}
}``````

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

``````void addTwoLinkedListIntegers() {

int fSize = first.size();
int sSize = second.size();
int diff;

/* Prepend the zeros to match the digits count */
if (fSize < sSize) {
diff = sSize - fSize;
for (int i=0; i<diff ; i++)
}
else if (sSize < fSize) {
diff = fSize - sSize;
for (int i=0; i<diff ; i++)
}
int rem = 0;
int idx = first.size()-1;

for (int i=idx; i>=0; i--) {
int val = first.get(i)+second.get(i)+rem;
if (val > 9) {
rem = val/10;
} else {
rem=0;
}
}
System.out.println(result.toString());
}``````

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

Here is a recursive python code
the idea is to get the length of each of list
s1 is the length of l1(list1), s2 is the length of l2(list2)
the function is passed with the lengths
Till the point s1>s2, only l1 is moved
after the point s1==s2, both are moved,
at each step the sum of the value of nodes(if s1>s2, only l1 is available) is taken with the carry from previous call
new val and carry is calculated
the new list is progressively created by appending the node from previous call

``````class Node:
def __init__(self,val):
self.val = val
self.next = None

def __repr__(self):
string = ""
return string

class Llist:
def __init__(self):
self.tail = None
def insert(self, val):
node = Node(val)
else:
self.tail.next = node
self.tail = node
return True

def __repr__(self):
string = ""
return string

if not l1 or not l2:
return l1 or l2
s1 = 0
s1+=1

s2=0
s2+=1

if carry > 0:
node = Node(1)

if s2>s1:
if s1>s2:
rlist, carry = add_list_recursive(l1.next, l2, s1-1, s2)
temp_val = l1.val + carry
val, carry = (temp_val,0) if temp_val < 10 else (temp_val-10,1)
node = Node(val)
node.next = rlist
return node, carry
else:
carry = 0
rlist = None
if s1>1:
rlist,carry = add_list_recursive(l1.next, l2.next, s1-1, s2-1)
temp_val = l1.val + l2.val + carry
val, carry = (temp_val,0) if temp_val < 10 else (temp_val-10,1)
node = Node(val)
node.next = rlist
return node, carry

llist1 = Llist()
llist1.insert(9)
llist1.insert(2)
llist1.insert(3)
llist1.insert(4)
llist1.insert(5)
print(llist1)

llist2 = Llist()
# llist2.insert(9)
# llist2.insert(2)
# llist2.insert(3)
# llist2.insert(4)
print(llist2)

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

Here is a recursive solution in python

``````class Node:
def __init__(self,val):
self.val = val
self.next = None

def __repr__(self):
string = ""
return string

class Llist:
def __init__(self):
self.tail = None
def insert(self, val):
node = Node(val)
else:
self.tail.next = node
self.tail = node
return True

def __repr__(self):
string = ""
return string

if not l1 or not l2:
return l1 or l2
s1 = 0
s1+=1

s2=0
s2+=1

if carry > 0:
node = Node(1)

if s2>s1:
if s1>s2:
rlist, carry = add_list_recursive(l1.next, l2, s1-1, s2)
temp_val = l1.val + carry
val, carry = (temp_val,0) if temp_val < 10 else (temp_val-10,1)
node = Node(val)
node.next = rlist
return node, carry
else:
carry = 0
rlist = None
if s1>1:
rlist,carry = add_list_recursive(l1.next, l2.next, s1-1, s2-1)
temp_val = l1.val + l2.val + carry
val, carry = (temp_val,0) if temp_val < 10 else (temp_val-10,1)
node = Node(val)
node.next = rlist
return node, carry

llist1 = Llist()
llist1.insert(9)
llist1.insert(2)
llist1.insert(3)
llist1.insert(4)
llist1.insert(5)
print(llist1)

llist2 = Llist()
# llist2.insert(9)
# llist2.insert(2)
# llist2.insert(3)
# llist2.insert(4)
print(llist2)

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

we can use recursion just by knowing the lengths of each of the list. There is no other need to maintain your own stack

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

``````import collections

list1 = collections.deque()
list2 = collections.deque()
final = collections.deque()

list1.append(8)
list1.append(3)
list1.append(1)

list2.append(9)
list2.append(2)
list2.append(1)
list2.append(4)

print(len(list1))
#print(list2)

carry = 0

for i in range(len(list1) if len(list1) > len(list2) else len(list2)):

add = (list1.pop() if (len(list1) > 0) else 0) + (list2.pop() if len(list2) > 0 else 0) + carry

print(carry)
else:
carry = 0

if (carry):
final.appendleft(carry)

print(final)``````

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.