## Facebook Interview Question for Web Developers

• 1
of 1 vote

Country: United States
Interview Type: Phone Interview

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

``````public class Contact {
int contactId;
List<String> emails;

Contact(int contactId, List<String> emails) {
this.contactId = contactId;
this.emails = emails;
}

@Override
public boolean equals(Object o) {
if(!(o instanceof Contact)) return false;
Contact otherContact = (Contact) o;
for(String email : emails)
if(otherContact.emails.contains(email)) {
merge(otherContact.emails);
return true;
}
return false;
}

private void merge(List<String> emails) {
for(String email : this.emails) {
if(!emails.contains(email)) {
emails.add(email);
}
}
}

@Override
public int hashCode() {
return 7;
}
}

public class Cleaner {
public Set<Contact> cleanContacts(List<Contact> contacts) {
return new HashSet<>(contacts);
}
}``````

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

The Equals function is not transitive. Consider three contacts:

* 1, with emails [a, b]
* 2, with emails [b, c]
* 3, with emails [c, d]

a == b, and b == c, but a != c. This will make the behaviour of your set implementation dependent.

Also, the complexity of this solution is probably too high for any interviewer, they will ask you to optimise it.

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

foooo

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

We can achieve this using 1 Map and 2 Sets.
Time Complexity O(N * K) --> N is the total number of contacts and K is a number of email IDs per contact.
Space Complexity O(K)

Logic: Consider input is a Map<Contact_ID, Set<Email_IDs>>.
1. Create emailToContact Map. This map keep track of email as key and contactID as value.
2. Create uniqueContactSet, duplicateContactSet. These Sets keep contactID that are unique and duplicate.
2. We loop through the input map and for each contact, get the list of email IDs
3. We add email IDs to emailToContact Map. If the key with that email already present, that means this email is duplicate with some other contacts email.
4. If duplicate email found, we populate duplicateContactSet with its contactID
5. At the end, we return nonduplicate contacts only.

Here is the code

``````private static Set<String> uniqueContacts(Map<String, Set<String>> input) {
Map<String, String> emailToContact = new HashMap<>();
Set<String> duplicateSet = new HashSet<>();
Set<String> uniqueSet = new HashSet<>();

for(String contactId: input.keySet()) {
uniqueSet.add(contactId);
Set<String> emails = input.get(contactId);
for(String email: emails) {
if(emailToContact.containsKey(email)) {
duplicateSet.add(emailToContact.get(email));
duplicateSet.add(contactId);
}else {
emailToContact.put(email, contactId);
}
}
}
uniqueSet.removeAll(duplicateSet);
return uniqueSet;
}``````

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

void removeDuplicates(std::unordered_map<std::string, std::unordered_set<std::string>>& inputMap, std::unordered_set<std::string>& uniqueSet) {
std::unordered_map<std::string, bool> uniqueIDs;

bool unique = true;
for (auto entry : inputMap) {
for (auto email : entry.second) {
if (uniqueIDs[email]) {
unique = false;
break;
}
else {
uniqueIDs[email] = true;
}
}
if (unique)
uniqueSet.insert(entry.first);
else unique = true;
}
}

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

The approach I would go using only C basics features (no library at all) in a situation where space isn't a problem:

Time complexity: O(n), being n the number of contacts;
Space complexity: O(n), being the maximum number of IDs
Algorithm:
1. create an auxiliary array to maintain the state for each email, if it was already used or not (the array key is the email ID while the value is 0 or 1 for "not used" or "used";
2. traverse the contact array checking and _if not used_ setting the email ID on the auxiliary array as "used";
3. clone the contact info to another array or erase its "line" from the original contact array.

``````#define NUM_CONTACTS 256 // just an example

// [contact id, email id]
int contacts[NUM_CONTACTS][2] = { 0 };
int uniq_contacts[NUM_CONTACTS][2] = { 0 };

void search_duplicates(void)
{
int i;
int email_used[NUM_CONTACTS] = { 0 }; // init all as false

for (i = 0; i < NUM_CONTACTS; i++) {
if (email_used[contacts[i][1]])
continue;

email_used[contacts[i][1]] = 1 // true;
uniq_contacts[i][0] = contacts[i][0];
uniq_contacts[i][1] = contacts[i][1];
}
}``````

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

Scanner sc = new Scanner(System.in);
int noOfRecords =sc.nextInt();

int j=0;
HashMap<String,String> map= new HashMap<>();
while(j<noOfRecords)
{
sc.nextLine();
String contactName = sc.next();

String contactId = sc.next();
String emailId = sc.next();
if(!map.containsKey(emailId))
if(!map.containsValue(contactName))
map.put(emailId,contactName);
j++;
}
System.out.println(map);
}

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

``````class Contact {
int contactId;
List<String> emails;

Contact(int contactId, List<String> emails) {
this.contactId = contactId;
this.emails = emails;
}

@Override
public boolean equals(Object o) {
if(!(o instanceof Contact)) return false;
Contact otherContact = (Contact) o;
for(String email : emails)
if(otherContact.emails.contains(email)) {
merge(otherContact.emails);
return true;
}
return false;
}

private void merge(List<String> emails) {
for(String email : this.emails) {
if(!emails.contains(email)) {
emails.add(email);
}
}
}

@Override
public int hashCode() {
return 7;
}
}

public class Cleaner {
public Set<Contact> cleanContacts(List<Contact> contacts) {
return new HashSet<>(contacts);
}``````

}

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

class Contact {
int contactId;
List<String> emails;

Contact(int contactId, List<String> emails) {
this.contactId = contactId;
this.emails = emails;
}

@Override
public boolean equals(Object o) {
if(!(o instanceof Contact)) return false;
Contact otherContact = (Contact) o;
for(String email : emails)
if(otherContact.emails.contains(email)) {
merge(otherContact.emails);
return true;
}
return false;
}

private void merge(List<String> emails) {
for(String email : this.emails) {
if(!emails.contains(email)) {
emails.add(email);
}
}
}

@Override
public int hashCode() {
return 7;
}
}

public class Cleaner {
public Set<Contact> cleanContacts(List<Contact> contacts) {
return new HashSet<>(contacts);
}
}

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

``````const myContacts = [
['a','b','c'],
['d'],
['e'],
['f','d'],
['a','b']
];

const removeDupes = contacts => {
const emails = {};
const deduped = [...contacts];
contacts.forEach((contact, id) => {
contact.forEach(email => {
if(emails[email] !== undefined) {
deduped[id] = null;
} else {
emails[email] = id;
}
});
});
return deduped.filter(a => !!a);
}

console.log(removeDupes(myContacts));``````

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

Commenting on the solution on the top by Saurabh. Originally I arrived at a similar solution by storing all duplicates and removing them from the final list. However I then corrected my solution to avoid 'transitive' removal of contacts. Consider the following example of contacts:
1 a b
2 b c
3 c d

The solution above will remove all of the contactIDs and return an empty set, because the second contactD has one 'email' in common with the first contactID ('b'), and the third contactID has one 'email' in common with the second contactID ('c'). This solution above marks all contactIDs as duplicates.

However I think removing duplicates means you remove just contactIDs that are duplicate with some other contactID that will remain in the output not those that were duplicate with the removed one. So I think the correct outputs are the following:
{1, 3}

(OR also {2, 3} and {1, 2} if order of the input does not matter)

ContactIDs 1 and 3 have no email in common so they should not be removed. Part of my code doing this is below. It only adds the emails of a contactID into the tracking list if the contactID is not removed:

``````for(String contact : listOfContacts.keySet()){
boolean toBeRemovedFlag = false;
for(String email : listOfContacts.get(contact)){
if(emailsAll.containsKey(email)){
toBeRemoved.add(contact);
toBeRemovedFlag = true;
break;
}
}
if(!toBeRemovedFlag){
for(String email : listOfContacts.get(contact)){
if(emailsAll.containsKey(email)){
emailsAll.put(email, emailsAll.get(email) + 1);
} else {
emailsAll.put(email, 1);
}
}
}
}``````

What do you think, which approach is correct?

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

public findUniques(Map<String, List<String>> contacts) {

Map<String, List<String>> reverseContacts = new HashMap();

for(String contact : contacts.keySet()) {
List<String> emailsForContact = contacts.get(contact);
for(String email : emailsForContact) {
List<String> contactsContainingEmail;
if(reverseContacts.containsKey(email)) {
contactsContainingEmail = reverseContacts.get(email);
} else {
contactsContainingEmail = new ArrayList();
}
contactsContainingEmail.add(contact);
reverseContacts.put(email, contactsContainingEmail);
}
}

for(String email : reverseContacts.keySet()) {
List<String> contacts = reverseContacts.get(email);

List<String> uniqueContacts = new ArrayList();

if(contacts.size()>1) {
uniqueContacts.addAll(contacts);
}
}
}
Example computation -

1 a b
2 b c
3 c d

a 1
b 1 2
c 2 3
d 3

output

1 3

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

``````import java.util.*;
class Contact{
int contactId;
List<String> emails;
Contact(int contactId,ArrayList<String> emails ){
this.contactId=contactId;
this.emails=emails;
}
}
public class ContactList{

Map<String, Integer> emailMap = new HashMap<String,Integer>();
public List<Contact> filterContactList(List<Contact> contactList){
List<Contact> removeContacts = new ArrayList<Contact>() ;
for(Contact contact : contactList){
for(String email:contact.emails){
if(emailMap.containsKey(email)){
removeContacts.add(contact);
break;
}
else{
emailMap.put(email,contact.contactId);
}
}
}
contactList.removeAll(removeContacts);
return contactList;

}
public static void main(String args[]){
List<Contact> listOfContacts = new ArrayList<Contact>();
Contact contact1 = new Contact(1,new ArrayList<>(Arrays.asList("Email1", "Email2", "Email3")));
Contact contact2 = new Contact(2,new ArrayList<>(Arrays.asList("Email4", "Email5")));
Contact contact3 = new Contact(3,new ArrayList<>(Arrays.asList("Email1", "Email6")));
Contact contact4 = new Contact(4,new ArrayList<>(Arrays.asList("Email6", "Email7")));
listOfContacts.add(contact1);
listOfContacts.add(contact2);
listOfContacts.add(contact3);
listOfContacts.add(contact4);
ContactList object = new ContactList();
List<Contact> filteredListOfContacts= object.filterContactList(listOfContacts);

for(Contact contact:filteredListOfContacts){
System.out.println("Id : "+contact.contactId);
}

}
}``````

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

public class DuplicatedContacts
{
public void Run()
{
var contacts = GetContacts();
var length = contacts.Count;

for (int i = length - 1; i > 0; i--)
{
for (var j = i - 1; j > -1; j--)
{
var intersectedList = contacts[i].Emails.ToList().Intersect(contacts[j].Emails.ToList()).ToList();
if (intersectedList.Count > 0)
{
contacts.Remove(contacts[j]);
}
}
}

contacts.ForEach(el =>
{
Console.WriteLine(el.ContactID + " " + el.ContactName);
});

Console.ReadKey();
}

static List<Contact> GetContacts()
{
var contacts = new List<Contact>();

contacts.Add(new Contact()
{
ContactID = 1,
ContactName = "Bill",
Emails = new int[]{
1, 2
}
});

contacts.Add(new Contact()
{
ContactID = 2,
ContactName = "Matt",
Emails = new int[]{
1
}
});

contacts.Add(new Contact()
{
ContactID = 3,
ContactName = "Erik",
Emails = new int[]{
3, 2
}
});

contacts.Add(new Contact()
{
ContactID = 4,
ContactName = "Vick",
Emails = new int[]{
4, 5
}
});

return contacts;
}
}

public class Contact
{
public int ContactID { get; set; }
public string ContactName { get; set; }
public int[] Emails { get; set; }
}

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

``````public class DuplicatedContacts
{
public void Run()
{
var contacts = GetContacts();
var length = contacts.Count;

for (int i = length - 1; i > 0; i--)
{
for (var j = i - 1; j > -1; j--)
{
var intersectedList = contacts[i].Emails.ToList().Intersect(contacts[j].Emails.ToList()).ToList();
if (intersectedList.Count > 0)
{
contacts.Remove(contacts[j]);
}
}
}

contacts.ForEach(el =>
{
Console.WriteLine(el.ContactID + " " + el.ContactName);
});

Console.ReadKey();
}

static List<Contact> GetContacts()
{
var contacts = new List<Contact>();

contacts.Add(new Contact()
{
ContactID = 1,
ContactName = "Bill",
Emails = new int[]{
1, 2
}
});

contacts.Add(new Contact()
{
ContactID = 2,
ContactName = "Matt",
Emails = new int[]{
1
}
});

contacts.Add(new Contact()
{
ContactID = 3,
ContactName = "Erik",
Emails = new int[]{
3, 2
}
});

contacts.Add(new Contact()
{
ContactID = 4,
ContactName = "Vick",
Emails = new int[]{
4, 5
}
});

return contacts;
}
}

public class Contact
{
public int ContactID { get; set; }
public string ContactName { get; set; }
public int[] Emails { get; set; }``````

}

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

``````public class DuplicatedContacts
{
public void Run()
{
var contacts = GetContacts();
var length = contacts.Count;

for (int i = length - 1; i > 0; i--)
{
for (var j = i - 1; j > -1; j--)
{
var intersectedList = contacts[i].Emails.ToList().Intersect(contacts[j].Emails.ToList()).ToList();
if (intersectedList.Count > 0)
{
contacts.Remove(contacts[j]);
}
}
}

contacts.ForEach(el =>
{
Console.WriteLine(el.ContactID + " " + el.ContactName);
});

Console.ReadKey();
}

static List<Contact> GetContacts()
{
var contacts = new List<Contact>();

contacts.Add(new Contact()
{
ContactID = 1,
ContactName = "Bill",
Emails = new int[]{
1, 2
}
});

contacts.Add(new Contact()
{
ContactID = 2,
ContactName = "Matt",
Emails = new int[]{
1
}
});

contacts.Add(new Contact()
{
ContactID = 3,
ContactName = "Erik",
Emails = new int[]{
3, 2
}
});

contacts.Add(new Contact()
{
ContactID = 4,
ContactName = "Vick",
Emails = new int[]{
4, 5
}
});

return contacts;
}
}

public class Contact
{
public int ContactID { get; set; }
public string ContactName { get; set; }
public int[] Emails { get; set; }
}``````

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

``````class Contact
{
public \$contact_id = null;
public \$email_ids = [];
public \$next;

function __construct(int \$contact_id = null, array \$email_ids)
{
\$this->contact_id = \$contact_id;
\$this->email_ids = \$email_ids;
\$this->next = null;
}

}

class ContactsList
{
public \$root;
public function __construct(Contact \$contact)
{
\$this->root = \$contact;
}

public function addContact(Contact \$contact)
{
\$current = \$this->root;
while(\$current)
{
if(\$current->next)
{
\$current = \$current->next;
}
else
{
\$current->next = \$contact;

break;
}
}
}

public function removeDuplicates()
{
\$current = \$this->root;
while(\$current)
{
\$temp_current = \$current;
\$prev = null;
while(\$temp_current)
{
if(\$temp_current->next)
if(sizeof(array_intersect(\$temp_current->email_ids, \$temp_current->next->email_ids)) > 0)
{
\$temp_current->next->email_ids = [];
\$tmp = \$temp_current->next->next;
\$temp_current->next = \$tmp;
}
\$temp_current = \$temp_current->next;
}

\$current = \$current->next;
}
}

public function printUnique(Contact \$contact)
{
while(\$contact)
{
if(!empty(\$contact->email_ids))
print_r(\$contact->contact_id);
echo "\n";

\$contact = \$contact->next;
}
}
}

\$contact = new Contact(1, [1, 3]);
\$contacts_list = new ContactsList(\$contact);
\$contacts_list->addContact(new Contact(2, [3, 5]));
\$contacts_list->addContact(new Contact(3, [10]));
\$contacts_list->addContact(new Contact(4, [11]));
\$contacts_list->removeDuplicates();
\$contacts_list->printUnique(\$contact);``````

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

``````class Contact
{
public \$contact_id = null;
public \$email_ids = [];
public \$next;

function __construct(int \$contact_id = null, array \$email_ids)
{
\$this->contact_id = \$contact_id;
\$this->email_ids = \$email_ids;
\$this->next = null;
}

}

class ContactsList
{
public \$root;
public function __construct(Contact \$contact)
{
\$this->root = \$contact;
}

public function addContact(Contact \$contact)
{
\$current = \$this->root;
while(\$current)
{
if(\$current->next)
{
\$current = \$current->next;
}
else
{
\$current->next = \$contact;

break;
}
}
}

public function removeDuplicates()
{
\$current = \$this->root;
while(\$current)
{
\$temp_current = \$current;
\$prev = null;
while(\$temp_current)
{
if(\$temp_current->next)
if(sizeof(array_intersect(\$temp_current->email_ids, \$temp_current->next->email_ids)) > 0)
{
\$temp_current->next->email_ids = [];
\$tmp = \$temp_current->next->next;
\$temp_current->next = \$tmp;
}
\$temp_current = \$temp_current->next;
}

\$current = \$current->next;
}
}

public function printUnique(Contact \$contact)
{
while(\$contact)
{
if(!empty(\$contact->email_ids))
print_r(\$contact->contact_id);
echo "\n";

\$contact = \$contact->next;
}
}
}

\$contact = new Contact(1, [1, 3]);
\$contacts_list = new ContactsList(\$contact);
\$contacts_list->addContact(new Contact(2, [3, 5]));
\$contacts_list->addContact(new Contact(3, [10]));
\$contacts_list->addContact(new Contact(4, [11]));
\$contacts_list->removeDuplicates();
\$contacts_list->printUnique(\$contact);``````

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

public static List<Contact> removeDuplicates(List<Contact> contacts){
Map<String, Integer> emailMap = new HashMap<String, Integer>();
List<Contact> contactUnique = new ArrayList<Contact>();
Iterator<Contact> it = contacts.iterator();

/*
* O(n) iterate over contacts and create email map
*/
while (it.hasNext()) {
Contact con = it.next();
Iterator<String> emailIt = con.getEmail().iterator();
while (emailIt.hasNext()) {
String email = emailIt.next();
if(emailMap.get(email) == null){
emailMap.put(email, 1);
}else{
Integer count = emailMap.get(email);
emailMap.put(email, ++count);
}
}
}

Iterator<Contact> it_1 = contacts.iterator();
while (it_1.hasNext()) {
Contact con = it_1.next();
Iterator<String> emailIt = con.getEmail().iterator();
Boolean isUnique = Boolean.TRUE;
while (emailIt.hasNext()) {
String email = emailIt.next();
if(emailMap.get(email) > 1){
isUnique = Boolean.FALSE;
break;
}
}
if(isUnique){
contactUnique.add(con);
}
}
return contactUnique;
}

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

``````public class DuplicateContacts {

public static class Contacts {

String contactID;
List<String> emails = new ArrayList<>(  );

public Contacts (String contactID, List<String> emails) {
this.contactID = contactID;
this.emails = emails;
}
}

public static void main(String[] args) {
Contacts c1 = new Contacts( "C1", Arrays.asList("a@gmail.com", "b@gmail.com", "c@gmail.com", "d@gmail.com") );
Contacts c2 = new Contacts( "C2", Arrays.asList("aa@gmail.com", "bb@gmail.com", "cc@gmail.com") );
Contacts c3 = new Contacts( "C3", Arrays.asList("a@gmail.com", "b@gmail.com", "c@gmail.com") );
Contacts c4 = new Contacts( "C4", Arrays.asList("aa@gmail.com", "bb@gmail.com", "cc@gmail.com") );
Contacts c5 = new Contacts( "C5", Arrays.asList("aaa@gmail.com") );

List<Contacts> list = Arrays.asList( c1,c2,c3,c4,c5 );

Set<Contacts> finalList = getUniqueList(list);

for (Contacts ct : finalList)
System.out.print(ct.contactID + " ");
}

private static Set<Contacts> getUniqueList(List<Contacts> listContact) {
Set<Contacts> finalList = new HashSet<>(  );
Map<String, Contacts> map = new HashMap<>();

for (Contacts c : listContact) {
for (String email : c.emails) {
if (!map.containsKey( email ))
map.put (email, c);
}
}

for (Contacts c : map.values()) {
if (listContact.contains( c ))
finalList.add(c);
}

return finalList;
}
}``````

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

Very elegant solutions here, but they seem oddly complicate:

using python:

``````#ASSUMPTION 1: The first occurrence should be kept and whatever record with same email that appears afterwards will be ignored.
#ASSUMPTION 2: Although the first occurrence in the file should be kept, the print order doesn't matter.
#ASSUMPTION 3: a single email doesn't repeat in the same contact
# contact_list is the list of contacts

exclusive_contact_list = list()

for contact in contact_list:
for x in exclusive_contact_list:
if len(set(contact[1] + x[1])) != len(contact[1]) + len(x[1]):
break
else:
exclusive_contact_list.append(contact)

for contact in exclusive_contact_list:
print(contact)``````

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

class Contact {
int ID;
list<string> emails;
public:
Contact(int id, list<string> email) {
ID = id;
emails = email;
}
friend void uniqueNumber(vector<Contact> objList) {
unordered_map<int, list<string> >umap;
unordered_map<int, list<string> >::iterator it;
for (int i = 0; i < objList.size(); i++) {
Contact c = objList.at(i);
umap[c.ID] = c.emails;
}
for (auto it : umap) {
if (it.second.size() == 1)
std::cout << it.first << std::endl;
}
}
};
void main() {
Contact c1(12, { "a@gmail.com","b@gmail.com" });
Contact c2(13, { "c@gmail.com" });
Contact c3(14, { "d@gmail.com" });
Contact c4(15, { "e@gmail.com","f@gmail.com" });
vector<Contact> c = { c1,c2,c3,c4 };
uniqueNumber(c);
}

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

``````class Contact {
int ID;
list<string> emails;
public:
Contact(int id, list<string> email) {
ID = id;
emails = email;
}
friend void uniqueNumber(vector<Contact> objList) {
unordered_map<int, list<string> >umap;
unordered_map<int, list<string> >::iterator it;
for (int i = 0; i < objList.size(); i++) {
Contact c = objList.at(i);
umap[c.ID] = c.emails;
}
for (auto it : umap) {
if (it.second.size() == 1)
std::cout << it.first << std::endl;``````

;
void main() {
Contact c1(12, { "a@gmail.com","b@gmail.com" });
Contact c2(13, { "c@gmail.com" });
Contact c3(14, { "d@gmail.com" });
Contact c4(15, { "e@gmail.com","f@gmail.com" });
vector<Contact> c = { c1,c2,c3,c4 };
uniqueNumber(c);

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

I dont think maps would work here.
Consider this example

p1 -> a, b, c
p2 -> d
p3 -> d, a
p4 -> e

in this case there is only one unique contact that is p1. This problem can be thought as a graph problem where we care supposed to find all disconnected graphs.

In above example p1, p2 and p3 are connected together hence same contact. p4 is disconnected.

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

``````const unique = test.reduce((a, v) => {
!a.get(v.name) && a.set(v.name, v)
return a;
}, new Map())

console.log([...unique.values()])``````

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

struct Contact {
int id;
vector<string> emails;
};

void removeDups_i(unordered_map <string, unordered_set<string>>& graph, unordered_set<string>& visited, string email) {
visited.insert(email);

for (const auto& nbr : graph[email]) {
if (visited.find(nbr) == visited.end()) {
removeDups_i(graph, visited, nbr);
}
}
}

vector<Contact> removeDups(vector<Contact> contacts) {
unordered_map <string, unordered_set<string>> graph;
unordered_set<string> visited;
vector<Contact> res;

for (const auto& val : contacts) {
for (int i = 0; i < val.emails.size(); i++) {
for (int j = i + 1; j < val.emails.size(); j++) {
graph[val.emails[i]].insert(val.emails[j]);
graph[val.emails[j]].insert(val.emails[i]);
}
}
}

for (const auto& contact : contacts) {
bool newContact = true;
for (const auto& email : contact.emails) {
if (visited.find(email) != visited.end()) {
newContact = false;
break;
}

}

if (newContact) {
res.push_back(contact);
removeDups_i(graph, visited, contact.emails[0]);
}
}

return res;
}

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

``````public static void OutputUniqueContactEmails(List<Tuple<string,string>> input)
{
var contacts = new Dictionary<string, string>();

foreach (var contact in input)
{
if (!contacts.ContainsValue(contact.Item2))
{
contacts.Add(contact.Item1, contact.Item2);
}
}

foreach (var contact in contacts)
{
Console.WriteLine(contact.Key);
}
}``````

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

Take the hint form this solution;

``````package facebook;

import java.util.*;

/**
* Author: Nitin Gupta(nitin.gupta@walmart.com)
* Date: 01/04/19
* Description:
*/
public class ContactCleaner {

static class Contact {
String userName;

Set<String> contacts;

boolean isVisited = false;

int index = -1;

public Contact(String name, Set<String> set, int index) {
userName = name;
contacts = new HashSet<>(set);
this.index = index;
}

@Override
public String toString() {
return String.valueOf(index);
}
}

public static void main(String args[]) {

String [][]contacts =  {{"John", "john@gmail.com", "john@fb.com"},
{"Dan", "dan@gmail.com", "+1234567"},
{"john123", "5412312", "john123@skype.com"},
{"john1985", "5412312", "john@fb.com"},
{"john19856", "john123@skype.com", "john@fb1.com"},
{"Dan2", "dan123@gmail.com", "+1234567"},{"Dan3", "dan@gmail.com", "+123456712312"},
{"Sandy", "sandy@gmail.com", "+123456712"},{"sandy4", "sandy@fb.com", "sandy@gmail.com"}};

List<Contact> contactList = buildContactList(contacts);
List<Set<Contact>> result = buildContactGraph(contactList);

System.out.println(result);
}

private static List<Set<Contact>> buildContactGraph(List<Contact> contactList) {

Map<String, List<Contact>> map = buildContactMap(contactList);

List<Set<Contact>> result = new ArrayList<>();

for (List<Contact> contacts : map.values()) {
Set<Contact> uniques = null;
for (Contact con : contacts) {

if (!con.isVisited) {
uniques = dfs(map, con, new HashSet<>());
}

}
if (uniques != null)
result.add(uniques);

}

return result;

}

private static Set<Contact> dfs(Map<String, List<Contact>> map, Contact con, Set<Contact> uniques) {

if (!con.isVisited) {
con.isVisited = true;
uniques.add(con);

for (String s : con.contacts) {
List<Contact> contactList = map.get(s);

for (Contact c : contactList) {
if (!c.isVisited) {
dfs(map, c, uniques);
}
}
}

}

return uniques;
}

private static Map<String, List<Contact>> buildContactMap(List<Contact> contactList) {

Map<String, List<Contact>> map = new HashMap<>();

for (Contact cont : contactList) {

for (String c : cont.contacts) {

if (map.containsKey(c)) {
map.get(c).add(cont);
} else {
List<Contact> list = new ArrayList<>();
list.add(cont);
map.put(c, list);
}

}
}
return map;

}

private static List<Contact> buildContactList(String[][] contacts) {

List<Contact> contactList = new LinkedList<>();

for (int i = 0; i < contacts.length; i++) {
Set<String> conts = new HashSet<>();
for (int j = 1; j < contacts[0].length; j++) {
conts.add(contacts[i][j]);
}

contactList.add(new Contact(contacts[i][0], conts, i));

}

return contactList;
}
}``````

This print duplicate together, to make this question
1. Just keep email id in contacts ( instead phone etc)
2. once found the result, print only those who set size is 1

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

Time complexity: O(n) where n is the number of items in the value collection of the input.
Simple Py soln.

def removeDups(x):
y = dict()
dups = []

for k,v in x.items():

for _v in v:
if _v not in y.keys():
y[_v] = k
else:
dups.append(k)
dups.append(y[_v])

res = [k for k,v in x.items() if k not in dups]

return res

Add a Comment
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.

Learn More

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

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More