Microsoft Citrix System Inc Interview Question
Software Engineer / Developers Software Engineer in Testst = 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.
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.
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;
}
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
I think his code is correct and it does handle duplicates. Maybe you should read the code carefully before commenting.
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
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;
}
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
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
}
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
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];
}
}
}
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;
}
//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
}
//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
}
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;
}
}
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;
}
}
- monika.agarwal712 January 24, 2013