## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Create a Node for each Entry with the following structure:

Node {

List<Strings> info
int index
boolean visited

}

For every string entry in "info", hash the Node into the Hashtable. Then, for each node, run DFS. Add all the Nodes to a visited list, and make a set out of these nodes. Next, run DFS for another Node. We know that if it is visited, then it already exists in the set. Keep running DFS until we exhaust all Nodes.

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

When we create hashtable of info -> Node. the info code be same phone number belonging to two diff entries or email ids belonging to two different entries.
The previous hashtable entry will be overritten. In that case how will DFS reach that node if we are using Hashtable to store the graph.?

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

Well we can certainly store it as info -> ArrayList<Node> to do a DFS.

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

Create a graph of contact Nodes.
Connect two node if they share a common email, phone or name.
The contacts to be merged will form a connected component.
Number of connected components is total unique contacts

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

Just to make sure, the complexity time is O(n), right?
Iterate over the list and create node for each entry + add each contact info to hash - O(n).
Run BFS and perform merge - O(n) - we visit each node maximum two times.

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

Don't we require O(n^2) just to create the graph? Is there any better solution with union-find?

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

SK's approach is easier can be in O(Contacts*length(infos))

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

``````public static void main(String[] args) {
// TODO Auto-generated method stub

HashMap<String, Integer> h = new HashMap();
String[][] A = { { "John", "john@gmail.com", "john@fb.com"},
{ "Dan", "dan@gmail.com", "+1234567"},
{"john123", "+5412312", "john123@skype.com"},
{ "john1985", "+5412312", "john@fb.com"}  };

int code = 0;
for(int i = 0; i < A.length; i++) {
int c = -1;
for(int j = 0; j < A[i].length; j++) {
String s = A[i][j];
if(h.containsKey(s)) {
c = h.get(s);
break;
}
}
if(c == -1) {
c = code++;
}
for(int j = 0; j < A[i].length; j++) {
String s = A[i][j];
h.put(s,  c);
}
}

for(int i = 0; i < A.length; i++) {
System.out.println(h.get(A[i][0]));
}

}``````

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

There is a small issue in the code i.e it connects elements which have first common element. In above case it will connect john123 and john1985 but it will not connect John to it.

Rewriting code to merge all connected contacts:
public static void main(String[] args) {
// TODO Auto-generated method stub

HashMap<String, Integer> h = new HashMap();
String[][] A = { { "John", "john@gmail.com", "john@fb.com"},
{ "Dan", "dan@gmail.com", "+1234567"},
{"john123", "+5412312", "john123@skype.com"},
{ "john1985", "+5412312", "john@fb.com"} };

int code = 0;
for(int i = 0; i < A.length; i++) {
int c = -1;
Set<Integer> groupings = new HashSet<Integer>();
for(int j = 0; j < A[i].length; j++) {
String s = A[i][j];
if(h.containsKey(s)) {
int value=h.get(s);
c = Math.min(c,value);
}
}
if(c == -1) {
c = code++;
}
else
{
groupings.remove(c);
for(Integer k : groupings )
{
for(int m=0;m<A[0].length;m++)
{
h.put(A[k][m],c);
}
}

}
for(int j = 0; j < A[i].length; j++) {
String s = A[i][j];
h.put(s, c);
}
}

for(int i = 0; i < A.length; i++) {
System.out.println(h.get(A[i][0]));
}

}

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

Above code has bug that it merge contact based on first common findings, while not considering other matchings as well.
Corrected code:

``````public static void main(String[] args) {
// TODO Auto-generated method stub

HashMap<String, Integer> h = new HashMap();
String[][] A = { { "John", "john@gmail.com", "john@fb.com"},
{ "Dan", "dan@gmail.com", "+1234567"},
{"john123", "+5412312", "john123@skype.com"},
{ "john1985", "+5412312", "john@fb.com"}  };

int code = 0;
for(int i = 0; i < A.length; i++) {
int c = -1;
Set<Integer> groupings = new HashSet<Integer>();
for(int j = 0; j < A[i].length; j++) {
String s = A[i][j];
if(h.containsKey(s)) {
int value=h.get(s);
c = Math.min(c,value);
}
}
if(c == -1) {
c = code++;
}
else
{
groupings.remove(c);
for(Integer k : groupings )
{
for(int m=0;m<A[0].length;m++)
{
h.put(A[k][m],c);
}
}

}
for(int j = 0; j < A[i].length; j++) {
String s = A[i][j];
h.put(s,  c);
}
}

for(int i = 0; i < A.length; i++) {
System.out.println(h.get(A[i][0]));
}

}``````

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

SK has given an overview about the solution, here's the details and code

1.) Convert contact array to list of Contact Object
2.) Create a map with key all the contact details(email, phone) and value be list of Contact(Person1, person2).
3.) Go through the map and for each contact in the list get the contact details(email, phone) and go over the map recursively and find out what other contact are mapped, while doing so mark contact as visited true.
4.) Add the person to a set.
5.) Add set to result list

``````import java.util.*;

class UnionPerson2 {

static class Contact {
List<String> contactList;
String name;
boolean visited;
Contact(List<String> contactList, String name, boolean visited) {
this.contactList = contactList;
this.name = name;
this.visited = visited;
}

}

public static void main(String a[]) {
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> conList = new ArrayList<Contact>();
for(int i = 0 ; i < contacts.length; i++) {
List<String> contactList = new ArrayList<String>();
for(int j = 1 ; j < contacts[i].length; j++) {
}
Contact con = new Contact(contactList, contacts[i][0], false);
}

Map<String, List<Contact>> map = new HashMap<String, List<Contact>>();
for(Contact c: conList) {
List<Contact> indexList = new ArrayList<Contact>();
for(String detail: c.contactList) {
if(map.containsKey(detail)) {
indexList = map.get(detail);
map.put(detail, indexList);

} else {
indexList = new ArrayList<Contact>();
map.put(detail, indexList);

}
}
}
List<Set<Contact>> resultList = new ArrayList<Set<Contact>>();
for(List<Contact> ls: map.values()) {
Set<Contact> resultSubList = new HashSet<Contact>();
for(Contact c: ls) {
if(!c.visited) {
resultSubList = findUnion(map, c, resultSubList);
}
}

}

for(Set<Contact> subList: resultList) {
if(subList.size() > 0) {
for(Contact co: subList) {
System.out.print(co.name + ", ");
}
System.out.println();
}
}
}

static Set<Contact> findUnion(Map<String, List<Contact>> map, Contact cont, Set<Contact> resultSubList) {
if(!cont.visited){
cont.visited = true;
for(String contactListStr: cont.contactList) {
for(Contact c: map.get(contactListStr)){
if(!c.visited) {
findUnion(map, c, resultSubList);
}
}
}
}
return resultSubList;

}
}``````

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

``````#define MAX_STRING_LNG 100

#include<stdio.h>
#include<conio.h>
#include<string.h>

struct contactInfo{
char name[MAX_STRING_LNG];
};

int main(){

int size=0;
scanf("%d",&size);

int samePerson[size];
int samePersonCounter = 0;
int anotherPerson[size];
int anotherPersonCounter = 0;
struct contactInfo contactDetails[size];

for(int i=0; i<size; i++){
scanf("%s",contactDetails[i].name);
}

for(int i=0; i<size; i++){
for(int j=1; j<size; j++){
if(firstContactResult == 0 || secondContactResult == 0){
anotherPerson[anotherPersonCounter] = i;
anotherPersonCounter++;
break;
}
else{
samePerson[samePersonCounter] = i;
samePersonCounter++;
break;
}
}
}

printf("\n\n");
for(int i=0; i<samePersonCounter; i++){
printf("%d",samePerson[i]);
}

printf("\n\n");
for(int i=0; i<anotherPersonCounter; i++){
printf("%d",anotherPerson[i]);
}
}``````

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

Above code has bug that it merge contact based on first common findings, while not considering other matchings as well.
Corrected code:

``````public static void main(String[] args) {
// TODO Auto-generated method stub

HashMap<String, Integer> h = new HashMap();
String[][] A = { { "John", "john@gmail.com", "john@fb.com"},
{ "Dan", "dan@gmail.com", "+1234567"},
{"john123", "+5412312", "john123@skype.com"},
{ "john1985", "+5412312", "john@fb.com"}  };

int code = 0;
for(int i = 0; i < A.length; i++) {
int c = -1;
Set<Integer> groupings = new HashSet<Integer>();
for(int j = 0; j < A[i].length; j++) {
String s = A[i][j];
if(h.containsKey(s)) {
int value=h.get(s);
c = Math.min(c,value);
}
}
if(c == -1) {
c = code++;
}
else
{
groupings.remove(c);
for(Integer k : groupings )
{
for(int m=0;m<A[0].length;m++)
{
h.put(A[k][m],c);
}
}

}
for(int j = 0; j < A[i].length; j++) {
String s = A[i][j];
h.put(s,  c);
}
}

for(int i = 0; i < A.length; i++) {
System.out.println(h.get(A[i][0]));
}

}``````

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

That's a O(n(^2)) solution. I think there is one in O(n log(n))

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

can you share O(nlogn) solution for this? Creating graph itself should be O(n^2).

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

you can looks like this

``````for (int i = 0; i < size;++i)
{
for (int j = i + 1; j < size; ++j)
{
//index the similar contacts in sameperson array
}
}``````

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

oh..and that will cut down the cost to O(n!)

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

First of all, thank you for the warm and fresh new question!!.

Here is C++ version of the solution.

This algorithm first construct the graph with each row as an edge and phone/email as a vertex.
I used DFS to find the connected graph.

Running time of this algorithm is O(N), where N is the number of distinct phone/email string.
Using the hashtable, constructing a graph takes O(N) although I did not implement hashtable in this solution. std::map will provide log(n) search time.
So, it will be O(N Log N ).

``````#include <map>
#include <list>
#include <string>
#include <iostream>
using namespace std;

struct edge;
struct vertext;

struct vertex {
string value;
bool visited;
vertex * parent;
list<edge *> edges;
map<string, edge*> merged;
vertex(string v): value(v), parent(0), visited(false){}
};

struct edge{
vertex *v;
vertex *w;
string* original;
string value;
edge(string v, string* o):value(v), original(o){}
};

void dfs(vertex *v, vertex *parent)
{
list<edge *>::iterator iter;
list<edge *>::iterator subiter;
for (iter = v->edges.begin(); iter != v->edges.end(); iter++)
{
edge *e = (*iter);
vertex* w = (e->v->value != v->value)? e->v : e->w;
if (w->visited != true)
{
w->visited = true;
w->parent = parent;
for (subiter = w->edges.begin(); subiter != w->edges.end(); subiter++)
{
if (parent->merged.find((*subiter)->value) == parent->merged.end())
{
parent->merged[(*subiter)->value] = (*subiter);
}
}
dfs(w, parent);
}
}
}

list<list<string>> merge_contact(string ** input, int len)
{
list<list<string>>result;
map<string, vertex *> vertices;
map<string, vertex *>::iterator iter;

//create the graph
for (int i = 0; i <len; i++)
{
edge * e = new edge(input[i][0], input[i]);
if ((iter = vertices.find(input[i][1])) != vertices.end())
{
e->v = iter->second;
e->v->edges.push_back(e);
} else {
vertex * v = new vertex(input[i][1]);
vertices[v->value] = v;
v->edges.push_back(e);
e->v = v;
}

if ((iter = vertices.find(input[i][2])) != vertices.end())
{
e->w = iter->second;
e->w->edges.push_back(e);
} else {
vertex * w = new vertex(input[i][2]);
vertices[w->value] = w;
w->edges.push_back(e);
e->w = w;
}
}

for(iter = vertices.begin(); iter != vertices.end(); iter++)
{
if (iter->second->visited != true)
{
iter->second->visited = true;
dfs(iter->second, iter->second);
}
}

for (iter = vertices.begin(); iter!= vertices.end(); iter++)
{
vertex *v = iter->second;
if (!v->parent)
{
list<string> m;
map<string, edge*>::iterator i;
for(i = v->merged.begin(); i != v->merged.end(); i++)
{
edge * e = i->second;
m.push_back(e->original[0]);
m.push_back(e->original[1]);
m.push_back(e->original[2]);
}
result.push_back(m);
}
}
return result;
}

int main()
{
string ** input = new string*[4];
string s1[3] = {"John", "john@gmail.com", "john@fb.com"};
string s2[3] = {"Dan", "dan@gmail.com", "+1234567"};
string s3[3] = {"john123", "+5412312", "john123@skype.com"};
string s4[3] = {"john1985", "+5412312", "john@fb.com"};
input[0] = s1;
input[1] = s2;
input[2] = s3;
input[3] = s4;
list<list<string>>result = merge_contact(input, 4);

list<list<string>>::iterator i;
list<string>::iterator i2;
for (i = result.begin(); i != result.end(); i++)
{
cout << "[ ";
for (i2 = (*i).begin(); i2 != (*i).end(); i2++)
{
cout<<(*i2) <<", ";
}
cout<< " ], ";
}

cout<< endl;
return 1;
}``````

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

Your code fails for this input:

``````string ** input = new string*[8];

string s0[3] = { "t", "x", "y" };
string s1[3] = { "g", "h", "i" };
string s2[3] = { "r", "s", "t" };
string s3[3] = { "o", "m", "n" };
string s4[3] = { "y", "h", "w" };
string s5[3] = { "e", "z", "v" };
string s6[3] = { "a", "b", "c" };
string s7[3] = { "f", "b", "e" };
input[0] = s0;
input[1] = s1;
input[2] = s2;
input[3] = s3;
input[4] = s4;
input[5] = s5;
input[6] = s6;
input[7] = s7;

list<list<string>>result = merge_contact(input, 8);``````

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

Looks like this was expected to be written in Python..

``````# Build reverse hash of lists using content as key and array of index as value
datamap = {}
for i,j in enumerate(data):
for k in j:
if k in datamap:
datamap[k] = datamap[k] + [i]
else:
datamap[k] = [i]sets = [set(i) for i in datamap.values() if i]

# Now merge/union the intersecting sets
sets = [set(i) for i in datamap.values() if i]
merged = True
while sets and merged:
first, rest = sets[0], sets[1:]
sets = []
merged = False
for x in rest:
if first.intersection(x):
first = first.union(x)
merged = True
else:
sets.append(x)
sets.append(first)

res = [list(a) for a in sets]
print res``````

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

# Build reverse hash of lists using content as key and array of index as value
# hashmap with int won't work cause dup key get overwritten immediately.
datamap = {}
for i,j in enumerate(data):
for k in j:
if k in datamap:
datamap[k] = datamap[k] + [i]
else:
datamap[k] = [i]

print datamap

# Now merge/union the intersecting sets
sets = [set(i) for i in datamap.values() if i]
merged = True
while sets and merged:
first, rest = sets[0], sets[1:]
sets = []
merged = False
for x in rest:
if first.intersection(x):
first = first.union(x)
merged = True
else:
sets.append(x)
sets.append(first)
print "res : %s"%sets

res = [list(a) for a in sets]
print res

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

``````contacts =  [["John", "john@gmail.com", "john@fb.com"],
["john123", "+5412312", "john123@skype.com"],
["john1985", "+5412312", "john@fb.com"],
["Dan", "dan@gmail.com", "+1234567"],
["Dan123", "dan@gmail.com", "+1876234"],
["DannyBoy", "dan@fb.com", "+1234567"],]

def overlaps(c1, c2):
return (c1 & c2) != set([])

contacts = [set(c) for c in contacts]
merged_contacts = []

while contacts:
group = [contacts.pop(0)]

for existing in group:
for contact in contacts:
if overlaps(existing, contact):
group.append(contact)
contacts.remove(contact)

merged_contacts.append(group)

print merged_contacts``````

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

Here is the swift implementation

``````func filterContacts(contacts: [[String]]) -> [[Int]]? {
if contacts.count == 0 {
return nil
}
var result = [[Int]]()
for i in 0..<contacts.count-1 {
var map = [String: Int]()
for str in contacts[i] {
map[str] = 1
}
for j in i+1..<contacts.count {
var unique = true
for element in contacts[j] {
if map[element] != nil {
unique = false
break
}
}
if unique {
result.append([i])
}
} else {
for k in 0..<result.count {
if result[k].contains(i) {
result[k].append(j)
}
break
}
}
for k in 0..<result.count {
if result[k].contains(j) {
result[k].append(i)
}
break
}
}
} else {
result.append([i, j])
}
}
}
}
return result
}``````

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

Swift implementation

``````func filterContacts(contacts: [[String]]) -> [[Int]]? {
if contacts.count == 0 {
return nil
}
var result = [[Int]]()
for i in 0..<contacts.count-1 {
var map = [String: Int]()
for str in contacts[i] {
map[str] = 1
}
for j in i+1..<contacts.count {
var unique = true
for element in contacts[j] {
if map[element] != nil {
unique = false
break
}
}
if unique {
result.append([i])
}
} else {
for k in 0..<result.count {
if result[k].contains(i) {
result[k].append(j)
}
break
}
}
for k in 0..<result.count {
if result[k].contains(j) {
result[k].append(i)
}
break
}
}
} else {
result.append([i, j])
}
}
}
}
return result
}``````

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

Here's a plain and simple JS solution. Spiffed up the input a bit to create more complexity.

``````var input = [[ "John", "john@gmail.com", "john@fb.com"],
[ "Dan", "dan@gmail.com", "+1234567"],
[ "john123", "+5412312", "john123@skype.com"],
[ "john1985", "+5412312", "john@fb.com"],
[ "Billy Bob", "+3453555", "john123@skype.com"],
[ "Sandra", "+224551", "sandra@gmail.com"],
[ "Gina", "+3453555", "gina@skype.com"],
[ "Virgil", "+224551", "virgil@skype.com"]];

var contacts = (function(){

var nodes = {};

function Node (index) {
this.visited = false;
this.index = index;
}

};

Node.prototype.isVisited = function () {
return this.visited;
};

Node.prototype.getCluster = function (output) {

var i = 0;

output || (output = []);

this.visited = true;
output.push(this.index);

for (i; i < linkedLength; i++) {
}
}

// make it pretty
return output.sort();
}

return {
findIdenticalContacts: function (input) {

var i, j, row, rowLength, rowEntry, node;

var map = {};

for (i in input) {

row = input[i];
rowLength = row.length;
node = new Node(i);

nodes[i] = node;

for (j = 0; j < rowLength; j++) {

rowEntry = row[j];

if (map[rowEntry]) {
}

map[rowEntry] = i;
}
}

for (i in nodes) {
node = nodes[i];

if (!node.isVisited()) {
// doing console out, we can do one extra step to push all these into output
console.log(node.getCluster());
}
}

}
};

}());

contacts.findIdenticalContacts(input);``````

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

``````var input = [[ "John", "john@gmail.com", "john@fb.com"],
[ "Dan", "dan@gmail.com", "+1234567"],
[ "john123", "+5412312", "john123@skype.com"],
[ "john1985", "+5412312", "john@fb.com"],
[ "Billy Bob", "+3453555", "john123@skype.com"],
[ "Sandra", "+224551", "sandra@gmail.com"],
[ "Gina", "+3453555", "gina@skype.com"],
[ "Virgil", "+224551", "virgil@skype.com"]];

var contacts = (function(){

var nodes = {};

function Node (index) {
this.visited = false;
this.index = index;
}

};

Node.prototype.isVisited = function () {
return this.visited;
};

Node.prototype.getCluster = function (output) {

var i = 0;

output || (output = []);

this.visited = true;
output.push(this.index);

for (i; i < linkedLength; i++) {
}
}

// make it pretty
return output.sort();
}

return {
findIdenticalContacts: function (input) {

var i, j, row, rowLength, rowEntry, node;

var map = {};

for (i in input) {

row = input[i];
rowLength = row.length;
node = new Node(i);

nodes[i] = node;

for (j = 0; j < rowLength; j++) {

rowEntry = row[j];

if (map[rowEntry]) {
}

map[rowEntry] = i;
}
}

for (i in nodes) {
node = nodes[i];

if (!node.isVisited()) {
// doing console out, we can do one extra step to push all these into output
console.log(node.getCluster());
}
}

}
};

}());

contacts.findIdenticalContacts(input);``````

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.