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.

- jaks September 20, 2016 | Flag Reply
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’.

- genew September 28, 2016 | Flag Reply
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

- Hs September 20, 2016 | Flag Reply
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

- Hs September 20, 2016 | Flag Reply
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

- Hs September 20, 2016 | Flag Reply
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

- Hs September 20, 2016 | Flag Reply
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

- Hs September 20, 2016 | Flag Reply
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

- Hs September 20, 2016 | Flag Reply
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
}
}
}

- Hs September 20, 2016 | Flag Reply
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

- Hs September 20, 2016 | Flag Reply
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

- Hs September 20, 2016 | Flag Reply
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

- Hs September 20, 2016 | Flag Reply
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.

- jaks September 21, 2016 | Flag Reply
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).
i.e. they are already friends.

- VinayS September 23, 2016 | Flag Reply
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>>

- Gloria September 26, 2016 | Flag Reply
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;
		}
		
		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;
	}

- JeffJAVA July 18, 2017 | Flag Reply
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).

- manidam07 September 20, 2016 | Flag Reply


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