Interview Question Computer Scientists
Country: United States
Interview Type: In-Person
Common friends: finding nodes X that are at distance 1 from node A will give you friend of A but not of B.
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.
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
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.
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.
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.
- Saket August 17, 2014- 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.