Google Interview Question Software Engineer / Developers
Country: United States
I not quite understand questions. Are the LinkeLists store binary number in theirs cells or the two linklists represent two binary number and each cell of them store a 1 or 0 number.
For the first situation how about the code below:
String calLists(LinkeList<String> al1, LinkedList<String> al2){
if(al1==null&&al2==null)
{
return null;
}
int sum=0;
if(al1==null){
for (int i=0; i<al2.size(); i++){
sum+=Integer.parseInt(al2.get(i),10)
}
}
if(al2==null){
for(int i=0; i<al1.size(); i++){
sum+=Integer.parseInt(al1.get(i),10)
}
return toBinaryString(sum);
}
int al1Size=al1.size();
int al2Size=al2.size();
int i=0;
for(i; i<(al1Size<al2Size?al1Size:al2Size); i++){
sum+=Integer.parInt(al1.get(i), 10)+Integer.parseInt(al2.get(i),10);
}
LinkeList temp=al1Size>al2Size?al1:al2
for(i=i+1; i<(al1Size>al2Size?al1Size:al2Size);i++){
sum+=temp.get(i);
}
return toBinarString(sum);
}
For situation two:
String calLink(LinkedList<Char> al1, LinkedList<Char> al2){
if(al1==null&&al2==null){
return null;
}
StringBuffer s;
if(al1==null){
s=new StringBuffer();
for(int i=0; i<al2.size(); i++){
s.append(al2.get(i));
}
return s.toString();
}
if(al2==null){
s=new StringBuffer();
for(int i=0; i<al1.size(); i++){
s.append(al1.get(i));
}
return s.toString();
}
s= new StringBuffer();
for(int i=0; i<al1.size();i++){
s.append(al1.get(i));
}
valueAl1=Integer.parseInt(s.toString(),10);
s=new StringBuffer();
for(int i=0; i<al2.size(); i++)
s.append(al2.get(i));
}
valueAl2=Integer.parseInt(s.toString(),10);
value=valueAl1+valueAl2;
return Integer.toBinaryString(value)
}
# You can simulate linked lists in Python with tuples.
# You want the least significant bit to be the head of
# the list.
def test():
one = (1, None)
two = (0, (1, None))
three = (1, (1, None))
six = (0, (1, (1, None)))
seven = (1, (1, (1, None)))
thirteen = (1, (0, (1, (1, None))))
assert three == sum(one, two)
assert thirteen == sum(six, seven)
assert 15 == to_decimal(sum(two, sum(six, seven)))
def sum(lst1, lst2, carry=0):
if lst1 is None and lst2 is None:
if carry:
return (1, None)
else:
return None
if lst1 is None:
b1, lst1 = 0, None
else:
b1, lst1 = lst1
if lst2 is None:
b2, lst2 = 0, None
else:
b2, lst2 = lst2
b = b1 + b2 + carry
if b >= 2:
return (b-2, sum(lst1, lst2, 1))
else:
return (b, sum(lst1, lst2, 0))
def to_decimal(lst):
if lst is None:
return 0
b, rest = lst
return b + 2 * to_decimal(rest)
test()
1 ] Reverse the two lists using this function :
struct node* Recurse_binary_Add(struct node* resultlist ,struct node* list1,struct node* list2)
{
struct node* newnode = createNode(0);
if(list1 != NULL || list2 != NULL)
{
if(list1 != NULL && list2 != NULL)
Recurse_binary_Add(newnode,list1->next, list2->next);
if(list1 != NULL)
Recurse_binary_Add(newnode,list1->next,NULL);
else
Recurse_binary_Add(newnode,NULL,list2);
}
2 ] Then find binary addition using this :
struct node* Iterative_binary_Add(struct node** resultlist ,struct node* list1,struct node* list2)
{
int reminder = 0, data = 0;
while(list1 != NULL || list2 != NULL)
{
if(list1 != NULL && list2 != NULL)
{
data = (list1->data + list2->data + reminder ) % 2;
list1 = list1->next;
list2 = list2->next;
}
else
{
if(list1 != NULL)
{
data = (list1->data + reminder ) %2;
list1 = list1->next;
}
else
{
data = (list2->data + reminder ) % 2;
list2 = list2->next;
}
}
reminder = (data == 0 )? 1 : 0 ;
struct node* newnode = createNode(data);
if(*resultlist == NULL)
*resultlist = newnode;
else
{
struct node* tempResultPointer = *resultlist;
while(tempResultPointer->next!=NULL)
tempResultPointer = tempResultPointer->next;
tempResultPointer->next = newnode;
}
}
return *resultlist;
}
Then reverse the result list
In C:
// Represent binary least significant bit first.
typedef struct Node
{
int bit;
struct Node* next;
} Node;
Node* add(Node* l1, Node* l2)
{
Node* ret = NULL;
Node* tail = NULL;
int carry = 0;
while ( l1 || l2 )
{
int r = (l1 ? l1->bit : 0) + (l2 ? l2->bit : 0) + carry;
r = r % 2;
carry = r / 2;
Node* tmp = (Node*)malloc(sizeof(Node));
tmp->bit = r;
if ( tail )
{
tail->next = tmp;
tail = tail->next;
}
else
{
tail = tmp;
ret = tail;
}
if ( l1 )
l1 = l1->next;
if ( l2 )
l2 = l2->next;
}
if ( carry )
{
Node* tmp = (Node*)malloc(sizeof(Node));
tmp->bit = carry;
tail->next = tmp;
tail = tmp;
}
return ret;
}
First you need to reverse the two linked lists, unless the heads that are given point to least significant bits of both numbers. Most likely that is not the case.
After the two linked lists are reversed, we scan both of the heads forward and sum them. We can either get 0 or 1. If it's a 1, it gets carried over, if not you just move forward. If either of the heads becomes null, we stop its traversal and keep traversing the head that is not null. Once we reach the end and we still have a carry-over bit 1, we need to prepend a new head with value 1. Reverse the resulted linked list and return its head.
How about using three stacks? Let's assumed that the linked list sore the binary numbers 1102 as 1->1->1->0->2 then the algorithm are:
1. store linkedlist1 to stack1 and linkedlist2 to stack2, element by element
2. create stack3
3. pop data from stack1 and stac2 at the same time, sum them up and add to stack3, record carry if it happens and use it at the next round.
4. Create linkedlist3 to append element popped out from stack3
This algorithm reply on the FILO characteristic to operate the sum in correct order.
Weakness is the space complexity, the speed is O(n)
ListNode* add(ListNode* head1, ListNode* head)
{
rev(head1);
rev(head2);
ListNode* head(NULL), tail(NULL);
int d, c(0);
while (head1 || head2 || c)
{
d = (head1 ? head1->val : 0) + (head2 ? head2->val : 0) + c;
if (head == NULL)
head = tail = new ListNode(d%2);
else
tail = tail->next = new ListNode(d%2);
c = d/2;
}
rev(head);
return head;
}
Let L1 and L2 are two singly linked list.Let we store sum in L3 an another linked list.
First Step :
Reverse both L1 and L2 by following code
Define curr = head; prev = NULL; while(curr) { next = curr->right; curr->right = prev; prev = curr; } head = prev;second step :
Once that is done start summing both L1 and L2 element wise in following ways
int carry = 0; while(L1->curr && L2->curr) { L3->curr->data = (L1->curr->data + L2->curr->data + carry)%2; carry = (L1->curr->data + L2->curr->data + carry)/2; increment 1 step in each } if(L1->curr) { L3->curr->data = (L1->curr->data + carry)%2; carry = (L1->curr->data + carry)/2; increment 1 step in each } else if(L2->curr) { L3->curr->data = ( L2->curr->data + carry)%2; carry = ( L2->curr->data + carry)/2; increment 1 step in each } if(carry) add extra node in L3 with value 13rd step :
- sonesh February 21, 2013Reverse all