Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
If any of the next pointer reaches to null just break it :
if(p->next !=null || q->next !== null)
{
}
Just check if any of the next pointer is null. If yes just break loop:
if(p->next !=null || q->next !=null)
{
ur logic
}
else
break;
static LinkedList findMatches(LinkedList l1, LinkedList l2)
{
Node curNode1=l1.head;
Node curNode2=l2.head;
LinkedList newlist = new LinkedList();
while (curNode1 != null && curNode2 !=null)
{
var comp=curNode1.val.CompareTo(curNode2.val);
if (comp==0)
{
newList.AddToEnd(head.val);
curNode2=curNode2.next;
curNode1=curNode1.next;
}
else if (comp=1)
curNode2=curNode2.next;
else if (comp=-1)
curNode1=curNode1.next;
}
return newList;
}
public static node intersection1(node l1, node l2){
node l3=null;
if(l1==null || l2==null ) return null;
while (l1!=null || l2!=null){
if(l1.data<l2.data) l1=l1.next;
if(l2.data<l1.data) l2=l2.next;
if(l1.data==l2.data){
if(l3==null)
l3=new node(l1.data);
else insert(l3,l1.data);
l1=l1.next;
l2=l2.next;
}
}
return l3;
}
public static Node twoListIntersection(ref Node head1, ref Node head2)
{
Node head3=null;
if (head1 == null || head2 == null)
return null;
Hashtable nodesTable = new Hashtable();
if (count(head2) >= count(head1))
{
while (head2 != null)
{
nodesTable[head2.data] = 1;
head2 = head2.next;
if (nodesTable.Contains(head1.data))
{
AppendToHead(ref head3, head1.data);
}
head1 = head1.next;
head2 = head2.next;
if (head1 == null)
return head3;
}
}
else
{
while (head1!= null)
{
nodesTable[head1.data] = 1;
if (nodesTable.Contains(head2.data))
{
AppendToHead(ref head3, head2.data);
}
head1 = head1.next;
head2 = head2.next;
if (head2 == null)
return head3;
}
}
return head3;
}
private static int count(Node head)
{
int count = 0;
while (head != null)
{
head = head.next;
count++;
}
return count;
}
node * intersection_list(node *a, node *b) {
node *head = NULL, *new_node = NULL;
while(a != NULL && b != NULL) {
if(a->data < b->data) {
a = a->next;
} else if(a->data > b->data) {
b = b->next;
} else {
// If equal, add to the new list being created.
new_node = (node *)malloc(sizeof(node));
new_node->data = a->data;
new_node->next = head;
head = new_node;
a = a->next;
b = b->next;
}
}
// If there is need to keep the proper sorting order;
head = reverse_list(head);
return head;
}
#include<stdio.h>
#include<stdlib.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)
{
temp->next=*h; // store the address of the pointer head(second field)
h = &temp; // transfer the address of 'temp' to 'head'
return *h;
}
node* MergePoint(struct node *a, struct node *b)
{
struct node *c = NULL;
// compare items from two arrays
while (a != NULL) {
int tmp = a->data;
while (b != NULL) {
if(b->data == tmp)
{
node* d = (struct node*)calloc(1, sizeof(struct node));;
d->data = b->data;
c = Insert(d, &c);
}
else if(b->data<tmp) {
break;
}
b = b->next;
}
a = a->next;
}
return c;
}
int main()
{
struct node *head = NULL; //empty linked list
int i = 0;
int a = 0;
for (i; i<5; i++) {
struct node* temp = (struct node*)calloc(1, sizeof(struct node));
temp->data = i; // store data(first field)
head = Insert(temp, &head);
}
struct node *head1 = NULL;
i=0;
int j = 1;
for (j; j<6; j++) {
struct node* temp = (struct node*)calloc(1, sizeof(struct node));
temp->data = j+1; // store data(first field)
head1 = Insert(temp, &head1);
}
node* c = MergePoint(head, head1);
while (head != NULL) {
printf("1st array = %d\n",head->data);
head = head->next;
}
while (head1 != NULL) {
printf("2rd array = %d\n",head1->data);
head1 = head1->next;
}
while (c != NULL) {
printf("result = %d\n",c->data);
c = c->next;
}
}
Node* intersection_two_lists(Node* A, Node* B) {
if (!A || !B) return NULL;
Node* head = NULL;
Node* previous = NULL;
while (A && B) {
if (A->val < B->val) A = A->next;
else if (B->val < A->val) B = B->next;
else {
Node* node_copy = new Node(A);
if (!previous) { previous = node_copy; head = node_copy; }
else { previous->next = node_copy; previous = node_copy; }
}
}
return head;
}
struct node* intersection(struct node* head, struct node* head1)
{
struct node *mover1, *mover2,*result=NULL,*p,*mr;
mover1=head;
mover2=head1;
while(mover1!=NULL)
{ mover2=head1;
while(mover2!=NULL)
{
if((mover1->info)==(mover2->info))
{
printf("%d\n",mover1->info);
p=(struct node*)malloc(sizeof(struct node));
p->info=mover1->info;
p->next=NULL;
if(result==NULL)
{
mr=p;
result=mr;
}
else
{
mr->next=p;
mr=p;
//printf("%d",mr->info);
}
}
mover2=mover2->next;
}
mover1=mover1->next;
}
display(result);
}
struct node * sum(struct node*head1,struct node* head2)
{
int a=0,b=0,count=1,sum,no;
struct node* mover1=head1;
struct node* mover2=head2, *result=NULL,*hr;
while(mover1!=NULL)
{
a+=(mover1->info)*count;
count=count*10;
mover1=mover1->next;
}printf("%d ",a);
count=1;
while(mover2!=NULL)
{
b+=(mover2->info)*count;
count=count*10;
mover2=mover2->next;
}
printf("%d ",b);
sum=a+b;
while(sum!=0)
{
no=sum%10;
sum=sum/10;
if(result==NULL)
{printf("hello");
result=insert(no,NULL);
printf(".....%d..",no);
}
else
{
insert(no,result);
}
}
return result;
}
Here is the perl code
##################################################
# name: FindIntersection
# Objective: Find intersection of elements two lists, create
# new list with intersection elements and return it
##################################################
sub FindIntersection {
my ($h1, $h2) = @_;
my $h3;
while( defined $h1 && defined $h2 ) {
if ($h1->{data} < $h2->{data}) {
$h1 = $h1->{_next};
} elsif ($h1->{data} > $h2->{data}) {
$h2 = $h2->{_next};
} else {# found intersection element
_add($h3, $h1->{data});
$h1 = $h1->{_next};
$h2 = $h2->{_next};
}
}
return $h3;
}
- Noobie September 30, 2012