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.

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.

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.

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.

Hints

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

Community answers

Answer by flattop.smarts-09

How are users/teams/companies mapped? Is there some predefined object mapping them all?

Loading coding console...