Facebook provides a notification service to inform users that one or more of their friend's birthday is lined up this week. Design a data structure to efficiently fetch the birthday's in the given range.
There is another Facebook interview question similar to this - Facebook maintains a log of when somebody logged in and when somebody logged out. Read this data and store it in a data structure. Now find how many users were logged into Facebook at a given time (say 10:25 am today).
Solution:-
I have used a Segment Tree. It is very efficient in performing range based queries. For the birthday problem, i have used a range of 1 to 366 (total number of days in a year). The Segment tree is similar to a binary tree, but it stores range values instead of single value. Each node will contain a range [i, j]. In that case the left node would contain range [i, (i+j)/2]. The right node will contain [(i+j)/2+1, j]. This way it would go on. Once the Segment tree is created, reach each user and store it in the Segment tree. Search is very efficient as it only have to match the given range value.
The same data structure can be used to create bar charts. In a few bar charts that we see, the bar chart range can be gradually decreased. For instance, it shows people between 1-100 years old, then click on it to show 1-50 range and 51-100 range. Then click again to show 1-25, 26-50, 51-75, 76-100...so on. It can go upto single level values. This is an ideal use case for Segment Tree.
There is another Facebook interview question similar to this - Facebook maintains a log of when somebody logged in and when somebody logged out. Read this data and store it in a data structure. Now find how many users were logged into Facebook at a given time (say 10:25 am today).
Solution:-
I have used a Segment Tree. It is very efficient in performing range based queries. For the birthday problem, i have used a range of 1 to 366 (total number of days in a year). The Segment tree is similar to a binary tree, but it stores range values instead of single value. Each node will contain a range [i, j]. In that case the left node would contain range [i, (i+j)/2]. The right node will contain [(i+j)/2+1, j]. This way it would go on. Once the Segment tree is created, reach each user and store it in the Segment tree. Search is very efficient as it only have to match the given range value.
The same data structure can be used to create bar charts. In a few bar charts that we see, the bar chart range can be gradually decreased. For instance, it shows people between 1-100 years old, then click on it to show 1-50 range and 51-100 range. Then click again to show 1-25, 26-50, 51-75, 76-100...so on. It can go upto single level values. This is an ideal use case for Segment Tree.
No comments:
Post a Comment