Interview Question for Computer Scientists


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.

- Saket August 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pramod August 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ps September 11, 2014 | Flag
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.

- Chaks November 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

something like natural join of two tables, FriendsA join FriendsB

- Kaustubh May 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 vote

You missed a tag.

- Anonymous August 02, 2014 | Flag Reply
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

- prk2110 January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Stanand April 28, 2015 | Flag
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.

- Gauti September 24, 2014 | Flag Reply
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.

- Gauti September 24, 2014 | Flag Reply
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.

- phoenix August 14, 2015 | Flag Reply
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....

- candy August 21, 2015 | 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