Amazon Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
4
of 4 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

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;

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;

}

{

}
{

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

}

}

{

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

cout << endl;
cout << endl;
}

{
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)
{
temp = cur -> next;
}

} while (flag == 1);

}

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
cur2 = cur2 -> next;
cur1 = cur1 -> next;

}
}
return temp;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

int intersection (char (*a), int na, char (*b), int nb, char (*c))
{
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[] = {"A", "ABC", "CAD"};
char b[] = {"B", "ABC", "CAD", "DAC", "MCF"};
char c;
int nc = intersection (a,3,b,5,c);
cout<< a <<b;
for (int x=0; x<=(nc-1); x++)
{
cout<<c[x];
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

int intersection (char (*a), int na, char (*b), int nb, char (*c))
{
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[] = {"A", "ABC", "CAD"};
char b[] = {"B", "ABC", "CAD", "DAC", "MCF"};
char c;
int nc = intersection (a,3,b,5,c);
cout<< a <<b;
for (int x=0; x<=(nc-1); x++)
{
cout<<c[x];
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

The solutions which I provided will give the common elements in both linked list..

Comment hidden because of low score. Click to expand.
0

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;
}
}}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.