Microsoft Interview Question
Team: Application insight
Country: Israel
Interview Type: In-Person
Perfect answer, just wanted to add, considering self-balancing BST (AVL-tree) approach, Time-complexity would be nlogn.
This can be further optimized by adding into the new list as you insert into the hashset. This avoids iteration over hashset to populate the new linked list.
public class Node implements Comparable<Node>
{
private String name;
private int phoneNo;
private String address;
public int compareTo(Node n)
{
if(n==null || !n instanceOf Node)
{
return -1;
}
if(name.equals(n.name)&&phoneNo.equals(n.phoneNo))
{
return 0;
}
return -1;
}
}
public class ListService
{
public static Node mergeWithoutDuplicates(Node l1,Node l2) throws NullPointerException
{
if(l1==null||l2==null)
{
throw new NullPointerException();
}
Node p=l1;
while(p.next!=null)
{
p=p.next;
}
p.next=l2;
return(removeDuplicates(l1));
}
private Node removeDuplicates(Node ls)
{
HashMap<Node,Boolean> mp=new HashMap<Node,Boolean>();
Node s=null;
Node f=ls;
while(f!=null)
{
if(!mp.containsKey(f))
{
mp.put(f,true);
}else
{
s.next=f.next;
f.next=null;
f=s.next;
}
}
return ls;
}
}
//O(n+m) space and O(n+m) time.
This is a O(n2) complexity solution, but does not require extra space. The 2 input linked lists are inputted as an array 'list'.
for (int j = 0; j < list.Length; j++)
{
var node = list[j];
while (node != null)
{
var left = head;
while (left != curpos)
{
if (node.Value == left.Value)
{
break;
}
left = left.Next;
}
if (left == curpos && left.Value != node.Value)
{
curpos.Next = node;
curpos = curpos.Next;
}
node = node.Next;
}
}
curpos.Next = null;
return head;
Iterate through both lists and insert each node of each list in a hash table or a balanced binary search tree indexed by (name, phone) key-value pairs (in C++ you can use a set<pair<string, string>>, assuming name and phone are strings). When inserting, if an element is already there, then just ignore the current node and do not insert it.
- 010010.bin August 03, 2015Then iterate through the set / hash table, building a new list along the way. Each node retrieved from the set is a new node in the linked list.
Time complexity: linear in the size of the lists
Space complexity: linear in the size of the lists
Other possible approaches include sorting both lists to avoid using additional space, but it comes at the cost of raising running time to O(n log(n)); OR you can use nested loops to check if each node exists in the other list or on the rest of the current list, but that would be n^2.