Facebook Interview Question for Interns


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

- duenytz January 22, 2019 | Flag Reply
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?

- Dan February 01, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dhiraj February 27, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

PollLast is an O(n) operation at worst.

- Shashank June 22, 2019 | Flag
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);
     }
}

- Barry January 18, 2019 | Flag Reply
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);
     }
}

- Barry January 18, 2019 | Flag Reply
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)

- nitinguptaiit March 31, 2019 | Flag
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

- Gordon January 19, 2019 | Flag Reply
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;
    }

- Vova January 24, 2019 | Flag Reply
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))

- baites January 25, 2019 | Flag Reply
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;
}\\\

- Anonymous January 26, 2019 | Flag Reply
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;
}

- Anonymous January 26, 2019 | Flag Reply
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

- Dan February 01, 2019 | Flag Reply
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);
    }

- Joanna February 07, 2019 | Flag Reply
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);
    }

- JZ February 07, 2019 | Flag Reply
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;
}

- Pri February 28, 2019 | Flag Reply
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;
	}

- Pri February 28, 2019 | Flag Reply
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;
	}

- Pri February 28, 2019 | Flag Reply
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();

- zebba March 01, 2019 | Flag Reply
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;
	}

- PJ March 14, 2019 | Flag Reply
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
            }
        }
    }

- ghsamm March 17, 2019 | Flag Reply
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());
    }

- vrk May 26, 2019 | Flag Reply
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))

- Shashank June 22, 2019 | Flag Reply
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))

- Anonymous June 22, 2019 | Flag Reply
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

- Shashank June 22, 2019 | Flag Reply
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;
  }
}

- sheng August 22, 2019 | Flag Reply


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