Bloomberg LP Interview Question Senior Software Development Engineers
Country: United States
Interview Type: Phone Interview
Solution in java:
import java.util.Iterator;
import java.util.LinkedList;
/**
* Solution:
* Step 1: Sort LinkedList in descending order
* Step 2: Check x[i] + y[i] + carryover > 10 ? assign carryForward = 1, substract 10 from result
* Step 3: insert result in resulting LinkedList
* Step 4: insert final carry over
* @author sk14882
*
*/
public class AddingLinkListNumbers {
protected LinkedList<Integer> sum(int x[], int[] y) {
LinkedList<Integer> l1 = new LinkedList<>();
LinkedList<Integer> l2 = new LinkedList<>();
LinkedList<Integer> lr = new LinkedList<>();
for (Integer i: x) {
l1.add(i);
}
System.out.println("Input l1[] -> " +l1);
for (Integer i: y) {
l2.add(i);
}
System.out.println("Input l2[] -> " + l2);
Iterator<Integer> i1r = l1.descendingIterator();
Iterator<Integer> i2r = l2.descendingIterator();
int carryForward=0;
while(i1r.hasNext() || i2r.hasNext()) {
Integer i = (i1r.hasNext() ? i1r.next() : 0);
Integer j = (i2r.hasNext() ? i2r.next() : 0);
int result = i+j+carryForward;
if(result >= 10) {
carryForward = 1;
result = result - 10;
} else {
carryForward = 0; //reset
}
lr.addFirst(result);
}
if(carryForward > 0) {
lr.addFirst(carryForward);
}
System.out.println("Result r[] -> " + lr);
return lr;
}
}
Test Code:
package com.hacker.rank.challenges;
import static org.hamcrest.Matchers.equalTo;
import static org.junit.Assert.assertThat;
import java.util.LinkedList;
import org.junit.Test;
public class AddingLinkListNumbersTest {
private static int[] x1 = new int[] {1,2,3};
private static int[] y1 = new int [] {4,5,6};
private static int[] x2 = new int[] {1,2,3};
private static int[] y2 = new int[] {4,5};
private static int[] x3 = new int[] {4,5,6};
private static int[] y3 = new int[] {7,8,9};
@Test
public void testSum() throws Exception {
AddingLinkListNumbers sample = new AddingLinkListNumbers();
LinkedList<Integer> lr1 = new LinkedList<>();
lr1.add(5);
lr1.add(7);
lr1.add(9);
assertThat(sample.sum(x1, y1), equalTo(lr1));
LinkedList<Integer> lr2 = new LinkedList<>();
lr2.add(1);
lr2.add(6);
lr2.add(8);
assertThat(sample.sum(x2, y2), equalTo(lr2));
LinkedList<Integer> lr3 = new LinkedList<>();
lr3.add(1);
lr3.add(2);
lr3.add(4);
lr3.add(5);
assertThat(sample.sum(x3, y3), equalTo(lr3));
}
}
Output:
Input l1[] -> [1, 2, 3]
Input l2[] -> [4, 5, 6]
Result r[] -> [5, 7, 9]
Input l1[] -> [1, 2, 3]
Input l2[] -> [4, 5]
Result r[] -> [1, 6, 8]
Input l1[] -> [4, 5, 6]
Input l2[] -> [7, 8, 9]
Result r[] -> [1, 2, 4, 5]
The Java solution above seems like a lot of code ... Here's a simpler O(n) version:
public static LinkedList<Integer> add(LinkedList<Integer> a, LinkedList<Integer> b) {
LinkedList<Integer> result = new LinkedList<Integer>();
String sum = (parseValue(a) + parseValue(b)) + "";
for(Character digit : sum.toCharArray())
result.add(Character.digit(digit, 10));
return result;
}
public static int parseValue(LinkedList<Integer> list) {
if(list == null || list.isEmpty()) return 0;
StringBuilder sb = new StringBuilder();
for(int digit : list)
sb.append(digit);
return Integer.parseInt(sb.toString());
}
struct Node* reverse(struct Node* head) {
struct Node* p = head;
struct Node* prev = 0;
while(p) {
head = p;
p = p->next;
head->next = prev;
prev = head;
}
return head;
}
struct Node* suml(struct Node* f, struct Node* s) {
f = reverse(f);
s = reverse(s);
int carry = 0;
struct Node* head = 0;
while(f || s || carry > 0) {
if(f) {
carry += f->data;
f = f->next;
}
if(s) {
carry += s->data;
s = s->next;
}
struct Node* tmp = malloc(sizeof(struct Node));
tmp->data = carry % 10;
carry /= 10;
tmp->next = head;
head = tmp;
}
f = reverse(f);
s = reverse(s);
return head;
}
struct Node* reverse(struct Node* head) {
struct Node* p = head;
struct Node* prev = 0;
while(p) {
head = p;
p = p->next;
head->next = prev;
prev = head;
}
return head;
}
struct Node* suml(struct Node* f, struct Node* s) {
f = reverse(f);
s = reverse(s);
int carry = 0;
struct Node* head = 0;
while(f || s || carry > 0) {
if(f) {
carry += f->data;
f = f->next;
}
if(s) {
carry += s->data;
s = s->next;
}
struct Node* tmp = malloc(sizeof(struct Node));
tmp->data = carry % 10;
carry /= 10;
tmp->next = head;
head = tmp;
}
f = reverse(f);
s = reverse(s);
return head;
}
Node *Add(Node *h1, Node *h2)
{
Node head;
Node *curr = &head;
int sum = 0;
while ( h1 != NULL || h2 != NULL)
{
Node* sumNode = new Node;
sum = 0;
if( h1 != NULL)
{
sum += h1->value;
h1 = h1->next;
}
if( h2 != NULL)
{
sum += h2->value;
h2 = h2->next;
}
sumNode->value = sum;
sumNode->next = NULL;
curr->next = sumNode;
curr = sumNode;
}
return head.next;
}
C++ solution
#include <list>
using namespace std;
typedef list<int> IntList;
IntList::value_type getListValue(const IntList &intlist)
{
IntList::value_type value = 0;
for (IntList::const_iterator i = intlist.cbegin(), iEnd = intlist.cend(); i != iEnd; ++i) {
value *= 10;
value += *i;
}
return value;
}
IntList sumIntList(const IntList &i1, const IntList &i2)
{
IntList sumList;
for (int sum = getListValue(i1) + getListValue(i2); sum; sum /= 10) {
sumList.push_front(sum % 10);
}
return sumList;
}
Maintain a variable for totalSum and another variable for carry. Add the value based on the head of the linked lists. Keep iterating while there is another node in the linked list or there is a carry. TC:- O(n+m) where n and m are the size of the linked lists. SC:- O(n+m) since we are constructing a new linked list and returning it. My solution in Python:
def addTwoNums(head1, head2): carry = 0 curr = dummy = Node(None) while head1 or head2 or carry: totalSum = 0 if head1: totalSum += head1.value head1 = head1.next if head2: totalSum += head2.value head2 = head2.next totalSum += carry carry = totalSum // 10 curr.next = Node(totalSum % 10) curr = curr.next return dummy.nextTest code:
# Test code class Node: def __init__(self, value): self.value = value self.next = None def printList(head): while head != None: print(head.value, end='->') head = head.next num1 = Node(4) num1.next = Node(5) num1.next.next = Node(6) num2 = Node(7) num2.next = Node(8) num2.next.next = Node(9) result = addTwoNums(num1, num2) printList(num1) print('\n+') printList(num2) print('\n' + ('-'*10)) printList(result) num1 = Node(4) num1.next = Node(5) num2 = Node(1) num2.next = Node(2) num2.next.next = Node(3) result = addTwoNums(num1, num2) print('\n\n') printList(num1) print('\n+') printList(num2) print('\n' + ('-'*10)) printList(result)Output:
- prudent_programmer March 14, 2018