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


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