Facebook Interview Question Web Developers
Country: United States
Interview Type: Phone Interview
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.
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;
}
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;
}
}
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];
}
}
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);
}
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);
}
}
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);
}
}
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));
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?
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
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);
}
}
}
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; }
}
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; }
}
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; }
}
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);
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);
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;
}
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;
}
}
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)
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);
}
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);
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.
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;
}
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);
}
}
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
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
- Shail September 03, 2018public 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); } }