Facebook Interview Question
Android EngineersCountry: United States
Interview Type: Phone Interview
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)
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)
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)
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.
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
#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++:
#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;
}
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);
}
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);
}
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);
}
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;
}
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;
}
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
}
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;
}
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;
}
- Popeye November 17, 2018