## Amazon Interview Question for Software Developers

Country: India
Interview Type: In-Person

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

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.

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

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

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

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

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

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

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

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``````

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

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``````

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

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

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

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``

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

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
}
}
}

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

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

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

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

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

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

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

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.

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

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

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

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

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

``````public class Connection {
List<Connection> connections = new ArrayList<Connection>();

public List<Connection> getConnections(){
return connections;
}

}
}

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()){
}

List<Connection> topTen = new ArrayList<Connection>();
for(int i=0;i<10;i++){
}
}``````

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

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

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.