Google Interview Question Software Engineers
Country: Switzerland
Interview Type: In-Person
We can keep nodes and connections between nodes represents friendship. Each Node can have a hash table of "Liked Things". Such that every time a person likes something, there will be an observer object for all friends. Then the observer checks to see if the "Liked Object" exists in the respective Node's hashtable.
class Person{
Hashset<Person> friendList = new Hashset<Person>() // like a hashset
}
class Thing{
HashSet<Person> LikedBy = new HashSet<Person>();
}
// Now when someone like Thing T , add that person to hashset of T and if likes are greater than friends of person who likes T then iterate through friend list of person and Find if they exists in hashset of T or vice versa
1. Distributed database will contain (key, value) pairs, representing the edges in friendship graph.
2. For every things(post) we will keep a observer list(implement observer pattern), containing the list of people who already liked it.
3. Now when a new observer register to the list, loop over existing observers and check from the distributed db which pair is actually friends and send the notification accordingly.
Two hashtables
1) Friendship grapgh(hashtable<id, hashset<friend_ids>>. This represents an adjacency list graph representing friends. The key is the person id, the hashset is the list of its friends at distance 1.
2) Hashtable of the items and its corresponding people who like it. Since its not a one to one relationship, one can either choose a unordered multimap, or a hashtable of items with value as set/hash of people ids.
3) operation. Lets assume person <id> like item item <it>.
iterate over the friend list from first table, and then do a lookup into second table. if hit, notify that person of this update. (via callback etc, or have each person register each friend as observers, and notify during the above update which include the liked item information)
1) The 2nd degree friends of each user can be stored as a HashTreeSet (Ordered Hash Set)
- TotalMantella August 22, 20152) The users who have liked each thing can again be stored as a HashTreeSet. Say,
Everytime a thing is liked, get the current sorted list of users who have liked it. Now, do a stepped comparison with the list of 2nd degree friends of the user who has just liked it. If there is matching, then the matched user is sent notification.