## Facebook Interview Question for Interns

• 0
of 0 votes

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) {
LinkedList<Integer> first = new LinkedList<>();
first.addFirst(4);
first.addFirst(9);
first.addFirst(3);
first.addFirst(1);
LinkedList<Integer> second = new LinkedList<>();
second.addFirst(8);
second.addFirst(1);
second.addFirst(3);
LinkedList<Integer> result = new LinkedList<>();
sumUpRecursive(first, second, result, false);
System.out.print("Result: " + result);
}

private static void sumUpRecursive(LinkedList<Integer> first, LinkedList<Integer> second, LinkedList<Integer> result, boolean carring) {
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
of 0 votes

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
of 0 votes

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

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

PollLast is an O(n) operation at worst.

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){
LinkedList<Integer> obj1 = new LinkedList<Integer> ();
LinkedList<Integer> obj2 = new LinkedList<Integer> ();
LinkedList<Integer> res = new LinkedList<Integer> ();
int maxlen,minlen;

obj1.add(9);
obj1.add(9);
obj1.add(9);
obj1.add(9);
obj2.add(3);
obj2.add(9);
obj2.add(2);

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

res.addFirst(tmp3);

}

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;
}
res.addFirst(tmp2);
}

if(carry !=0)
res.addFirst(carry);
}
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;
}
res.addFirst(tmp2);
}

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

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){
LinkedList<Integer> obj1 = new LinkedList<Integer> ();
LinkedList<Integer> obj2 = new LinkedList<Integer> ();
LinkedList<Integer> res = new LinkedList<Integer> ();
int maxlen,minlen;

obj1.add(9);
obj1.add(9);
obj1.add(9);
obj1.add(9);
obj2.add(3);
obj2.add(9);
obj2.add(2);

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

res.addFirst(tmp3);

}

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;
}
res.addFirst(tmp2);
}

if(carry !=0)
res.addFirst(carry);
}
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;
}
res.addFirst(tmp2);
}

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

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

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

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) {
LinkedList<Byte> result = new LinkedList<>();

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;
result.addFirst((byte) (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;
result.addFirst((byte) (sum % 10));
}
}

if (rest > 0) {
result.addFirst((byte) rest);
}

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;

Node* head = nullptr;

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

return head;
}

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;

Node* head = nullptr;

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

return head;
}

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

result.add((d1 + d2 + rest)%10);
rest = (d1 + d2)/10;
}

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

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

Collections.reverse(result);

return new LinkedList<>(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();

result.add((d1 + d2 + rest)%10);
rest = (d1 + d2)/10;
}

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

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

Collections.reverse(result);

return new LinkedList<>(result);
}``````

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

LinkedList<Integer> addList(LinkedList<Integer> num1, LinkedList<Integer> num2)
{
LinkedList<Integer> res = new LinkedList<Integer>();
LinkedList<Integer> shorter = new LinkedList<Integer>();
LinkedList<Integer> longer = new LinkedList<Integer>();
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;
}

//Pad shorter list to same length by adding preceeding 0
int diff = maxlen - minlen;
for(int i=0; i<diff; i++)
{
shorter.addFirst(0);
}

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;
}
res.addFirst(temp3);
}

if(carry > 0)
res.addFirst(carry);

return res;
}

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

``````LinkedList<Integer> addList(LinkedList<Integer> num1, LinkedList<Integer> num2)
{
LinkedList<Integer> res = new LinkedList<Integer>();
LinkedList<Integer> shorter = new LinkedList<Integer>();
LinkedList<Integer> longer = new LinkedList<Integer>();
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;
}

//Pad shorter list to same length by adding preceeding 0
int diff = maxlen - minlen;
for(int i=0; i<diff; i++)
{
shorter.addFirst(0);
}

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;
}
res.addFirst(temp3);
}

if(carry > 0)
res.addFirst(carry);

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)
{
LinkedList<Integer> res = new LinkedList<Integer>();
LinkedList<Integer> shorter = new LinkedList<Integer>();
LinkedList<Integer> longer = new LinkedList<Integer>();
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;
}

//Pad shorter list to same length by adding preceeding 0
int diff = maxlen - minlen;
for(int i=0; i<diff; i++)
{
shorter.addFirst(0);
}

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;
}
res.addFirst(temp3);
}

if(carry > 0)
res.addFirst(carry);

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<>();
first.addFirst(4);
first.addFirst(9);
first.addFirst(3);
first.addFirst(1);
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);

LinkedList<Integer> second = new LinkedList<>();
second.addFirst(8);
second.addFirst(1);
second.addFirst(3);
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();
LinkedList<Integer> resultIntList = new LinkedList<Integer>();
for(char number: resultString.toCharArray())
{
resultIntList.add(Integer.parseInt(String.valueOf(number)));
}

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 restSums = sumNormalizedLinkedListNumbers(a.next, b.next)
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
}
}

}

var getLengthOfLinkedList = linkedList => { // O(n)
if(!linkedList)
return 0
return 1 + getLengthOfLinkedList(linkedList.next)
}

var prependLinkedListWithZeros = (linkedList, numberOfZeros) => { // O(n)
while(numberOfZeros > 0) {
linkedList = {
value: 0,
next: linkedList
}
numberOfZeros--
}
return linkedList
}

// 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() {
LinkedList<Integer> result = new LinkedList<Integer>();
LinkedList<Integer> first = new LinkedList<Integer>();
first.addFirst(3);
first.addFirst(2);
first.addFirst(1);
LinkedList<Integer> second = new LinkedList<Integer>();
second.addFirst(7);
second.addFirst(5);
second.addFirst(4);
second.addFirst(3);

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++)
first.addFirst(0);
}
else if (sSize < fSize) {
diff = fSize - sSize;
for (int i=0; i<diff ; i++)
second.addFirst(0);
}
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) {
result.addFirst(val%10);
rem = val/10;
} else {
result.addFirst(val);
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
add_list_recursive(l1, l2, s1, s2)
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):
head = self
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string

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

def __repr__(self):
head = self.head
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string

def add_list(l1, l2):
if not l1 or not l2:
return l1 or l2
s1 = 0
head = l1
while(head):
s1+=1
head=head.next

s2=0
head=l2
while(head):
s2+=1
head=head.next

head,carry = add_list_recursive(l1, l2, s1, s2)
if carry > 0:
node = Node(1)
node.next = head
head = node
return head

def add_list_recursive(l1, l2, s1, s2):
if s2>s1:
return add_list_recursive(l2, l1, 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)

print(add_list(llist1.head,llist2.head))``````

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):
head = self
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string

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

def __repr__(self):
head = self.head
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string

def add_list(l1, l2):
if not l1 or not l2:
return l1 or l2
s1 = 0
head = l1
while(head):
s1+=1
head=head.next

s2=0
head=l2
while(head):
s2+=1
head=head.next

head,carry = add_list_recursive(l1, l2, s1, s2)
if carry > 0:
node = Node(1)
node.next = head
head = node
return head

def add_list_recursive(l1, l2, s1, s2):
if s2>s1:
return add_list_recursive(l2, l1, 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)

print(add_list(llist1.head,llist2.head))``````

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 java.io.*;
import java.util.*;

class MyCode {
public static void main (String[] args) {
LinkedList<Integer> first = new LinkedList<Integer>();
LinkedList<Integer> second = new LinkedList<Integer>();

first.addFirst(4);
first.addFirst(9);
first.addFirst(3);
first.addFirst(1);

second.addFirst(8);
second.addFirst(1);
second.addFirst(3);
second.addFirst(3);
second.addFirst(3);

LinkedList<Integer> sum = MyCode.sum(first, second);
for(Integer i: sum) {
System.out.print(i);
}
System.out.println("expected: " + (1394+33318));
}

public static LinkedList<Integer> sum(LinkedList first, LinkedList second) {
Iterator<Integer> firstIterator = first.descendingIterator();
Iterator<Integer> secondIterator = second.descendingIterator();
LinkedList<Integer>  ret = new LinkedList<Integer>();

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

ret.addFirst((a+b+rest)%10);
rest = (a + b + rest) / 10;
}

return ret;
}
}``````

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

if add >= 10:
carry = add - 9
add = 0
print(carry)
else:
carry = 0

final.appendleft(add)

if (carry):
final.appendleft(carry)

print(final)``````

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More