|
Two unsorted linked lists are given. Find the union......
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Two unsorted linked lists are given. Find the union......
Question:
Two unsorted linked lists are given.
Find the union.
Eg: a) 1->9->9->5->7->8->9->7
b) 44->33->1->9->55
Result:
1->9->5->7->8->44->33->55
The elements in the result can be in any order
maybe an answer:
Since no information about not using additional storage is given. I assume we can use HashSet to do the job of intersection.
Algorithm
1. Traverse list 1 and insert into hashset
2. Traverse list 2 and insert into hashset
3. Create the new list by traversing each element in hashset and creating links appropriately
4. Return his newly created list
public LinkedList<Node> LinkedListsUnion(Node root1, Node root2)
{
HashSet<int> elems= new HashSet<int>();
while(root1.Next != null)
{
elems.Insert(root1.Data);
root1=root1.Next;
}
while(root2.Next!=null)
{
elems.Insert(root2.Data);
root2=root2.Next;
}
LinkeList ll= new LinkedList();
foreach(int item in elems)
{
Node n= new Node(item);
if(ll.Root==null)
{
ll.Root=n;
}
else
{
Node temp=ll.root;
//Traverse till the end of the list
//to insert at last
// but since ordering is not important we can even
// change the head ptr to the new node
while(temp.Next==null)
temp=temp.Next;
temp.Next=n;
}
return ll;
}
(Continued on next question...)
Other Interview Questions
| 