Facebook Interview Question for Android Engineers


Country: United States
Interview Type: Phone Interview




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

private LinkedList<Integer> sumList(LinkedList<Integer> l1, LinkedList<Integer> l2) {
        LinkedList<Integer> result = new LinkedList<>();
        
        Stack<Integer> stack1 = new Stack<>();
        Iterator<Integer> i1 = l1.iterator();
        while(i1.hasNext()) {
            stack1.push(i1.next());
        }
        
        Stack<Integer> stack2 = new Stack<>();
        Iterator<Integer> i2 = l2.iterator();
        while(i2.hasNext()) {
            stack2.push(i2.next());
        }
        int number = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty()) {
            number += stack1.isEmpty() ? 0 : stack1.pop();
            number += stack2.isEmpty() ? 0 : stack2.pop();
            result.addFirst(number%10);
            number /= 10;
        } 
        if(number != 0)
            result.addFirst(number);
        
        return result;
    }

- Popeye November 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution Using Ruby

class Node
	attr_accessor :value, :next_node

	def initialize(value)
		@value = value
	end
end

class LinkedList
	attr_accessor :first_node
	attr_accessor :values
	def initialize(first_node)
		@first_node = first_node
		@values = []
	end

	def traverse(node=first_node)
		return if node.nil?
		values.push(node.value)
		traverse(node.next_node)
	end

	def last_node
		node = first_node
		return node if node.next_node.nil?
		return node if node.next_node.nil? while (node = node.next_node)
	end

	def append(value)
		if first_node
		   last_node.next_node = Node.new(value)
		else
		   first_node = Node.new(value)
		end
	end
end

def sum_linked_list(linked_list_1, linked_list_2)
	linked_list_1.traverse
	linked_list_2.traverse

	values_1 = linked_list_1.values
	values_2 = linked_list_2.values

	stack_result = []

	carry_over= 0
	while values_1.any?
		sum = values_1.pop + values_2.pop + carry_over
		if sum < 10
			stack_result.push(sum)
		else
			modulus = sum % 10
			stack_result.push(modulus)
			carry_over = sum / 10
		end
	end

	stack_result.push(carry_over) if carry_over > 0
	
	first_node = Node.new(stack_result.pop)
	linked_list = LinkedList.new(first_node)
	while stack_result.any?
		linked_list.append(stack_result.pop)
	end
	return linked_list
end

node1 = Node.new(5)
node1.next_node = Node.new(6)
node1.next_node.next_node = Node.new(3)
linked_list_1 = LinkedList.new(node1)


node2 = Node.new(8)
node2.next_node =Node.new(4)
node2.next_node.next_node = Node.new(2) 
linked_list_2 = LinkedList.new(node2)

sum_linked_list(linked_list_1, linked_list_2)

- kusumah November 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node
	attr_accessor :value, :next_node

	def initialize(value)
		@value = value
	end
end

class LinkedList
	attr_accessor :first_node
	attr_accessor :values
	def initialize(first_node)
		@first_node = first_node
		@values = []
	end

	def traverse(node=first_node)
		return if node.nil?
		values.push(node.value)
		traverse(node.next_node)
	end

	def last_node
		node = first_node
		return node if node.next_node.nil?
		return node if node.next_node.nil? while (node = node.next_node)
	end

	def append(value)
		if first_node
		   last_node.next_node = Node.new(value)
		else
		   first_node = Node.new(value)
		end
	end
end

def sum_linked_list(linked_list_1, linked_list_2)
	linked_list_1.traverse
	linked_list_2.traverse

	values_1 = linked_list_1.values
	values_2 = linked_list_2.values

	stack_result = []

	carry_over= 0
	while values_1.any?
		sum = values_1.pop + values_2.pop + carry_over
		if sum < 10
			stack_result.push(sum)
		else
			modulus = sum % 10
			stack_result.push(modulus)
			carry_over = sum / 10
		end
	end

	stack_result.push(carry_over) if carry_over > 0
	
	first_node = Node.new(stack_result.pop)
	linked_list = LinkedList.new(first_node)
	while stack_result.any?
		linked_list.append(stack_result.pop)
	end
	return linked_list
end

node1 = Node.new(5)
node1.next_node = Node.new(6)
node1.next_node.next_node = Node.new(3)
linked_list_1 = LinkedList.new(node1)


node2 = Node.new(8)
node2.next_node =Node.new(4)
node2.next_node.next_node = Node.new(2) 
linked_list_2 = LinkedList.new(node2)

lst = sum_linked_list(linked_list_1, linked_list_2)

- kusumah November 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Python:

def list_to_stack (l):
	s = []
	for e in l:
		s.append(e)
	return s 

def add_ls (l1, l2):
	num = 0
	s3 = []
	s1 = list_to_stack (l1)
	s2 = list_to_stack (l2)
	while (len(s1) or len(s2) or num):
		n1 = 0 if len(s1) == 0 else s1.pop()
		n2 = 0 if len(s2) == 0 else s2.pop()
		num += n1 + n2
		s3.insert(0, int(num%10))
		num = int(num/10)
	return s3

// Input
l1 = [5, 6, 3]
l2 = [8, 4, 2]

result = add_ls (l1, l2)

- JayP November 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I didn't quite understand your solution, but looks like you dont even need "list_to_stack()" function. Look like you're converting list to back to same list again.

- MT November 23, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the list_to_stack() function is just pseudo for traversing the linked-list and creating a stack..

- matt December 19, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift

class Node {
    
    var next: Node?
    
    var number: Int
    
    init(number: Int, next: Node? = nil) {
        self.number = number
        self.next = next
    }
    
}

extension Node {

    func reverse() -> Node {
        var result:[Int] = []
        var current: Node? = self
        while current != nil {
            result.insert(current?.number ?? 0, at: 0)
            current = current?.next
        }
        current = nil
        var start: Node?
        for n in result {
            let node = Node(number: n)
            if current != nil {
                current?.next = node
            } else {
                start = node
            }
            current = node
        }
        return start!
    }

    var asInt: Int {
        var result = 0
        var current: Node? = self
        while current != nil {
            result = result * 10
            result += current?.number ?? 0
            current = current?.next
        }
        return result
    }

}

let input1 = Node(number: 5, next: Node(number: 6, next: Node(number: 3)))
let input2 = Node(number: 8, next: Node(number: 4, next: Node(number: 2)))

func sum(input1: Node, input2: Node) -> Node {
    var input1: Node? = input1.reverse()
    var input2: Node? = input2.reverse()
    
    var start: Node?
    var current: Node?
    
    var r = 0
    while input1 != nil && input2 != nil {
        let sum = (input1?.number ?? 0) + (input2?.number ?? 0) + r
        r = sum / 10
        if current != nil {
            current?.next = Node(number: sum % 10)
            current = current?.next
        } else {
            current = Node(number: sum % 10)
            start = current
        }
        input1 = input1?.next
        input2 = input2?.next
    }
    if r != 0 {
        current?.next = Node(number: r)
    }
    return start!.reverse()
}

print(sum(input1: input1, input2: input2).asInt) // 1405

- eugene.kazaev November 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the solution should use O(1) space. We can reverse(LL) in O(n). Add up and then reverse Again. will end up O(n) and O(1) space.

- Aks November 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <list>

std::list<int> sumList(std::list<int> l1, std::list<int> l2);
void printDigits(std::list<int> list);

int main()
{
    std::cout << "Hello World!\n";
    
    int firstInts[] = {5, 6, 3};
    std::list<int> first(firstInts, firstInts + sizeof(firstInts) / sizeof(int));
    int secondInts[] = {8, 4, 2};
    std::list<int> second(secondInts, secondInts + sizeof(secondInts) / sizeof(int));
    
    printDigits(first);
    printDigits(second);
    
    std::list<int> sum;
    if (first.size() >= second.size())
    {
        sum = sumList(first, second);   
    }
    else
    {
        sum = sumList(second, first);
    }
    
    printDigits(sum);
}

void printDigits(std::list<int> list)
{
    while(list.size() > 0)
    {
        std::cout << list.front();
        list.pop_front();
        if (list.size() > 0)
        {
            std::cout << "-\>";
        }
    }
    std::cout << "\n";
}

// assumes first list is not less than second list
std::list<int> sumList(std::list<int> l1, std::list<int> l2)
{
    std::list<int> sum;
    int carryOne = 0;
    
    while (l1.size() > 0)
    {
        int stepSum = 0;
        if (l2.size() > 0)
        {
            stepSum = l1.back() + l2.back() + carryOne;
            l1.pop_back();
            l2.pop_back();
        }
        else
        {
            stepSum = l1.back() + carryOne;
            l1.pop_back();
        }
        carryOne = 0;
        
        if (stepSum >= 10)
        {
            carryOne = 1;
        }
        
        stepSum %= 10;
        
        sum.push_front(stepSum);
    }
    
    if (carryOne)
    {
        sum.push_front(carryOne);
    }
    
    return sum;
}

- Solution in C++ December 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in C++:

#include <iostream>
#include <list>

std::list<int> sumList(std::list<int> l1, std::list<int> l2);
void printDigits(std::list<int> list);

int main()
{
    std::cout << "Hello World!\n";
    
    int firstInts[] = {5, 6, 3};
    std::list<int> first(firstInts, firstInts + sizeof(firstInts) / sizeof(int));
    int secondInts[] = {8, 4, 2};
    std::list<int> second(secondInts, secondInts + sizeof(secondInts) / sizeof(int));
    
    printDigits(first);
    printDigits(second);
    
    std::list<int> sum;
    if (first.size() >= second.size())
    {
        sum = sumList(first, second);   
    }
    else
    {
        sum = sumList(second, first);
    }
    
    printDigits(sum);
}

void printDigits(std::list<int> list)
{
    while(list.size() > 0)
    {
        std::cout << list.front();
        list.pop_front();
        if (list.size() > 0)
        {
            std::cout << "-\>";
        }
    }
    std::cout << "\n";
}

// assumes first list is not less than second list
std::list<int> sumList(std::list<int> l1, std::list<int> l2)
{
    std::list<int> sum;
    int carryOne = 0;
    
    while (l1.size() > 0)
    {
        int stepSum = 0;
        if (l2.size() > 0)
        {
            stepSum = l1.back() + l2.back() + carryOne;
            l1.pop_back();
            l2.pop_back();
        }
        else
        {
            stepSum = l1.back() + carryOne;
            l1.pop_back();
        }
        carryOne = 0;
        
        if (stepSum >= 10)
        {
            carryOne = 1;
        }
        
        stepSum %= 10;
        
        sum.push_front(stepSum);
    }
    
    if (carryOne)
    {
        sum.push_front(carryOne);
    }
    
    return sum;
}

- Jace December 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args){

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

List<Integer> list1 = new LinkedList<>();
list1.add(5);
list1.add(6);
list1.add(3);

System.out.println("list 1 values are"+ list1);

List<Integer> list2 = new LinkedList<>();
list2.add(8);
list2.add(4);
list2.add(2);

System.out.println("list 2 values are"+ list2);

//Stack<Integer> stack1 = new Stack<>();
String str1 = "";
Iterator<Integer> i1 = list1.iterator();
while(i1.hasNext()) {
//stack1.push(i1.next());
str1 += i1.next();
}

System.out.println("str1 values are"+ str1);

//Stack<Integer> stack2 = new Stack<>();
String str2 = "";
Iterator<Integer> i2 = list2.iterator();
while(i2.hasNext()) {
//stack2.push(i2.next());
str2 += i2.next();
}

Integer i = Integer.parseInt(str1) + Integer.parseInt(str2);
System.out.println(i);

}

- Sunny Ahuja December 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args){

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

List<Integer> list1 = new LinkedList<>();
list1.add(5);
list1.add(6);
list1.add(3);

System.out.println("list 1 values are"+ list1);

List<Integer> list2 = new LinkedList<>();
list2.add(8);
list2.add(4);
list2.add(2);

System.out.println("list 2 values are"+ list2);

//Stack<Integer> stack1 = new Stack<>();
String str1 = "";
Iterator<Integer> i1 = list1.iterator();
while(i1.hasNext()) {
//stack1.push(i1.next());
str1 += i1.next();
}

System.out.println("str1 values are"+ str1);

//Stack<Integer> stack2 = new Stack<>();
String str2 = "";
Iterator<Integer> i2 = list2.iterator();
while(i2.hasNext()) {
//stack2.push(i2.next());
str2 += i2.next();
}

Integer i = Integer.parseInt(str1) + Integer.parseInt(str2);
System.out.println(i);

}

- Sunny December 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args){

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

        List<Integer> list1 = new LinkedList<>();
        list1.add(5);
        list1.add(6);
        list1.add(3);

        System.out.println("list 1 values are"+ list1);

        List<Integer> list2 = new LinkedList<>();
        list2.add(8);
        list2.add(4);
        list2.add(2);

        System.out.println("list 2 values are"+ list2);

        //Stack<Integer> stack1 = new Stack<>();
        String str1 = "";
        Iterator<Integer> i1 = list1.iterator();
        while(i1.hasNext()) {
            //stack1.push(i1.next());
            str1 += i1.next();
        }

        System.out.println("str1 values are"+ str1);

        //Stack<Integer> stack2 = new Stack<>();
        String str2 = "";
        Iterator<Integer> i2 = list2.iterator();
        while(i2.hasNext()) {
            //stack2.push(i2.next());
            str2 += i2.next();
        }

       Integer i = Integer.parseInt(str1) + Integer.parseInt(str2);
        System.out.println(i);

    }

- Sunny December 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function reverseLinkedList(node){
    function* reverseGenerator(node){
        if (node.next){
            yield* reverseGenerator(node.next);
        }

        yield node;
    }

    return reverseGenerator(node);
}

function getNodeNumValue(node){
    return ((node && node.value) || 0);
}

const sumTwoLinkedLists = (first, second) => {
    const firstReversed = reverseLinkedList(first);
    const secondReversed = reverseLinkedList(second);

    let firstListNode = firstReversed.next().value;
    let secondListNode = secondReversed.next().value; 
    let curry = 0;
    let nextNode;

    while(firstListNode || secondListNode){
        let sum = getNodeNumValue(firstListNode) + getNodeNumValue(secondListNode) + curry;

        curry = sum >= 10 ? 1 : 0;
        sum = sum % 10;

        let currentNode = {value: sum, next: nextNode};
        nextNode = currentNode;

        firstListNode = firstReversed.next().value;
        secondListNode = secondReversed.next().value; 
    }

    return nextNode;

}

- vladimir.s December 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function reverseLinkedList(node){
    function* reverseGenerator(node){
        if (node.next){
            yield* reverseGenerator(node.next);
        }

        yield node;
    }

    return reverseGenerator(node);
}

function getNodeNumValue(node){
    return ((node && node.value) || 0);
}

const sumTwoLinkedLists = (first, second) => {
    const firstReversed = reverseLinkedList(first);
    const secondReversed = reverseLinkedList(second);

    let firstListNode = firstReversed.next().value;
    let secondListNode = secondReversed.next().value; 
    let curry = 0;
    let nextNode;

    while(firstListNode || secondListNode){
        let sum = getNodeNumValue(firstListNode) + getNodeNumValue(secondListNode) + curry;

        curry = sum >= 10 ? 1 : 0;
        sum = sum % 10;

        let currentNode = {value: sum, next: nextNode};
        nextNode = currentNode;

        firstListNode = firstReversed.next().value;
        secondListNode = secondReversed.next().value; 
    }

    return nextNode;

}

- vladimir.s December 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Kotlin (not really taking advantage of the linked list. This solution will work for any list)

fun sumList(list1: LinkedList<Int>, list2: LinkedList<Int>): LinkedList<Int> {

    return LinkedList((list1.toInt() + list2.toInt()).toListOfInt())
}

fun List<Int>.toInt(): Int {
    val startingExponent = this.size - 1
    return this.foldIndexed(0.0) { index, acc, element ->
        acc + element * Math.pow(10.0, ((startingExponent - index).toDouble()))
    }.toInt()
}

fun Int.toListOfInt(): List<Int> {
    val list: LinkedList<Int> = LinkedList()
    var number = this
    while (number > 0) {
        list.addFirst((number % 10))
        number /= 10
    }
    return list
}

- Joao March 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public LinkedList<Integer> sumListMine(LinkedList<Integer> l1, LinkedList<Integer> l2) {
        LinkedList<Integer> result = new LinkedList<>();
        
        int number = 0;
        while(!l1.isEmpty() || !l2.isEmpty()) {
            
            number += l1.isEmpty() ? 0 : l1.pollLast();
            number += l2.isEmpty() ? 0 : l2.pollLast();
            result.addFirst(number % 10);
            number /= 10;
        }
        
        if (number != 0)
            result.addFirst(number);
        
        return result;
    }

- Zeeshan Aslam October 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and

- Zeeshan Aslam October 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

fsdfsdfs

- Zeeshan Aslam October 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public LinkedList<Integer> sumListMine(LinkedList<Integer> l1, LinkedList<Integer> l2) {
        LinkedList<Integer> result = new LinkedList<>();
        
        int number = 0;
        while(!l1.isEmpty() || !l2.isEmpty()) {
            
            number += l1.isEmpty() ? 0 : l1.pollLast();
            number += l2.isEmpty() ? 0 : l2.pollLast();
            result.addFirst(number % 10);
            number /= 10;
        }
        
        if (number != 0)
            result.addFirst(number);
        
        return result;
    }

- android.zeeshan October 21, 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