Implement Notification Rate Limiter
Company: Cursor
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates the ability to design and implement hierarchical rate limiting using sliding-window aggregation across user, team, and company scopes, testing data-structure selection, time-window accounting, and algorithmic correctness.
Constraints
- 0 <= len(attempts) <= 200000
- 1 <= len(user_to_team) <= 200000
- 1 <= len(team_to_company) <= 200000
- All user IDs in `attempts` exist in `user_to_team`
- All team IDs from `user_to_team` exist in `team_to_company`
- Timestamps are integers and attempts are given in non-decreasing timestamp order
Examples
Input: ({1: 10}, {10: 100}, [(1, 1), (1, 2), (1, 3), (1, 4), (1, 601), (1, 602)])
Expected Output: [True, True, True, False, True, True]
Explanation: The first three attempts are accepted for the user. The fourth is denied because the user would exceed 3 notifications in the last 600 seconds. At timestamp 601, the attempt at time 1 has expired because 601 - 1 = 600, so sending is allowed again.