Amazon Interview Question
Software DevelopersCountry: India
Interview Type: In-Person
1. Find common elements in their adjacency list for person A.
2. Store the number of common elements for A’s 100 friend in an array
3. Use 'min-heap of k elements’ to retain k number of A’s friends with most mutual friends.
4. when A’s friend, say B, add new friends. Recalculate common elements between A and B and run the new number again 'min-heap of k elements’.
pseudocode
Friend F has 500 friends and those 500 friends have 5 frinds
We can have dictionary with key/value as Mutualfriend name and frequency.
for (DirectFriend in F.Friends): //will extract one by one friend from 500 friends
for(MutualFriend in DirectFriend.Friends): //will extract 5 friends one by one
if MutualFriend in HM.keys():
HM[MutualFriend] = 1
else
HM[MutualFriend]+=1
You can also have dictionary with key/value as Mutualfriend name and frequency count
Lets say Friend F has 500 friends
//pseudocode
for (directFriend in F.friends):
for(mutualFriend in directFriend.friends):
if mutualFriend in dict.keys():
dict[mutualFriend] += 1
else:
dict[mutualFriend] = 1
You can also have dictionary with key/value as Mutualfriend name and frequency count
Lets say Friend F has 500 friends
//pseudocode
for (directFriend in F.friends):
for(mutualFriend in directFriend.friends):
if mutualFriend in dict.keys():
dict[mutualFriend] += 1
else:
dict[mutualFriend] = 1
You can also have dictionary with key/value as Mutualfriend name and frequency count
Lets say Friend F has 500 friends
//pseudocode
for (directFriend in F.friends):
for(mutualFriend in directFriend.friends):
if mutualFriend in dict.keys():
dict[mutualFriend] += 1
else:
dict[mutualFriend] = 1
You can also have dictionary with key/value as Mutualfriend name and frequency count
Lets say Friend F has 500 friends
//pseudocode
for (directFriend in F.friends):
for(mutualFriend in directFriend.friends):
if mutualFriend in dict.keys():
dict[mutualFriend] += 1
else:
dict[mutualFriend] = 1
You can also have dictionary with key/value as Mutualfriend name and frequency count
Lets say Friend F has 500 friends
//pseudocode
{for (directFriend in F.friends):
{for(mutualFriend in directFriend.friends):
{if mutualFriend in dict.keys():
dict[mutualFriend] += 1
else:
dict[mutualFriend] = 1
}
}
}
I thought the question was about to choose the best data structure. Recommendation can be done in many factors. e.g. A has friends (B,C,D)
B -> E, C->E, D->F. Get the friends who are also friends with more than one friend (E). So with hashmap, you can have the count. If there is a tie, choose the oldest friend.
We can use a Graph to solve this problem.
Vertices : Person's profile
Edge : Relationship like A is a friend of B.
we can have top 10 Vertices on the basis of Degree as it is going to be a undirected garph.
Condition: That vertex is not adjacent to current profile(Vertex).
i.e. they are already friends.
Graph is the best way for this Social Network Analysis Problem.
Each person represents a NODE. Each edge represents "friend relationship" between two NODES(people).
So java way of representing this would be a
Have a Person class, then have a HashMap to represent this graph
HashMap<String, List<People>>
public class Connection {
List<Connection> connections = new ArrayList<Connection>();
public List<Connection> getConnections(){
return connections;
}
public void addConnection(Connection conn){
this.connections.add(conn);
}
}
public List<Connection> mutualTopTenVotes(Connection A){
Map<Connection,Integer> mutualConnectionsCount = new HashMap<Connection,Integer>();
for(Connection conn:A.getConnections()){
for(Connection aConn:conn.getConnections()){
if(mutualConnectionsCount.get(aConn) == null) mutualConnectionsCount.put(aConn, 1);
else mutualConnectionsCount.put(aConn, mutualConnectionsCount.get(aConn)+1);
}
}
Comparator<Entry> comparator = new Comparator<Entry>() {
@Override
public int compare(Entry o1, Entry o2) {
return ((Integer)o1.getValue()).compareTo((Integer)o2.getValue());
}
};
PriorityQueue<Entry> entries = new PriorityQueue<Map.Entry>(10, comparator);
for(Entry e:mutualConnectionsCount.entrySet()){
entries.add(e);
}
List<Connection> topTen = new ArrayList<Connection>();
for(int i=0;i<10;i++){
topTen.add((Connection) entries.peek().getKey());
}
return topTen;
}
Jaks's Heap implementation is fine, but the main issue is how to get mutual friend count (Frequency).
A is has 100 friend. And each 100 friend have 5 friend. So now A has 500 mutual friend. These all 500 user has mutual friend count AT LEAST 1.
Now to find these 500 user mutual friend count, we need to iterate over all 100 friend of A and find, it is friend of that user OR not. If yes then increase mutual friend count by 1.
But this way 1 user making 100 checks so 500 user will need to make 500*100 calls.
can we have any better solution to find frequency( mutual friend count).
Use HashMap<Friend, Frequency & Index in MinHeap > & MinHeap<Friend with Frequency>. MinHeap has size k. Whenever a friend has more frequency, update the count in hashmap. Then check the count with top of minheap. If count is more than minheap's top, remove top item and insert the new friend. Whenever you do heapify, maintain the index in hashmap. If existing friend's frequency is increased, increase it using heap-increase-key.
- jaks September 20, 2016