- Initial Considerations
- Worst case scenario, whether it’s a push or a pull, it’s 10^5, so 10^5 queries will break the bank.
- (Tip: In the case of “push”, which changes the recipient’s value when a notification occurs, it is not allowed if 10^5 people with 10^5 friends send the notification 10^5 times. Conversely, in the case of a “pull”, where you go to check who among your friends sent the notification when you confirm the notification, it is not allowed if a person with many friends confirms the notification all the time).
- Delay only the processing of people whose friends are on route N or higher.
- These people are high route N people.
- Only pull these people x when confirming notification
- Total number of notifications generated by x with x
- The total number of routes y has received from x. Highly route n
- Subtract these two and you get the number of new notifications from x
- Consideration complete
- Official Explanation - square partitioning OK
This page is auto-translated from /nishio/PAST5O using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.