Microsoft Interview Question Software Engineer / Developers
Java code:
Iterator<Integer> list1_iterator = List1.Iterator();
Iterator<Integer> list2_iterator = List2.Iterator();
while(list1_iterator.hasNext())
{
int key = list1_iterator.next();
while(list2_iterator.hasNext())
{
if (key<list2_iterator.next())
list2_iterator.next();
else
// insert key at this position in List2 and break;
}
}
<pre lang="c++" line="1" title="CodeMonkey22137" class="run-this">#include <iostream>
using namespace std;
struct Node {
int val;
Node * next;
Node(int vals[], int size, int offset=0) {
val = vals[offset];
offset++;
if(offset<size) {
next = new Node(vals, size, offset);
}
}
void print() {
cout << val;
if(next!=NULL) {
cout << " ";
next->print();
}
}
};
typedef Node LinkedList;
void merge(LinkedList& a, LinkedList& b) {
Node * pa = &a;
Node * pb = &b;
while(true) {
if(pb->val < pa->val) { // swap
Node temp = *pa;
*pa = *pb;
*pb = temp;
}
if(pa->next!=NULL)
pa=pa->next;
else
{
pa->next = pb;
break;
}
}
}
int main() {
int a_vals[] = {2,3,6,8};
int b_vals[] = {1,4,5,7};
LinkedList a(a_vals, sizeof(a_vals)/sizeof(int));
LinkedList b(b_vals, sizeof(b_vals)/sizeof(int));
merge(a, b);
a.print(); // a contains merged list, b is irrelevant
return 0;
}</pre><pre title="CodeMonkey22137" input="yes">
</pre>
Here is a C# Solution using LinkedList from Generic Collections
static void Main(string[] args)
{
LinkedList<int> first = new LinkedList<int>();
first.AddLast(1);
first.AddLast(2);
first.AddLast(5);
first.AddLast(8);
first.AddLast(12);
first.AddLast(16);
first.AddLast(17);
first.AddLast(22);
LinkedList<int> second = new LinkedList<int>();
second.AddLast(2);
second.AddLast(2);
second.AddLast(3);
second.AddLast(4);
second.AddLast(7);
second.AddLast(11);
second.AddLast(14);
second.AddLast(33);
LinkedList<int> mergedList = MergeSortedLinkedList(first, second);
PrintLinkedList(mergedList);
}
static LinkedList<int> MergeSortedLinkedList(LinkedList<int> FirstList, LinkedList<int> SecondList)
{
if (SecondList.First.Value >= FirstList.Last.Value)
{
FirstList.AddLast(SecondList.First);
return FirstList;
}
if (FirstList.First.Value >= SecondList.Last.Value)
{
SecondList.AddLast(FirstList.First);
return SecondList;
}
LinkedListNode<int> currentToInsert = SecondList.First;
LinkedListNode<int> lastReachedNode = FirstList.First;
while (currentToInsert != null)
{
while (lastReachedNode.Next != null && lastReachedNode.Value < currentToInsert.Value)
{
lastReachedNode = lastReachedNode.Next;
}
if (lastReachedNode.Next == null)
FirstList.AddAfter(lastReachedNode, currentToInsert.Value);
else
FirstList.AddBefore(lastReachedNode, currentToInsert.Value);
currentToInsert = currentToInsert.Next;
}
return FirstList;
}
static void PrintLinkedList(LinkedList<int> ListToPrint)
{
LinkedListNode<int> toPrint = ListToPrint.First;
while (toPrint != null)
{
Console.WriteLine(toPrint.Value);
toPrint = toPrint.Next;
}
}
without creating new nodes
public static LinkedList<T> MergeTwoSortedLists(LinkedList<T> a, LinkedList<T> b)
{
Node<T> startA = a.HeadNode;
Node<T> startB = b.HeadNode;
LinkedList<T> newList = null;
IComparer<T> comparer = Comparer<T>.Default; // used to compare node values when percolating down the tree
if (startA == null) return b;
if (startB == null) return a;
if (comparer.Compare(a.LastNode.Data,b.LastNode.Data) > 0)
{
a.LastNode.Next = b.HeadNode;
a.LastNode = b.LastNode;
return a;
}
if (comparer.Compare(a.LastNode.Data, b.LastNode.Data) < 0)
{
b.LastNode.Next = a.HeadNode;
b.LastNode = a.LastNode;
return b;
}
while (startA != null && startB != null)
{
if (comparer.Compare(startA.Data, startB.Data) < 0)
{
while (startA.Next != null && comparer.Compare(startA.Next.Data, startB.Data) < 0)
{
startA = startA.Next;
}
Node<T> temp = startA.Next;
startA.Next = startB;
startA = temp;
if (newList == null)
{
newList = a;
}
}
else if (comparer.Compare(startA.Data, startB.Data) > 0)
{
while (startB.Next != null && comparer.Compare(startB.Next.Data, startA.Data) < 0)
{
startB = startB.Next;
}
Node<T> temp = startB.Next;
startB.Next = startA;
startB = temp;
if (newList == null)
{
newList = b;
}
}
else
{
startA = startA.Next;
}
}
if (startA == null)
{
}
return newList;
}
<pre lang="c++" line="1" title="CodeMonkey1685" class="run-this">#include<iostream>
struct Node {
Node(int data): value(data),next(NULL) {}
Node* next;
int value;
};
class MergeList {
public:
MergeList():firstList(NULL),secondList(NULL)
{
}
void createList(Node* first, Node* second);
Node* mergeTwoList(Node* first, Node* second);
private:
Node* firstList;
Node* secondList;
};
void
MergeList::createList(Node* first, Node* second)
{
int list1;
int list2;
cout<<"Enter element count for first list"<<endl;
cin>>list1;
for (int i =0; i<list1 ; i++) {
cout<<"Enter data "<<i<<endl;
int data;
cin>>data;
Node* newNode = new Node(data);
if (first == NULL) {
first = newNode;
firstList = first;
} else {
first->next = newNode;
first = first->next;
}
}
cout<<"Enter element count for second list"<<endl;
cin>>list2;
for (int i =0; i<list2 ; i++) {
cout<<"Enter data "<<i<<endl;
int data;
cin>>data;
Node* newNode = new Node(data);
if (second == NULL) {
second = newNode;
secondList = second;
} else {
second->next = newNode;
second = second->next;
}
}
cout<<"first list = ";
first = firstList;
while (first != NULL) {
cout<<first->value<<"->";
first = first->next;
}
cout<<endl;
cout<<"second list = ";
second = secondList;
while (second != NULL) {
cout<<second->value<<"->";
second = second->next;
}
cout<<endl;
}
Node*
MergeList::mergeTwoList(Node* first, Node* second)
{
first = firstList;
second = secondList;
int i =0;
Node* prev = NULL;
while ((first != NULL) && (second != NULL)) {
if (first->value > second->value) {
Node* temp = second->next;
second->next = first;
if (prev) {
prev->next = second;
} else {
firstList = second;
}
prev = second;
second = temp;
} else {
prev = first;
first = first->next;
}
}
if (first) {
first->next = NULL;
} else {
if (prev) {
prev->next = second;
} else {
firstList = second;
}
}
first = firstList;
second = secondList;
return firstList;
}
void
main()
{
MergeList* mergeList = new MergeList();
Node* first = NULL;
Node* second = NULL;
mergeList->createList(first, second);
Node* merList = mergeList->mergeTwoList(first, second);
cout<<"After merging first list = ";
while (merList != NULL) {
cout<<merList->value<<"->";
merList = merList->next;
}
cout<<endl;
}
</pre><pre title="CodeMonkey1685" input="yes">Following code merge the two sorted list. I have run this code on gcc.
#include<iostream>
struct Node {
Node(int data): value(data),next(NULL) {}
Node* next;
int value;
};
class MergeList {
public:
MergeList():firstList(NULL),secondList(NULL)
{
}
void createList(Node* first, Node* second);
Node* mergeTwoList(Node* first, Node* second);
private:
Node* firstList;
Node* secondList;
};
void
MergeList::createList(Node* first, Node* second)
{
int list1;
int list2;
cout<<"Enter element count for first list"<<endl;
cin>>list1;
for (int i =0; i<list1 ; i++) {
cout<<"Enter data "<<i<<endl;
int data;
cin>>data;
Node* newNode = new Node(data);
if (first == NULL) {
first = newNode;
firstList = first;
} else {
first->next = newNode;
first = first->next;
}
}
cout<<"Enter element count for second list"<<endl;
cin>>list2;
for (int i =0; i<list2 ; i++) {
cout<<"Enter data "<<i<<endl;
int data;
cin>>data;
Node* newNode = new Node(data);
if (second == NULL) {
second = newNode;
secondList = second;
} else {
second->next = newNode;
second = second->next;
}
}
cout<<"first list = ";
first = firstList;
while (first != NULL) {
cout<<first->value<<"->";
first = first->next;
}
cout<<endl;
cout<<"second list = ";
second = secondList;
while (second != NULL) {
cout<<second->value<<"->";
second = second->next;
}
cout<<endl;
}
Node*
MergeList::mergeTwoList(Node* first, Node* second)
{
first = firstList;
second = secondList;
int i =0;
Node* prev = NULL;
while ((first != NULL) && (second != NULL)) {
if (first->value > second->value) {
Node* temp = second->next;
second->next = first;
if (prev) {
prev->next = second;
} else {
firstList = second;
}
prev = second;
second = temp;
} else {
prev = first;
first = first->next;
}
}
if (first) {
first->next = NULL;
} else {
if (prev) {
prev->next = second;
} else {
firstList = second;
}
}
first = firstList;
second = secondList;
return firstList;
}
void
main()
{
MergeList* mergeList = new MergeList();
Node* first = NULL;
Node* second = NULL;
mergeList->createList(first, second);
Node* merList = mergeList->mergeTwoList(first, second);
cout<<"After merging first list = ";
while (merList != NULL) {
cout<<merList->value<<"->";
merList = merList->next;
}
cout<<endl;
}
</pre>
/* C implementation
Merge two sorted linked list */
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node * next;
}NODE;
merge(NODE **START1,NODE **START2)
{
NODE *p1,*ptr,*prev,*tp;
p1=*START1;
while(p1!=NULL)
{
prev=NULL;
ptr=*START2;
while(ptr!=NULL)
{
if(p1->data<ptr->data)
break;
else
{
prev=ptr;
ptr=ptr->next;
}
}
if(prev==NULL)
*START2=p1;
else
prev->next=p1;
tp=p1;
p1=p1->next;
tp->next=ptr;
}
}
insert(NODE **START,int value)
{
NODE *ptr,*p,*prev;
prev=NULL;
p=(NODE *)malloc(sizeof(NODE));
p->data=value;
ptr=*START;
while(ptr!=NULL)
{
if(value<ptr->data)
break;
else
{
prev=ptr;
ptr=ptr->next;
}
}
if(prev==NULL)
*START=p;
else
prev->next=p;
p->next=ptr;
}
display(NODE *START)
{
if(START==NULL)
{
printf("The list is empty");
}
else
while(START!=NULL)
{
printf("%d\n",START->data);
START=START->next;
}
}
int main()
{
int n1,n2,i,value1,value2;
NODE *p1,*p2;
p1=p2=NULL;
printf("Enter the number of elements for List1:\n");
scanf("%d",&n1);
for(i=0;i<n1;i++)
{
scanf("%d",&value1);
insert(&p1,value1);
}
printf("The sorted list1 is:\n");
display(p1);
printf("Enter the number of elements for List2:\n");
scanf("%d",&n2);
for(i=0;i<n2;i++)
{
scanf("%d",&value2);
insert(&p2,value2);
}
printf("The sprted list2 is:\n");
display(p2);
merge(&p1,&p2);
printf("The merged linked list is:");
display(p2);
return(0);
}
Posting millions of lines of code helps no one.
You are only satisfying yourselves
Code is for the computers, algorithms are for the humans ((:
I would like to put my alg here but in such a messy topic, no one can find my post so im skipping..
Okay, here is the algotithm:
1). we need to deside which one will be destination list.
Compare the 1st elements in 2 lists. The destination list will be the one with smaller 1st element:
It 1st elements are the same, we assume the first list will be the desination.
1->2->5->8 (dest)
3->4->7 (source)
1->2->8->10 (dest)
1->3->5->7->11 (source)
2->5->7->8 (source)
1->3->9->10 (dest)
2). if dest->next==NULL - insert the rest of the source into destination and quit.
3). if source->next==NULL - quit.
4). if sourcenode==destnode or sourcenode==destnode->next - move to the next souce node.
5). if destnode < sourcenode < destnode->next : insert source node between them, move to the next source node.
6). if sourcenode > destnode->next : move to the next destination node.
here is a simple case I could think of
head1 //list1
head2 // list2
ptr = head1;
while(ptr) //fetch one ptr and insert it into the second linked list
{ // such that the second linked list remains sorted
insert(head2, ptr);
ptr = ptr->nxt;
}
//insert code
insert(head2, ptr)
{
define ptr2;
define prev;
for(ptr2 = head2; ptr2->nxt; )
{
prev = ptr2;
if(ptr2->data > ptr->data)
break;
}
ptr->nxt= prev->nxt;
prev->nxt = ptr;
}
no extra list for merging, it means that every time we just select a unprocessed item from LIST1 and find a appropriate place in LIST2 to insert,I think the key is that we need not to traverse the whole LIST2 each time, just start after the LIST1 item just inserted.
- Anonymous August 30, 2010Node * mergeList(Node *list1, Node *list2)
{
assert(list1 != NULL && list2 != NULL);
Node *p1 = list1;
Node *p2 = list2;
Node *prev = p2;
Node *tmp = NULL;
while(p1 !=NULL)
{
while(p1 != NULL && p1->data >= p2->data)
{
if(prev == p2)
{
p2 = p2->next;
}
else
{
prev = p2;
p2 = p2->next;
}
}
if(p1 != NULL)
{
tmp = p1->next;
if(prev->data >= p1->data)
{
p1->next = p2;
}
else
{
p1->next = p2;
prev->next = p1;
}
prev = p1; // This is the key The item to be inserted can't be smaller than p1
p1 = tmp;
}
}
}