## Amazon Interview Question

Software Engineer / Developers**Country:**United States

// 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];

}

}

By intersection I think he meant ,the common elements of both the lists. Well, thats my take on the question. I would probably use a hashtable, to keep track of all the strings in the first linked list ,then do a search for all the strings in the second list, if found ,I would add to a new list.

@unome, yes that was what the question was.

were a few cases like if the intersection element in the second list was repeated..in that case if an element was repeated then add the string back to the map with a NULL so repeated intersection elements in the second list are not added more than once to the third list.

struct node* getNthLast(struct node* node, int N){

if(node == null) return null;

struct node* ptr1,ptr2;

int i;

ptr1 = ptr2 = node;

for(i=0;i<N && ptr1 != null;i++){

ptr1 = ptr1->next;

}

if(i!=N) return null; //means LL doesn't have N nodes

if(ptr1 == null){ // case when i=N and ptr1 = null

return ptr2;

}

while(ptr1 != null){

ptr1 = ptr1->next;

ptr2 = ptr2->next;

}

return ptr2;

}

}}

Hash all the elements of the first list..

- Sagar March 31, 2012Lookup 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