CareerCup

Hash all the elements of the first list..
Lookup for the every element of second list in the created hash. If you find a collision, return the
element..
Complexity would be o(m+n).. m = length of 1st list , n = length of 2nd list

// This program will show the intersection of two linked list.. i.e. common strings in both linked list..
#include <iostream>
#include <conio.h>

using namespace std;

struct Node
{
char *data;
Node * next;
};

void addFirst (Node **head, char* data);
void display (Node *head);
void addLast (Node *head, char * data);
void addFirst (Node **head, char * data);
void display (Node *head);
Node *reverse (Node **head);
Node *sortList ( Node **head);
Node *intersection( Node* listOne, Node* listTwo);

int main()
{
Node *list1 = new Node();
Node *list2 = new Node();
Node *intersectionList = new Node();

list1 -> data = "abc";
list1 -> next = NULL;

list2 -> data = "bcd";
list2 -> next = NULL;

addLast(list1, "cde");
addLast(list1, "def");
addLast(list1, "efg");
addLast(list1, "hij");
addLast(list1, "ghi");
addLast(list1, "jkl");


addLast(list2, "cde");
addLast(list2, "jhg");
addLast(list2, "hij");
addLast(list2, "cvb");
addLast(list2, "hgf");
addLast(list2, "rew");
addLast(list2, "ghi");
addLast(list2, "asd");

sortList(&list1);
cout << "List 1 After Sorting: " << endl;
display (list1);

sortList(&list2);
cout << "List 2 After Sorting: " << endl;
display (list2);

intersectionList = intersection( list1, list2);
cout << "Intersection List: " << endl;
display (intersectionList);

delete list1;
delete list2;


}

void addFirst (Node **head, char * data)
{

Node *newHead = new Node();

newHead -> data = data;
newHead -> next = *head;
*head = newHead;


}
void addLast (Node *head, char * data)
{
Node *cur = head;
Node *newHead = new Node();
newHead -> data = data;

while(cur)
{
if(cur -> next == NULL)
{
cur -> next = newHead;
newHead -> next = NULL;
return;
}
cur = cur -> next;

}

}

void display (Node *head)
{
Node *cur = head;

while(cur)
{
if ( cur -> next == NULL)
{
cout << cur -> data;
}
else
cout << cur -> data << ",";
cur = cur -> next;
}

cout << endl;
cout << endl;
}


Node *sortList (Node **head)
{
Node *cur = *head;
Node *temp = new Node();
Node *temp1 = new Node();


int flag = 0;
temp = cur -> next;

do{
flag = 0;
while(cur -> next != NULL)
{
if (cur -> data > temp ->data )
{
temp1 -> data = cur -> data;
cur -> data = temp -> data;
temp -> data = temp1 -> data;
cur = cur -> next;

if (cur -> next != NULL)
{
temp = cur -> next;

}
flag = 1;
}
else //if(cur -> next != NULL)
{

if (cur -> next != NULL)
cur = cur -> next;
if (cur -> next != NULL)
temp = cur -> next;
}
}

if(temp == cur)
{
cur = *head;
temp = cur -> next;
}



} while (flag == 1);

//cur = *head;

return *head;

}

Node *intersection( Node* listOne, Node* listTwo)
{
Node *cur1 = listOne;
Node *cur2 = listTwo;
Node *temp = new Node();
int pos = 0;

while(cur1 || cur2)
{
if( cur1 -> data > cur2 ->data )
if(cur2 -> next == NULL)
return temp;
else
cur2 = cur2 -> next;

if( cur1 -> data < cur2 ->data )
if(cur1 -> next == NULL)
return temp;
else
cur1 = cur1 -> next;

if( cur1 -> data == cur2 ->data )
{
if(pos == 0)
{
temp -> data = cur2 -> data;
pos++;
}
else
addFirst(&temp, cur2 -> data);
cur2 = cur2 -> next;
cur1 = cur1 -> next;

}
}
return temp;
}

int searchElement(char t[], char (*b)[10], int nb)
{
int x;
for (x=0; x<nb; x++)
{
if (!strcmp(t, b[x]))
return 1;
}
return 0;
}

int intersection (char (*a)[10], int na, char (*b)[10], int nb, char (*c)[10])
{
int x,k=0;
for (x=0; x<na; x++)
{
if( searchElement(a[x], b, nb) )
{
strcpy(c[k], a[x]);
k++;
}
}
return k;
}

void main()
{
clrscr();
char a[][10] = {"A", "ABC", "CAD"};
char b[][10] = {"B", "ABC", "CAD", "DAC", "MCF"};
char c[30][10];
int nc = intersection (a,3,b,5,c);
cout<< a <<b;
for (int x=0; x<=(nc-1); x++)
{
cout<<c[x];
}
}

int searchElement(char t[], char (*b)[10], int nb)
{
int x;
for (x=0; x<nb; x++)
{
if (!strcmp(t, b[x]))
return 1;
}
return 0;
}

int intersection (char (*a)[10], int na, char (*b)[10], int nb, char (*c)[10])
{
int x,k=0;
for (x=0; x<na; x++)
{
if( searchElement(a[x], b, nb) )
{
strcpy(c[k], a[x]);
k++;
}
}
return k;
}

void main()
{
clrscr();
char a[][10] = {"A", "ABC", "CAD"};
char b[][10] = {"B", "ABC", "CAD", "DAC", "MCF"};
char c[30][10];
int nc = intersection (a,3,b,5,c);
cout<< a <<b;
for (int x=0; x<=(nc-1); x++)
{
cout<<c[x];
}
}

i think the solution is to sort the list with the larger number of strings.

and then do binary search in it using the strings in the other list.

won't this take o(n log m) solution?

Considering by lists, you mean linked lists,

1) Linear scan through both the lists to determine their length.
2) The difference of the lengths determines by how much the longer list is longer than the shorter list and more specifically how many extra nodes are in the front of the bigger list as compared to the start of the smaller list upto the intersection point.

3) Traverse through the larger list for a distance = difference calculated in step 2.
4) Now traverse both lists together to find at which point they have the same node.

Complexity= O(n)