Bloomberg LP Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Phone Interview




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

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

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

4->5->6->
+
7->8->9->
----------
1->4->6->1->


4->5->
+
1->2->3->
----------
5->7->3->

- prudent_programmer March 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

- Sandesh Kamat March 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jersey355 March 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous April 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- badboy April 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Wayne May 30, 2018 | 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