Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Once GetNewsFeed(user) is called, it will actually see for user friends publish() [which is actually stored just in user's account] and display 30 of them(If exist).
Propose an estimate based on msg operation
Publish: add msg to all the friend's msg list
GetNewsFeed: process all the msg attached to the user
Each user, there's a msg list
UserInfo {
MessageNode *msg_list;
FriendNode *friend_list;
}
void Publish(UserInfo user, string msg) {
// for each friend, insert msg into their msg list
foreach friend in friend_list
insert msg into User[friend].msg_list;
}
void GetNewsFeed(user) {
foreach msg in msg_list
process msg
}
Assume
user num: 1M
avg friend_num: 1k
msg/user/second: 0.001
Consider Publish
msg insertions per second: 1/user/second, 1M total insertions/second
Consider GetNewsFeed
user num: 1M
avg friend_num: 1k
msg read operation/second/user: 1
total msg read operations: 1M
2M total msg operations/second
Assume server capacity = 1k msg operations/ server
num of servers: 2k
My solution is slightly different from the Observer pattern.
In Observer Pattern, the publisher is the one who fires up the trigger. Suppose Obama has 100k listeners on facebook. Whenever Obama updates his status, he's publishing broadcasting updates to 100k listeners, which is not necessary(not all the listeners are active or online-waiting).
On the other hand, we modify the pattern so that observer pulls the trigger.
Guess this fits into publish subscribe model - Observer design pattern
1. Each user owns his/her data in his/her user area (data structure). Can be
class User { UserID id; // unique id std::list<Update> self_updates; // owned by user; list of updates in reverse chrono order std::list<Update *> friend_updates; // owned by user friends; list of updates in reverse chronological order std::list<User *> friends; // Friend list }; class Update { UpdateType type; // media type of this update - can be photo/video etc DateTime timestamp; Message msg; // Message text in this update Media *media; // can be pointer to photo/video/audio in the update OR NULL List<Comment> comments; // Comments on this update }Now Publish(user, msg) will
- jtr.hkcr March 03, 20131. Wrap the msg into Update data structure and add to the front of 'self_updates' list
2. For all the friends in 'friends' list, update their 'friend_updates' list with a pointer to this Update data structure (This is where the observer pattern comes).
Note: A user logged into the FB web UI will see the update when the browser polls the user area for any self/friend updates.
GetNewsFeed(user) will
1. Get the first 30 updates from 'self_updates' and 'friend_updates' sort them according to timestamp (these two are sorted according to timestamp individually). This will interleave self_updates between friend_updates.
2. Take the latest 30 updates from this sorted list to send back to browser UI.
Hope this design suffices.