Amazon Interview Question
Software Engineer / DevelopersCountry: 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