Amazon.com
www.amazon.com Seattle, WA 5000+ Employees

# Interview Question for Software Design Engineer In Test at Amazon.com: Sep 3, 2010

## Write a function to find the node where two linked lists meet.

Yes | No
Inappropriate?

0 of 1 people found this helpful

Nov 28, 2010
public static void main(String[] args) {
List<Integer> L1 = Arrays.asList(1,2,5,7,9,10,12,18,3);
List<Integer> L2 = Arrays.asList(2,3,4,8,9,9,10,11,12,18);

System.out.println("L1 : " + list1);
System.out.println("L2 : " + list2);
ArrayList<Integer> result = new ArrayList<Integer>();
System.out.println("two linked lists meet: " + findCommon(list1, list2,result));
}
{
if (list1.isEmpty()) return result;
int pop = list1.pop();
return findCommon(list1, list2, result);
}
Yes | No
Inappropriate?

Sep 26, 2011
// solution in C++
#include <iostream>
#include <map>

using namespace std;

// simple Node class
class Node
{
public:
Node(int v) : val(v), next(NULL) {}
int val;
Node* next;
};

// function to find intersection Node
{
// interate through first list and populate map
map<Node*, int> nodeMap;
{
}
// interate through second list and try to find in map
{
{
}
}
return NULL;
}

// test code (happy path only)
int main()
{
// linked list 1 values = 1,2,3,4,5,6
Node* n12 = new Node(2);
Node* n13 = new Node(3);
Node* n14 = new Node(4);
Node* n15 = new Node(5);
Node* n16 = new Node(6);
n12->next = n13;
n13->next = n14;
n14->next = n15;
n15->next = n16;

// linked list 2 values = 11,12,13,5,6
Node* n22 = new Node(12);
Node* n23 = new Node(13);
n22->next = n23;
n23->next = n15;

{
cout << head1->val << " ";
}
cout << endl;

{
cout << head2->val << " ";
}
cout << endl;
Yes | No
Inappropriate?

Sep 26, 2011
Previous answer got truncated. Here's the last of the test code starting at the function call.

{
cout << head1->val << " ";
}
cout << endl;

{
cout << head2->val << " ";
}
cout << endl;

cout << "lists intersect at " << intersection->val << endl;

cout << "\n\n\nPress Enter to quit. ";
cin.ignore();
return 0;
}
Yes | No
Inappropriate?