Microsoft Interview Question for Software Engineer in Tests


Country: United States
Interview Type: In-Person




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

intersec(Node *list1, Node *list2)
{
	p = list1;
	q = list2;
	
	Node *intersect = null;
	while(p && q)
	{
		if(p->data == q->data)
		{
			addToList(&intersect, p->data);
			p = p->next;
			q = q->next;
		}
		else if(p->data < q->data)
		{
			p = p->next;
		}
		else
		{
			q = q->next;
		}

- Noobie September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

}

O(n) worst case. No extra space.

- Noobie September 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

is it handling when q? or p has less number of elements ?

- Anonymous September 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If any of the next pointer reaches to null just break it :
if(p->next !=null || q->next !== null)
{

}

- chaz September 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- chaz September 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

u r not checking for duplicates...for eg: 2->2->4 , 2->2->5 are given..then your code returns 2->2

- boss November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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

- amirka September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Anonymous October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- soni vashisht September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Random4 September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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


}

- cqyanbo September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Martin September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anshul September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anshul September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- rawat011 June 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Which team is this for?

- Anonymous April 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

core algo in C:

while (a && b) {
        if (a->val <= b-> val)
            a = a->next;
        if (a->val >= b->val)
            b = b->next;
        if (a->val == b->val)
            add_to_list(list, a->val);
    }

- guest October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if conditions should be like
if (a->val < b-> val) and if (a->val < b-> val). Equal sign should be removed from both if conditions. Also inside last if you need to update both a and b to a->next and b->next

- rawat011 June 11, 2013 | Flag


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