Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
Here my doubt is
if the function is retuning only Node, how the output will come as list ?
In amazon written test, out should be list but i am still confused that function is retuning Node so if i return node, it will print only 1st digit of the linked list.
the function will return the "head" of the sum list. So we can use that to print the final sum. Returning list means to return the head element pointer.
That's right. We can return head of the new list. Actually I am able to write recursive function to create the sum list but assuming both are of the same length. Anyone has better idea how can we make it work for unequal length list??
private Node SumEqualListR(Node head1, Node head2)
{
int carry;
Node temp;
if (head1.next == null && head2.next == null)
{
int sum = head1.key + head2.key;
return new Node(sum);
}
temp = SumEqualListR(head1.next, head2.next);
carry = temp.key / 10;
temp.key = temp.key % 10;
Node newnode = new Node(head1.key + head2.key + carry);
newnode.next = temp;
return newnode;
}
You can create 2 stacks from each link list. Then start popping out bigger stack and on the same time pop up the smaller stack...do the sum of values and take a division and modular division. Save the value of modular division in node of new link list and hold the value of Divisor to sum up in next cycle.
I guess it would have been quite easier to get the solution without using extra space, if it would have been a doubly linked list. Did you confirm first that it was/n't a doubly linked list?
struct node* add(struct node* l1,struct node* l2)
{
l1 = reverse(l1);
l2 = reverse(l2);
struct node* l3 = malloc(sizeof(struct node*));
l3 = NULL;
int carry =0;
while(l1 != NULL || l2 != NULL)
{
int sum = ((l1 == NULL?0:l1->data ) + (l2 == NULL?0:l2->data ) + carry)%10;
carry = ((l1 == NULL?0:l1->data ) + (l2 == NULL?0:l2->data ) )/10;
push(&l3,sum);
if(l1!=NULL)l1=l1->next;
if(l2!=NULL)l2=l2->next;
}
push(&l3,carry);
return l3;
}
Traverse first linkedlist and find the number - 4-5-7-6 -> 4576
Similarly traverse second linked list and find the number 5-7 -> 57
add num1 and num2 and conver to string using Integer.toString(num1+num2);
Create a linkedlist by taking each character of the string starting from s[0] then s[1] etc till s.length()
Node addLinkList( Node h1, node h2)
{
Node temp;
if(h1.next == null && h2.next==null) {
return(new Node(h1.val + h2.val, null);
}
else if(h1.next == null) {
temp = addLinkList(h1,h2.next);
}
else if(h2.next == null ) {
temp = addLinList(h1.next,h2);
}
else {
temp=addLinkList(h1.next,h2.next);
}
int carry = temp.val/10;
temp.val = temp.val%10;
return(new Node(carry+h1.val+h2.val,temp);
}
Java code to add the node values
public static Node addLists(Node head1, Node head2){
if(head1==null && head2==null){
return null;
}else if(head1 == null){
return head2;
}else if(head2 == null){
return head1;
}
Node newHead = null;
Node newCurr = null;
Node curr1 = head1;
Node curr2 = head2;
int carry = 0;
while(curr1 != null && curr2 != null){
int newSum = curr1.data + curr2.data + carry;
if(newSum >= 10){
carry = 1;
newSum = newSum - 10;
}else{
carry = 0;
}
if(newHead == null){//first node
newHead = new Node(newSum);
newCurr = newHead;
}else{//subsequent nodes
newCurr.next = new Node(newSum);
newCurr = newCurr.next;
}
curr1= curr1.next;
curr2= curr2.next;
}
while(curr1 != null){
int newSum = curr1.data + carry;
if(newSum >= 10){
carry = 1;
newSum = newSum - 10;
}else{
carry = 0;
}
newCurr.next = new Node(newSum);
newCurr = newCurr.next;
curr1= curr1.next;
}
while(curr2 != null){
int newSum = curr2.data + carry;
if(newSum >= 10){
carry = 1;
newSum = newSum - 10;
}else{
carry = 0;
}
newCurr.next = new Node(newSum);
newCurr = newCurr.next;
curr2= curr2.next;
}
if(carry == 1){
newCurr.next = new Node(1);
newCurr = newCurr.next;
}
newCurr.next = null;
return newHead;
}
/* Cases: both lists null -> exception
1 list null -> other list
both lists non null -> return sum */
public Node merge(Node n1, Node n2)
{
if (n1 == null || n2 == null )
{
if (n1 == null && n2 == null )
throw new exception("Null lists");
else if (n1 == null)
return n2;
else
return n1;
}
int s1 = 0;
while (n1 != null)
{
s1 = 10 * s1 + n1.data;
n1 = n1.next;
}
int s2 = 0;
while (n2 != null)
{
s2 = 10 * s2 + n2.data;
n2 = n2.next;
}
int sum = s1 + s2;
Stack s = new Stack();
while (sum != 0)
{
s.push(sum % 10);
sum = sum / 10;
}
Node n = new Node();
Node current = n;
while (!s.empty())
{
node t = new Node();
t.data = s.pop();
if (current == null)
current = t;
else
{
current.next = t;
current = current.next;
}
}
return n;
}
/* Cases: both lists null -> exception
1 list null -> other list
both lists non null -> return sum */
public Node merge(Node n1, Node n2)
{
if (n1 == null || n2 == null )
{
if (n1 == null && n2 == null )
throw new exception("Null lists");
else if (n1 == null)
return n2;
else
return n1;
}
int s1 = 0;
while (n1 != null)
{
s1 = 10 * s1 + n1.data;
n1 = n1.next;
}
int s2 = 0;
while (n2 != null)
{
s2 = 10 * s2 + n2.data;
n2 = n2.next;
}
int sum = s1 + s2;
Stack s = new Stack();
while (sum != 0)
{
s.push(sum % 10);
sum = sum / 10;
}
Node n = new Node();
Node current = n;
while (!s.empty())
{
node t = new Node();
t.data = s.pop();
if (current == null)
current = t;
else
{
current.next = t;
current = current.next;
}
}
return n;
}
public Node addList(Node n1, Node n2) {
if(n1.nextNode == null && n2.nextNode == null) {
int value = n1.value + n2.value;
return new Node(value, null);
}
Node next1 = n1.nextNode != null ? n1.nextNode : n1;
Node next2 = n2.nextNode != null ? n2.nextNode : n2;
Node temp = addList(next1, next2);
int carry = 0;
if(temp != null && temp.value > 9) {
carry = 1;
temp.value = temp.value - 10;
}
Node result = new Node(n1.value+n2.value+carry, temp);
return result;
}
public Node addList(Node n1, Node n2) {
if(n1.nextNode == null && n2.nextNode == null) {
int value = n1.value + n2.value;
return new Node(value, null);
}
Node next1 = n1.nextNode != null ? n1.nextNode : n1;
Node next2 = n2.nextNode != null ? n2.nextNode : n2;
Node temp = addList(next1, next2);
int carry = 0;
if(temp != null && temp.value > 9) {
carry = 1;
temp.value = temp.value - 10;
}
Node result = new Node(n1.value+n2.value+carry, temp);
return result;
}
public static Node addList(Node n1, Node n2) {
if(n1.nextNode == null && n2.nextNode == null) {
int value = n1.value + n2.value;
return new Node(value, null);
}
Node next1 = n1.nextNode != null ? n1.nextNode : n1;
Node next2 = n2.nextNode != null ? n2.nextNode : n2;
Node temp = addList(next1, next2);
int carry = 0;
if(temp != null && temp.value > 9) {
carry = 1;
temp.value = temp.value - 10;
}
Node result = new Node(n1.value+n2.value+carry, temp);
return result;
}
Reverse both the linked lists -> O(n+m)
- y2km11 February 26, 2012Traverse both linked lists simultaneously, building the the sum linked list -> O(n)
Reverse the sum linked list -> O(n)
Space -> O(1)