How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Cursor.

What role is this question designed for?

This question is commonly asked for Backend Engineer candidates at Cursor during technical interviews.

Implement Notification Rate Limiter | Cursor Coding Question

Implement Notification Rate Limiter

Company: Cursor

Role: Backend Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement `should_send_notifications(user_id, timestamp) -> bool`. You are given two mappings: - each `user_id` belongs to exactly one `team_id` - each `team_id` belongs to exactly one `company_id` A notification attempt made by `user_id` at `timestamp` should be **allowed** only if accepting it would keep all of the following sliding-window limits satisfied over the previous 10 minutes: - a user may send at most **3** notifications - a team may send at most **10** notifications - a company may send at most **20** notifications If the request is allowed, it must immediately count toward the user, team, and company limits. If it is denied, it must not be recorded. Assume timestamps are integer seconds and calls arrive in non-decreasing timestamp order. Be prepared to walk through real test cases and explain the time and space complexity of your approach.

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.

Implement a simulator for `should_send_notifications(user_id, timestamp) -> bool`. Each `user_id` belongs to exactly one `team_id`, and each `team_id` belongs to exactly one `company_id`. Process notification attempts in the given order and return whether each attempt is allowed. An attempt at time `t` is allowed only if, after accepting it, the number of accepted notifications with timestamps `s` such that `t - s < 600` would remain at most 3 for that user, 10 for that team, and 20 for that company. If an attempt is allowed, it must be recorded immediately for the user, team, and company. If it is denied, it must not be recorded.

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.

Input: ({1: 10, 2: 10, 3: 10, 4: 10, 5: 10}, {10: 100}, [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 6), (2, 7), (3, 8), (4, 9), (5, 10), (1, 11), (2, 601)])

Expected Output: [True, True, True, True, True, True, True, True, True, True, False, True]

Explanation: The first 10 accepted attempts fill the team quota. The attempt at time 11 is denied because the team would exceed 10 notifications, and denied attempts do not get recorded. At time 601, the event at time 1 has expired, so the team has room again.

Input: ({1: 10, 2: 10, 3: 10, 4: 10, 5: 20, 6: 20, 7: 20, 8: 20, 9: 30, 10: 30, 11: 30, 12: 30}, {10: 100, 20: 100, 30: 100}, [(1, 1), (2, 2), (3, 3), (4, 4), (1, 5), (2, 6), (3, 7), (5, 8), (6, 9), (7, 10), (8, 11), (5, 12), (6, 13), (7, 14), (9, 15), (10, 16), (11, 17), (12, 18), (9, 19), (10, 20), (11, 21), (12, 601)])

Expected Output: [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False, True]

Explanation: The company accumulates 20 accepted notifications across three teams without any single team exceeding 10. The attempt at time 21 is denied because the company limit would be exceeded. At time 601, the accepted event at time 1 has expired, so the final attempt is allowed.

Input: ({1: 10}, {10: 100}, [])

Expected Output: []

Explanation: There are no attempts to process, so the result is an empty list.

Hints

Keep separate recent accepted timestamps for each user, team, and company.
Because timestamps are processed in sorted order, a deque lets you remove expired timestamps from the front in amortized O(1) time.

Quick Overview

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.