## Interview Question for Computer Scientists

• 0

Country: United States
Interview Type: In-Person

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

Basically a friends network is an undirected graph. Each person is a vertex of the graph and friendship is an edge between the two vertices. We can represent the graph by by maintaining an adjacency list.
- Like: Each person maintains a list of Posts. Lets say person A puts a post, persons who are connected to person A will be notified about the post (observer pattern). Friend B can like a post which increase the 'Like' count.
- Friends Suggestion: For person A find all nodes X that is at distance 2 from node A. (Now this is scalable as the requirements can tell what is the depth we want to look for making suggestions.)
- Common Friends: When A visits person B. Find all nodes X that are at distance 1 from node A.

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

Common friends: finding nodes X that are at distance 1 from node A will give you friend of A but not of B.

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

For common friends, I believe it should be finding all those paths between Node A and Node B whose length is 2. Say Node A - > Node K -> Node B . Such nodes would be the common friends.

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

I think Saket is talking about all friends of B who are at distance 1 from A.

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

something like natural join of two tables, FriendsA join FriendsB

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

You missed a tag.

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

It is not scalabe to do it for large values using graph. Tried this on dijsktra's algorithm,fails above 10^5. as graph complexity increases and time to retrieve becomes very large. Using files is better way

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

I agree that the complexity is bad if we are using graph.
We can use NoSql DB and create document structure like this:
For user:
User {
id = 11
friends_ids: {1, 2, 3, 4}
new_friends_ids: {5, 6}
}

For "like" we need create document for every object that can be liked:

Picture {
id = 14
liked_by_ids: {1,3,5}
}

In this case if you come to your friends page we just need to compare two lists "friends_ids" to know common friends.
To known who liked picture we just need get liked_by_ids list.
This approach can be extended to user comments also.

Scalability is reached by NoSql DB. We can use distributive DB.

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

For common friends check the nodes which are at distance 1 from A then from this list check the list of friends which are at distance 1 from B. For friends suggestion we can consider all the nodes which are not at distance 1 from A or not connected to A.

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

For common friends check the nodes which are at distance 1 from A then from this list check the list of friends which are at distance 1 from B. For friends suggestion we can consider all the nodes which are not at distance 1 from A or not connected to A.

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

you can save a list of friends in set and for common friend search whether it exist in set. Internally it is implemented by tree, so would be quiet fast. I dont know why people are questioning scalability of graph ? It is data structure which is in memory. You can keep data in nosql on back end.However you never need to load all data in memory. You can load data on demand.

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

Traverse the graph from A to find all nodes at a distance of 2 from A. If these are C1, C2... etc. find the C nodes which have the maximum # edges with nodes in A's friend list B1, B2....

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.