## Microsoft Interview Question

• 0

Team: Application insight
Country: Israel
Interview Type: In-Person

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

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.

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

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

Perfect answer, just wanted to add, considering self-balancing BST (AVL-tree) approach, Time-complexity would be nlogn.

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

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.

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

Your time complexity calculation is incorrect - you haven't considered the fact that building the set/tree takes time (e.g. building a balanced binary is O(nlogn))

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

public class Node implements Comparable<Node>
{
private String name;
private int phoneNo;

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.

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

geeksforgeeks.org dynamic-programming-set-34-assembly-line-scheduling

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

geeksforgeeks dynamic-programming-set-34-assembly-line-scheduling

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

dana,
can the original lists be modified ?

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

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)
{
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;

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.