## Microsoft Interview Question for Software Engineer in Tests

Country: United States

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

Use simple maths principles of face and place values.
Traverse list one (eg.5->6->3 ) multiply each digit with 10^n ,where n is nodecount starting at 0 and add the result. This would be 5*10^0 + 6*10^1+ 3*10^2 = 365
Similarly do for list 2 nd regular '+' operator.
Then to form a new resultant list take mod of 10 which will be the ones place,divide the number by 10, then loop this
Eg. 613
613%10 -> 3
613/10 =61; 61%10 -> 1 (item 2 in list)
61/10 =6 ; 6%10 -> 6 (item 3 in list )

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

i like your solution, can you shw implementation of this??

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

``````Node addTwoLists(ref Node head1, ref Node head2)
{
int carry = Math.Abs(sum / 10);

return null;
{
}
{
}
else
{
}
}``````

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

Can u please explain how (sum % 10)+carry in any AppendToHead(ref headx, (sum % 10) + carry);
function working ?
what I get is if der are two numbers :
365
+248
---------
for first (5+8) =13 then
3 -> carry 1
Then carry = sum/10 = 1
and sum%10 = 3
so what does (sum%10) + carry does ?

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

It will add any carry from the previous number... btw 5+8 =13
13%10 = 3 if there is the carry from previous values it add to the next sum

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

How would this soluntion work when we add 564 + 2

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

Carry recalculation when one of the lists gets exhausted is missing. and lastly create a new node if carry is set

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

Here a compact solution:

``````Node sum(Node a, Node b, boolean carry)
{
if(a == null && b == null && !carry)
return null;

if(a == null && b == null && carry)
return new Node(1);

int result = 0;

if(a != null)
result += a.value;

if(b != null)
result += b.value;

if(carry)
result++;

Node res = new Node(result % 10);

Node term1 = a != null ? a.next : null;
Node term2 = b != null ? b.next : null;
boolean carry1 = result > 9;

res.next = sum(term1, term2, carry1);

return res;
}``````

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

``````node * add_lists(node *h1, node *h2) {
int carry = 0, sum = 0;
node *sum_list = malloc(sizeof(node));
node *sum_list_current = sum_list;
while(h1 != NULL && h2 != NULL) {
sum = h1->data + h2->data + carry;
carry = sum/10;
sum %= 10;
push(&(sum_list_current->next), sum);
sum_list_current = sum_list_current->next;
h1 = h1->next;
h2 = h2->next;
}
while(h1 != NULL) {
sum = h1->data + carry;
carry = sum/10;
sum %= 10;
push(&(sum_list_current->next), sum);
sum_list_current = sum_list_current->next;
h1 = h1->next;
}
while(h2 != NULL) {
sum = h2->data + carry;
carry = sum/10;
sum %= 10;
push(&(sum_list_current->next), sum);
sum_list_current = sum_list_current->next;
h2 = h2->next;
}
if(carry > 0) {
push(&(sum_list_current->next), carry);
}
node *next = sum_list->next;
free(sum_list);
return next;
}``````

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

whats free(sum_list)? didnt understand..? arent the above codes not the same?

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

I used a dummy-node strategy in which the first element is a dummy node. Allows me to not require checking for the head == NULL case. Therefore, I need to free the dummy node before returning the next node which is the real node.

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

reverse the two linked lists (which can be done in O(n) ), simulate normal addition with carry, and reverse the final linked list again.

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

``````public static void main(String[] args) {
LinkedList<Integer> l1 = arr2ll(3, 6, 5);
LinkedList<Integer> l2 = arr2ll(1, 2, 3);

int car = 0;
for(Iterator<Integer> i1 = l1.iterator(), i2 = l2.iterator(); i1.hasNext() || i2.hasNext(); ){
int n1 = i1.hasNext() ? i1.next() : 0;
int n2 = i2.hasNext() ? i2.next() : 0;
int sum = (n1 + n2 + car) % 10;
car = (n1 + n2 + car) / 10;
}
if(car > 0)

printLL(l);
}

{
for(Iterator iter = ll.iterator(); iter.hasNext();)
System.out.println(iter.next());
}

public static <T extends Object> LinkedList<T> arr2ll(T...arr){
for(T t : arr)
return ll;
}``````

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

Entire working code below:

``````#include<stdio.h>
#include<stdlib.h>

typedef struct Digits digit;

typedef struct Digits
{
int value;
digit *next;
}digit;

digit* convert2list(int number);
digit* add(digit *num1_list, digit *num2_list, int carry);
int convert2int(digit *num_list);

void main()
{
int num1, num2, sum;
digit *num1_list, *num2_list, *sum_list;
printf("enter the two positive numbers: ");
scanf("%d%d", &num1, &num2);
num1_list = convert2list(num1);
num2_list = convert2list(num2);
sum = convert2int(sum_list);
printf("\n %d + %d = %d", num1, num2, sum);
printf("\nenter any character to exit: ");
scanf("%d", num1);
}

digit* convert2list(int number)
{
digit *node;
if (number == 0)
return NULL;
node = (digit*)malloc(sizeof(digit));
node->value = number%10;
node->next = convert2list(number/10);
return node;
}

int convert2int(digit* num_list)
{
if (num_list == NULL)
return 0;
else
return num_list->value + 10*convert2int(num_list->next);
}

digit* add(digit* num1_list, digit* num2_list, int carry)
{
int sum_digits;
digit *node;
if (num1_list == NULL && num2_list == NULL && carry == 0)
return NULL;

node = (digit*)malloc(sizeof(digit));
sum_digits = carry + (num1_list!=NULL?num1_list->value:0) + (num2_list!=NULL?num2_list->value:0);
node->value = sum_digits%10;
return node;
}``````

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

``````Node* list_sum(Node* A, Node* B) {
if (!A || !B) return NULL;
Node* prev = NULL;
int carry = 0;
while (A || B) {
int sum = 0;
if (A) { sum += A->val; A = A->next; }
if (B) { sum += B->val; B = B->next; }
sum += carry;
sum = sum % 10;
carry = sum / 10;
Node* sum_node = new Node(sum);
if (!prev) head = prev = sum_node;
else { prev->next = sum_node; prev = sum_node; }
}
}``````

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

Other than the recursive solution, we can also use STACKS. Below is the pseudocode

Push all nodes in list1 to Stack1
Push all nodes in list2 to Stack2
Simply pop from each stack and add the result to Stack 3
Finally pop Stack3 and create the output linked list.

Obviously this uses more space than the standard recursive approach.

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

#include<stdlib.h>
#include<stdio.h>

typedef struct node
{
struct node *next; // the reference to the next node
int data; // will store information
} node;

node* Insert(node *temp, node **h)
{

return *h;

}

node * reverse( node * ptr )
{
node * temp;
node * previous = NULL;
while(ptr != NULL) {
temp = ptr->next;
ptr->next = previous;
previous = ptr;
ptr = temp;
}
return previous;
}

node* SumLists(node *a, node *b)
{
node* sum = NULL;

int carry = 0;

while (a!=NULL && b!=NULL) {
int tmp = a->data + b->data + carry;
carry = 0;
if (tmp >= 10) {
carry = 1;
tmp = tmp%10;
}

node* current = (struct node*)malloc(sizeof(node));
current->data = tmp;
sum = Insert(current, &sum);

a = a->next;
b = b->next;
}

while(a!=NULL) {
node* current = (struct node*)malloc(sizeof(node));
int tmp = a->data+carry;
if (tmp>10) {
carry = tmp%10;
}
else {
carry = 0;
}

current->data = tmp;

sum = Insert(current, &sum);

a = a->next;
}

while(b!=NULL) {
node* current = (struct node*)malloc(sizeof(node));
int tmp = b->data+carry;
if (tmp>10) {
carry = tmp%10;
}
else {
carry = 0;
}

current->data = tmp;

sum = Insert(current, &sum);

b = b->next;
}

if(carry != 0)
{
node* current = (struct node*)malloc(sizeof(node));
current->data = carry;
sum = Insert(current, &sum);
}

//sum = reverse(sum);

return sum;
}

int main()
{
int i = 0;
int a = 0;
for (i; i<3; i++) {
struct node* temp = (struct node*)calloc(1, sizeof(struct node));
temp->data = i; // store data(first field)
}

i=0;
int j = 2;
for (i; i<3; i++) {
struct node* temp = (struct node*)calloc(1, sizeof(struct node));
temp->data = j+7; // store data(first field)
}

while (tmp != NULL) {
printf("%d",tmp->data);
tmp = tmp->next;
}

printf("------\n");

while (tmp != NULL) {
printf("%d",tmp->data);
tmp = tmp->next;
}

printf("------\n");

printf("sum=");
}

printf("\n");

}

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

``````struct node * add_sum_number_llist(struct node *list_one,
struct node *list_two ){
int carry = 0, num_one = 0, num_two = 0, temp_sum = 0, sum=0;
struct node *ret_list = NULL ;

while( (NULL != list_one) || (NULL != list_two)){
num_one = 0 ;
num_two = 0 ;
if (NULL != list_one){
num_one = list_one->value ;
list_one = list_one->next ;
}
if (NULL != list_two){
num_two = list_two->value ;
list_two = list_two->next ;
}
temp_sum = num_one + num_two + carry ;
sum *= 10 ;
sum += temp_sum % 10 ;
temp_sum /= 10 ;
carry = temp_sum % 10 ;

}
sum *= 10 ;
sum += carry ;
while (sum != 0){
insert(&ret_list, sum % 10 );
sum /= 10 ;
}
return ret_list ;
}``````

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

Java implementation. I see there are already several solutions posted for this problem.
I just wanted to put my solution out there for feedback.

Implementation takes in the head node of 2 linked lists as input and returns the node head of the linked list that contains their sum. The first portion of the addList method iterates through the 2 input list and adds each node until the end of the shortest input list is reached. If both list are the same length we are done. Assuming the number in a node ranges from 0 to 9 (going off the example), then the carry over to the next significant node will always be 1 and the data left in the current node will be (currentSum - 10). E.g. if you add 9 + 9 = 1(carry over to next node)8(current node sum). The second part of the adds the remaining nodes to the output node if we happened to have list of different lengths (i.e. one of the input list reaches null before the other). In this case the short list node entries are treated as 0 entries, which is equivalent to just copying the longer list node entries over.

``````public class Node{
public Node next;
public int data;
}

static Node addList(Node listOne, Node listTwo){
int carryOver = 0;
int dataSum = 0
Node sum = new Node();
Node currentNode = sum;

while(listOne != null || listTwo != null){
dataSum = ((listOne != null) ? listOne.data : 0) + ((listTwo != null) ? listTwo.data : 0)
dataSum += carryOver;
carryOver = 0;

if(dataSum > 10 ){
carryOver = 1;
dataSum -=10;
}

currentNode.data = dataSum;
currentNode.next = new Node();
currentNode = currentNode.next;
listOne = (listOne != null) ? listOne.next : null;
listTwo = (listTwo != null) ? listTwo.next : null;
}

if(carryOver){
currentNode.data = 1;
}

currentNode.next = null;
return(sum);
}``````

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

Can you please explain a bit?

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

I have added additional comment on my implementation. Let me know if you have additional questions. I also changed the implementation some to fix a loop bug and reduce code duplication.

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

Its simple as folllows.

``````Node * addLists(Node *n1,Node *n2,int carry)
{
if(n1==NULL && n2==NULL)
{
return NULL;
}
Node *n3=new Node;
int value=carry;
if(n1!=NULL)
{
value+=n1->data;
}
if(n2!=NULL)
{
value+=n2->data;
}
n3->data=value%10;
Node *res=addLists(n1->next,n2->next, value>=10 ? 1 : 0);
n3->next=res;
return n3;
}``````

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

``````public class AdditionOfTwoList {

if (l1 == null || l1.size() == 0 || l2 == null || l2.size() == 0) {
return;
}
int s1 = l1.size();
int s2 = l2.size();

int carryIn = 0;
int s = s1 < s2 ? s1 : s2;
for (int i = 0; i < s; i++) {
int a = l1.get(i);
int b = l2.get(i);
int c = a + b + carryIn;
carryIn = 0;
if (c > 9) {
c = c - 10;
carryIn = 1;
}
}
if (s1 < s2) {
for (int i = s1; i < s2; i++) {
int c = l2.get(i) + carryIn;
carryIn = 0;
}
} else if (s1 > s2) {
for (int i = s2; i < s1; i++) {
int c = l1.get(i) + carryIn;
carryIn = 0;
}
} else {
if (carryIn == 1) {
}
}
for (Integer i : result) {
System.out.print(i + " ");
}
}

public static void main(String[] args) {

}
}``````

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.

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