Amazon Interview Question
SDE1sTeam: Hyderabad
Country: India
Interview Type: Phone Interview
/*
Given n (of size m) Linked lists
Print all set(head of linked list) of link list that intersect with each other.
e.g.
1-->2-->3-->4-->5
6-->7-->8-->4-->5
8->9->10->11->12
13->14->15->12
16->17->18
1 6
8 13
16
*/
#include<iostream>
#include<stack>
using namespace std;
class list
{
public:
int data;
list* next;
list(int data)
{
this->data = data;
next = NULL;
}
};
void displayAll(class list* heads[], int num)
{
class list* temp;
for(int i=0;i<num;i++)
{
temp = heads[i];
while(temp)
{
cout<<" "<<temp->data;
temp = temp->next;
}
cout<<endl;
}
}
void getHeadThatIntersect(class list* heads[], int num)
{
stack<list*> st[num];
for(int i=0;i<num;i++)
{
while(heads[i])
{
//cout<<" spot #"<<endl;
st[i].push(heads[i]);
heads[i] = heads[i]->next;
}
}
//cout<<" spot 1"<<endl;
for(int i=0;i<num;i++)
{
if(st[i].empty())
{
// cout<<" spot 2"<<endl;
continue;
}
else
{
list* temp = st[i].top();
// cout<<" spot 3 "<<temp->data<<endl;
for(int j = i+1;j<num;j++)
{
if(st[j].empty())
continue;
if(st[i].top() == st[j].top())
{
while(st[j].size() != 1)
st[j].pop();
cout<<" "<<((st[j].top())->data)<<" ";
st[j].pop();
}
if(j == num-1)
{
while(st[i].size() != 1)
st[i].pop();
cout<<" "<<((st[i].top())->data)<<" ";
st[i].pop();
}
}
cout<<endl;
}
}
}
int main()
{
// int num;
// cout<<" Enter the number of list :- ";
// cin>>num;
/************************************************/
//First List
list* head1 = new list(1);
head1->next = new list(2);
head1->next->next = new list(3);
head1->next->next->next = new list(4);
head1->next->next->next->next = new list(5);
//Second List
list* head2 = new list(6);
head2->next = new list(7);
head2->next->next = new list(8);
head2->next->next->next = head1->next->next->next;
//Third List
list* head3 = new list(8);
head3->next = new list(9);
head3->next->next = new list(10);
head3->next->next->next = new list(11);
head3->next->next->next->next = new list(12);
//Fourth List
list* head4 = new list(13);
head4->next = new list(14);
head4->next->next = new list(15);
head4->next->next->next = head3->next->next->next->next;
//Fifth List
list* head5 = new list(16);
head5->next = new list(17);
head5->next->next = new list(18);
/************************************************/
class list* heads[5] = {head1, head2, head3, head4, head5};
displayAll(heads, 5);
cout<<endl<<endl;
getHeadThatIntersect(heads, 5);
system("PAUSE");
return 0;
}
This can be done in roughly O(nm) complexity and O(nm) memory where n is the number of elements that are in all lists and m is the number of lists
Create a Set Union to track the Intersections of lists
Use a HashMap to map integers to their set
public static void printIntersections(LinkedList<Integer> lists){
HashMap<Integer,Integer> setUnionMap = new HashMap<Integer,Integer>();
HashMap<Integer,Integer> elementMembershipMap = new HashMap<Integer,Integer>();
//attach all the integers together and build the set union list up
for(LinkedList<Integer> list : lists){
Iterator<Integer> iterator = list.iterator();
if(!interator.hasNext()){
continue;
}
Integer name = iterator.next();
setUnionMap.put(name, null);
while(iterator.hasNext()){
Integer element = iterator.next();
Integer parent = elementMembershipMap.get(element);
if(parent == null){
elementMembershipMap.put(element, name);
}
else{
parent = getParent(parent, setUnionMap);
setUnionMap.put(name, parent);
}
}
}
//invert the set union to construct collections of list names
HashMap<Integer, Collection<Integer>> groupMembershipMap = new HashMap<Integer, Collection<Integer>>();
for(Integer setName : setUnionMap.keySet()){
Integer parent = getParent(setName, setUnionMap);
if(parent == null){
ArrayList<Integer> col = new ArrayList<Integer>();
col.add(setName);
groupMembershipMap.put(setName, col);
}
else{
Collection<Integer> col = groupMembershipMap.get(parent);
col.add(setName);
}
}
//output the list names
for(Collection<Integer> valueSet : groupMembershipMap.getValues()){
StringBuilder line = new StringBuilder();
Iterator<Integer> iterator = valueSet.iterator();
while(iterator.hasNext()){
if(line.length() > 0){
line.append(", ");
}
line.append(String.parseInt(iterator.next()));
}
System.out.println(line.toString());
}
}
private static Integer getParent(Integer lookUp, HashMap<Integer,Integer> unionMap){
Integer parentName = unionMap.get(lookUp);
if(parentName == null){
return lookUp;
}
Integer root = getParent(parentName, unionMap);
if(root != parentName){
unionMap.put(lookUp, root);
}
return root;
}
O(nm) time complexity and I think O(n) space
public class IntersectFinder
{
public ArrayList<ArrayList<Integer>> findIntersect(ArrayList<LinkedList<Integr>> allLists) throws InvalidInputException
{
if(allLists==null||allLists.size()==0)
{
throw new InvalidInputException();
}
Map<Integer,ArrayList<Integer>> setsMap=findIntersectingSets(alllists);
//Iterate through the map and store all sets into a single array list
ArrayList<ArrayList<Integer>> intersectingLists=new ArrayList<ArrayList<Integer>>();
for(Map.Entry<Integer,ArrayList<Integer>> me:setsMap.entrySet())
{
intersectingLists.add(me.getValue());
}
return intersectingLists;
}
private Map<Integer,ArrayList<Integer>> findIntersectingSets(ArrayList<LinkedList<Integer>> lists)
{
Map<Integer,ArrayList<Integer>> sets=new HashMap<Integer,ArrayList<Integer>>();
for(LinkedList<Integer> ls:lists)
{
//Navigate to the last entry of the current list
Integer m=ls.size()-1;
ArrayList<Integer> set;
//check if this last alue exists in the map(Is there another list we've already seen that intersects with this one?)
if(sets.contains(m))
{
set=sets.get(m);//If tail value exists in the map, get the corresponding value(Array list of head values from other lists that have the same tail)
set.add(ls.get(0));
sets.put(m,set);
}else{
set=new ArrayList<Integer>(1);
set.add(m);
sets.put(m,set);
}
}
return sets;
}
}
Seems easy enough just make a Hash Table with the key been the Data and the value been a list of heads that have them.
Then look them up.
public List<Tuple<int, int>> GetIntersections(List<LinkedList<int>> lists)
{
List<Tuple<int, int>> result = List<Tuple<int, int>>();
var combinations = new HashSet<string>();
var map = new Dictionary<int, List<int>>();
foreach(LinkedList<int> ll in lits)
{
Node<int> current = ll.Head;
while(current != null)
{
if(map.ContainsKey(current.Data))
{
map[current.Data].Add(ll.Head.Data)
}
else
{
map.Add(current.Data, new List<int> { ll.Head.Data };
}
}
}
foreach(LinkedList<int> ll in lits)
{
Node<int> current = ll.Head;
while(current != null)
{
foreach(var head in map[current.Data])
{
if(head != ll.Head.Data)
{
// Find combination and reverse combination exist
// so they are are unique
string hash = head + "," + ll.Head.Data;
string reverseHash = ll.Head.Data + "," + head;
if(!combinations.Contains(hash) &&
!combinations.Contains(reverseHash)
{
combinations.Add(hash);
result.Add(new Tuple<int, int>(ll.Head.Data, head);
}
}
}
}
}
return result;
}
If we are allowed to assume that the numbers are not bigger than K (for example 1000 or something like that) then we can use union-find data structure instead of hash maps. UF allows us to union and find intersection in amortized O(1). As a result what we need is to check union in two nested loops for first elements in each LinkedList. UF requires O(K) memory. Time complexity is bound above by double loop to go through all elements in lists once -> O(N * M).
import java.util.*;
/**
* Created by Igor_Sokolov on 6/16/2015.
*/
public class CareerCup_5991240778645504 {
private static final int K = 1000;
private static class UF {
int[] parent;
int[] rank;
public UF(int size) {
this.parent = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
this.rank = new int[size];
Arrays.fill(rank, 1);
}
public void union(int i, int j) {
int pi = find(i);
int pj = find(j);
if (rank[pi] == rank[pj]) {
parent[pi] = pj;
rank[pj]++;
} else if (rank[pi] > rank[pj]) {
parent[pj] = pi;
} else {
parent[pi] = pj;
}
}
public int find(int j) {
int p = j;
while (parent[p] != p) {
p = parent[p];
}
while (parent[j] != p) {
int x = parent[j];
parent[j] = p;
j = x;
}
return p;
}
}
public static void main(String[] args) {
LinkedList<Integer>[] lists = prepareData();
List<List<Integer>> result = findIntersections(lists);
printResult(result);
}
private static void printResult(List<List<Integer>> result) {
for (List<Integer> list: result) {
StringBuilder sb = new StringBuilder();
for (int i: list) {
sb.append(i).append(' ');
}
System.out.println(sb);
}
}
private static LinkedList<Integer>[] prepareData() {
LinkedList<Integer>[] lists = new LinkedList[5];
for (int i = 0; i < lists.length; i++) {
lists[i] = new LinkedList<>();
}
lists[0].addAll(Arrays.asList(1, 2, 3, 4, 5));
lists[1].addAll(Arrays.asList(6, 7, 8, 4, 5));
lists[2].addAll(Arrays.asList(8, 9, 10, 11, 12));
lists[3].addAll(Arrays.asList(13, 14, 15, 12));
lists[4].addAll(Arrays.asList(16, 17, 18 ));
return lists;
}
private static List<List<Integer>> findIntersections(LinkedList<Integer>[] input) {
UF uf = new UF(K);
final int N = input.length;
for (int i = 0; i < N; i++) {
int head = input[i].getFirst();
for (int v : input[i]) {
uf.union(head, v);
}
}
boolean[] visited = new boolean[N];
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < N; i++) {
if (!visited[i]) {
visited[i] = true;
int x = input[i].getFirst();
List<Integer> list = new ArrayList<>();
list.add(x);
for (int j = i + 1; j < N; j++) {
int y = input[j].getFirst();
if (uf.find(x) == uf.find(y)) {
visited[j] = true;
list.add(y);
}
}
result.add(list);
}
}
return result;
}
}
Algorithm:
1) Go through first list till the end node. Store this end node in the hash.
2) Now if any lists among remaining m-1 lists has same end node then that list is intersecting with this list. Otherwise keep on saving the end nodes only.
Time Complexity: O(nm)
Space Complexity: O(m) Since only last node on m lists is stored in hash.
We can further reduce the time complexity to O(m) if we keep track of last node in our linked list implementation.
I'm pretty sure intersection doesn't have to be the same end node.. that example just happens to have the same end nodes.
Put all list elements in hashtable
Linked list data as key and value as head of each linked list.
Traverse hashtable for a list which is having two or more than two elements.
Print elements of list.
for eg.
HashTable will look like..
Key(node data) Value(headnode)
1---1
2---1
3---1
4---1-->6
5---1--->6
6---6
7---6
8---6--->8
9---8
10--8
11--8
12--8-->13
13--13
14---13
15---13
16---16
17---16
18---16
ANS: 1 6
6 8
8 13
Please explain what intersection means here. What is the inherent logic to solve the problem?. Giving just the code is not enough.
- NoNameKid June 17, 2015Could anyone provide a C++ solution to the problem?