How to design Facebook wall feed?
Each user should see the posts posted by their friends and themselves.
Each user has a list of posts which is already sorted in ascending order (latest last) as the last posts have been added to the end of the list.
So we basically want to show the latest posts of a certain group of people. Now the question becomes sorting n sorted lists.
We can have a pointer to the last element of each list. The newest post is for sure one of the posts that has a pointer on.
So we push all these last elements to a MinHeap (minheap.Insert) and as definition of MinHeaps, by each insertion, the heap gets reformed so that the smallest value is the value on top of the heap.
Once we added all the last elements, we need to get the element on top which is the newest post and show it on the feed. We do that by calling minheap.delete() function which again reforms the MinHeap.
Now, for the top post that we have found, we need to move the pointer to the previous post on the same list and insert that to the MinHeap, since it can potentially be the next newest post.
We can do the above steps for as many times as we need and for the next scrolling down on the page, find more new posts continuing the previous order with the same pointers.
@yashar I do not think this solution will work in real world. You are storing all the wall posts of each user in a list, which is not practical.
@pranav12 No! Each user already has the list of their posts.
The list that I'm using (let's call it TobeProcessed) will have n+1 elements, where n is number of the friends that the current user has, and +1 is himself.
This list is created once User.GetFeed() has been called. Then, each friend's latest post will be added to this list (TobeProcessed).
At any given time, each friend has at most 1 post in TobeProcessed list. Once a newest post is selected to be posted on the feed (let's say post1), we remove it from TobeProcessed, and add the next newest post from the same friend who posted post1. So the size of the TobeProcessed list remains same (or decreases)
Depends how you want to do it. The most interesting thing in the Facebook feed is that posts are ranked by content more than strict time, and rank varies according to who is viewing them. That would make it much more complicated.
@Fdondi Yes, of course. If you want to add some machine learning to it. But it's not the case in a 40 minutes interview.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.