Microsoft Citrix System Inc Interview Question for Software Engineer / Developers Software Engineer in Tests






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

merge(node h1*,node *h2)
{ node *ptr1=h1,*ptr2=h2,*prev1=null,*temp;
   if(h1==null)
         return h2;

   while(*ptr1!=null&&ptr2!=null)
   {
             if(ptr1->data<=ptr2->data)
             {
                      prev1=ptr1;
                      ptr1=ptr1->next;
                      if(ptr1->data==ptr2->data)
                      {       temp=ptr2;
                              ptr2=ptr2->next;
                              free(temp);
                      }
               }
               else
               {
                        temp=ptr2->next;
                        ptr2->next=ptr1;
                        if(prev1==null)
                        {
                                  h1=ptr2;
                        }
                        else
                               prev1->next=ptr2;

                         ptr2=temp;
   }
}
  if(h1==null && h2==null)
      return null; 
    else if(ptr1==null)
         prev1->next=ptr2;
         return h1;
   else if(ptr2==null)
        return h1;

- monika.agarwal712 January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

t = linklist of one sorted list
u = linklist of other sorted list.
r = result link list

for ( t++ and u++)
{if t.data < u.data
r->next = t
r = r->next
if t.data = u.data
r->next = t
r= r->next
if t.data >u.data
r->next = u
r= r->next
}

if any one linklist become empty , put other linklist into result as such.

- sushantmax88 December 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

t = linklist of one sorted list
u = linklist of other sorted list.
r = result link list

for ( t++ and u++)
{if t.data < u.data
r->next = t
r = r->next
if t.data = u.data
r->next = t
r= r->next
if t.data >u.data
r->next = u
r= r->next
}

if any one linklist become empty , put other linklist into result as such.

- sushantmax88 December 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node *merge(node *p,node *q)
{
if(p==NULL) return q;
if(q==NULL) return p;
if(p->data==q->data)
{
p->next=merge(p->next,q->next);
delete q;
return p;
}
if(p->data>q->data)
{
q->next=merge(p,q->next);
return q;
}
p->next=merge(p->next,q);
return p;
}

- um December 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Have you read the Q carefully? It requires us to remove the duplicates also. Your code doesn't (ex. it fails when p={1} & q={1,1}) remove the duplicates. And for god's sake please read the Q carefully before posting codes. You are spamming the forums in this way.

thanks

- Anonymous February 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think his code is correct and it does handle duplicates. Maybe you should read the code carefully before commenting.

- Sushant February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sushant: that code doesn't handle 1,1. I tried it:

#include "stdafx.h"

#include <iostream>
using namespace std;

struct node
{
   int data;
   node * next;
};

node *merge(node *p,node *q)
{
if(p==NULL) return q;
if(q==NULL) return p;
if(p->data==q->data)
{
p->next=merge(p->next,q->next);
delete q;
return p;
}
if(p->data>q->data)
{
q->next=merge(p,q->next);
return q;
}
p->next=merge(p->next,q);
return p;
}


int main ()
{
  node *a = new node(); a->data = 1; a->next = NULL;
  node *b = new node(); b->data = 1; b->next = new node(); b->next->data = 1; b->next->next = NULL;

  node *x = merge(a,b);
  while(x != NULL)
  {
     cout<<x->data<<"->";
     x = x->next;
  }
  cout<<endl;


  return 0;
}

=> output:
1->1

- Soros April 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

merge sort on two lists

- JustEfinGoogleIt December 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Awesome UM..!

- PKT January 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Clever code by UM, it even maybe works - I haven't checked.
However, this is a DUMB solution as it takes linear space due to the recursion.

- Soros April 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node *merge(Node *h1, Node *h2)
{
  Node *head = NULL, *prev = NULL, *curr = NULL;
  Node *c1 = h1, *c2 = h2;
  while (c1 || c2) {
    if (c2 == NULL) {
      curr = c1;
      c1 = c1->next;
    } else if (c1 == NULL) {
      curr = c2;
      c2 = c2->next;
    } else if (c1->value <= c2->value) {
      curr = c1;
      c1 = c1->next;
    } else {
      curr = c2;
      c2 = c2->next;
    }
    if (prev) {
      if (prev->value == curr->value)
        continue;
      else
        prev->next = curr;
    }
    if (head == NULL)
      head = curr;
    prev = curr;
  }
  return head;
}

- leeym April 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect

- Piyush February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node lastNodeAdded = NULL;
list toReturn;
while(!list1.empty() || !list2.empty())
{
   lastlastNode = lastNodeAdded;
   if(list1 != NULL && lastNodeAdded.getValue == list1.getValue()
      while(list1 != NULL && list1.getValue() == lastNodeAdded)
         list1 = list1.getNext();

   if(list1 != NULL && lastNodeAdded.getValue == list2.getValue()
      while(list2 != NULL && list2.getValue() == lastNodeAdded)
         list2 = list2.getNext();

   if(list1 != NULL && list2 != NULL)
   {
      if(list1.getValue() > list2.getValue())
      {
         lastNodeAdded = list2.getValue();
         list2 = list2.getNext();
      }
      else
      {
         lastNodeAdded = list1.getValue();
         list1 = list1.getNext();
      }
   }
   else if(list1 != NULL && list2 == NULL)
   {
      lastNodeAdded = list1;
      list1 = list1.next();
   }
   else if(list1 == NULL && list2 != NULL)
   {
      lastNodeAdded = list2;
      list2 = list2.next();
   }
   else
   {
      continue;
   }
   lastlastNode.setNext(lastNodeAdded);
   toReturn.add(lastNodeAdded);
}

Time O(N+M), Space O(N+M) the list we return. I wrote the code on notepad, there maybe some minor issue with the function

- Mat April 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pseudo code is as follows:

int mergeList(struct node* list1 , struct node* list2)
{
if (list1 and list2 are null) return failure;
else if (one list of the two list is null) return success;
else
{
while (list1) get the max_number;
while (list2->data <= max_number) get the last pointer in list2 say prev
while (prev is not NULL meaning end of second list)
create new node* add that to last element of list1 and increase both of the list element


}

return success

}

- jay May 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Take each node from second list and keep it in the first list by just modifying the pointers - O(n^2) time, no space required
2. Just append the second list to the last node of the first list and do a comparison sort to modify the values within each node - O(nlogn) time, no space
3. Extra list and go over each list linearly to move node the new list - O(list1.length + list2.length) time and same space complexity as well

- SS June 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, in the 3rd point above, no space is required if we just move the nodes instead of creating new ones

- SS June 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

List<int> RemoveDuplicatesAndMerge(int[] A, int[] B)
{
    return new List<int>(RemoveDuplicatesAndMergeInternal(A, B));
}

IEnumerable<int> RemoveDuplicatesAndMergeInternal(int[] A, int[] B)
{
   int a = 0;
   int b = 0;
   int last;

   while ((a < A.length) && (b < B.Length))
   {        
        if (A[a] < B[b])
        {
            if (A[a] != last)
            {
                last = A[a];
                yield return A[a];
            }
            a++;
        }
        else if (B[b] < A[a])
        {
            if (B[b] != last)
            {
                 last = B[b];
                 yield return B[b];            
            }
            b++;
        }
        else    // A[a] == B[b]
        {
            a++;
            b++;
        }
   }

   for (;a < A.length;a++)
   {
        if (last != A[a])
        {
            yield return A[a];
        }
   }

   for (;b < B.length;b++)
   {
        if (last != B[b])
        {
            yield return B[b];
        }
   }
}

- Ashish Kaila June 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry missed that they are linked lists. However translation should be trivial.

- Ashish Kaila June 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Rectifying UM's solution:

#include "stdio.h"


#include <iostream>
using namespace std;


struct node
{
int data;
node * next;
};

node *merge(node *p,node *q)
{
if(p!=NULL){
while(p->next != NULL && (p->data==p->next->data)){
p=p->next;
}
}
if(q!=NULL){
while(q->next != NULL && (q->data==q->next->data)){
q=q->next;
}
}
if(p==NULL) {
// q=sort(q);
return q;
}
if(q==NULL) {
//p=sort(p);
return p;
}
if(p->data==q->data){
p->next=merge(p->next,q->next);
delete q;
return p;
}
if(p->data>q->data)
{
q->next=merge(p,q->next);
return q;
}
p->next=merge(p->next,q);
return p;
}


int main ()
{
node *a = new node(); a->data = 1; a->next = NULL;
node *b = new node(); b->data = 1; b->next = NULL;


node *x = merge(a,b);
while(x != NULL)
{
cout<<x->data<<"->";
x = x->next;
}
cout<<endl;


return 0;
}

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

Hi Folks,

If we do not have any space constraints then what about BST :) and get sorted list by inorder traversal.prepare one BST by taking elements from both the lists and BST won't be having any duplicate element.

- Rex July 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//h1 = head of first link list
//h2 = head of second link list

LIST *merge_linklist(LIST *h1, LIST* h2){

LIST* h3 == NULL; // head of the merged list
LIST *trav,*node; //temporary pointer
if(h1==NULL && h2==NULL)
return NULL;//return NULL if both list are empty
if(h1==NULL)
return h2;
else if(h2==NULL)
return h1

while (h1!=NULL && h2!=NULL) {
//check in the next element is same
//as the previos one
if (h1->value = h1->next->value) {
h1=h1->next;
continue; //ignore the element
}else if (h2->value = h2->next->value) {
h2=h2->next;
continue; //ignore the element
}
if(h1->value < h2->value){
//create a node for final merge list
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h1->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h1->value;
trav->next = node;
trav = trav->next;
node->next = NULL;

}
h1= h1->next;



}else if(h1->value > h2->value){
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h2->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h2->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h2=h2->next; //move the pointer of the list having the smaller value
}else{// when h1 and h2 are equal

if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h2->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h1->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}

h1=h1->next;
h2=h2->next;
}
}//while loop ends
//trav points to tail of the merged list h3
//now we need to attach the tail of h3 to the left over element of the longer list
(h1==NULL) ? (trav->next=h2->next):(trav->next=h1->next);
return h3; // return the head of the merged list
}

- vivekh February 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//h1 = head of first link list
//h2 = head of second link list

LIST *merge_linklist(LIST *h1, LIST* h2){ 

    LIST* h3 == NULL; // head of the merged list
    LIST *trav,*node; //temporary pointer
    if(h1==NULL && h2==NULL) 
        return NULL;//return NULL if both list are empty
    if(h1==NULL)
        return h2;
    else if(h2==NULL)
        return h1

            while (h1!=NULL && h2!=NULL) {
                //check in the next element is same 
                //as the previos one  
                if (h1->value = h1->next->value)  {
                    h1=h1->next;
                    continue; //ignore the element
                }else if (h2->value = h2->next->value)  {
                    h2=h2->next;
                    continue; //ignore the element
                }
                if(h1->value < h2->value){
                    //create a node for final merge list
                    if(h3 == NULL){
                        h3 = (LIST*) malloc(sizeof(LIST));
                        h3->value = h1->value // store the smaller of h1 and h2 into h3
                            h3->next = NULL;
                        trav = h3;
                    }else{
                        node = (LIST*) malloc(sizeof(LIST));
                        node->value = h1->value;
                        trav->next = node;
                        trav = trav->next;
                        node->next = NULL;

                    }
                    h1= h1->next;



                }else if(h1->value > h2->value){
                    if(h3 == NULL){
                        h3 = (LIST*) malloc(sizeof(LIST));
                        h3->value = h2->value // store the smaller of h1 and h2 into h3
                            h3->next = NULL;
                        trav = h3;
                    }else{
                        node = (LIST*) malloc(sizeof(LIST));
                        node->value = h2->value;
                        trav->next = node;
                        trav = trav->next;
                        node->next = NULL;
                    }
                    h2=h2->next; //move the pointer of the list having the smaller value
                }else{// when h1 and h2 are equal

                    if(h3 == NULL){
                        h3 = (LIST*) malloc(sizeof(LIST));
                        h3->value = h2->value // store the either h1 or h2 into h3
                            h3->next = NULL;
                        trav = h3;
                    }else{
                        node = (LIST*) malloc(sizeof(LIST));
                        node->value = h1->value;
                        trav->next = node;
                        trav = trav->next;
                        node->next = NULL;
                    }

                    h1=h1->next;
                    h2=h2->next;
                }
            }//while loop ends
    //trav points to tail of the merged list h3
    //now we need to attach the tail of h3 to the left over element of the longer list
    (h1==NULL) ? (trav->next=h2->next):(trav->next=h1->next);
    return h3; // return the head of the merged list
}

- vivekh February 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. merge two lists
2. Remove dupicates in merged list

- venkatesh December 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

keep track of maximum element inserted in resultant linked list so far it and the rest is simple

- nit.kmr0245 July 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MergeList {
public Node merge(Node n1,Node n2){
Node current1=n1;
Node current2=n2;
Node start;
if(current1.data>= current2.data){
start = new Node(n1.data);
current1= current1.next;
while(current1!=null){
if(current1.data==n1.data){
current1= current1.next;
}
}
while(current2!=null&& current2.data==n1.data){
current2= current2.next;
}
start.next= merge(current1,current2);
}

else{
start = new Node(current2.data);
current2= current2.next;
while(current2!=null){
if(current2.data==n2.data){
current2= current2.next;
}
}
while(current1!=null&& current1.data==n2.data){
current1= current1.next;
}
start.next= merge(current1,current2);
}

return start;
}
}

- Sagar Reddy July 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package linkedList;

public class MergeList {
public Node merge(Node n1,Node n2){
Node current1=n1;
Node current2=n2;
Node start;
if(current1.data>= current2.data){
start = new Node(n1.data);
current1= current1.next;
while(current1!=null){
if(current1.data==n1.data){
current1= current1.next;
}
}
while(current2!=null&& current2.data==n1.data){
current2= current2.next;
}
start.next= merge(current1,current2);
}

else{
start = new Node(current2.data);
current2= current2.next;
while(current2!=null){
if(current2.data==n2.data){
current2= current2.next;
}
}
while(current1!=null&& current1.data==n2.data){
current1= current1.next;
}
start.next= merge(current1,current2);
}

return start;
}
}

- Sagar Reddy July 05, 2015 | Flag Reply


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