In a Databricks Agent Framework deployment, tool calls from multiple agents are logged as a time-ordered stream. Implement an algorithm that returns the first timestamp when any agent exceeds a sliding-window limit, using standard data structures efficiently.
Given a list of events events, where each event is [timestamp, agent_id], and integers window_size and max_calls, return the earliest timestamp at which some agent_id has made more than max_calls calls within the inclusive window [timestamp - window_size + 1, timestamp]. If no agent violates the limit, return -1.
events: List[List[int, str]], window_size: int, max_calls: intintEvents are already sorted by non-decreasing timestamp. This models practical throttling for Databricks Foundation Model APIs or Model Serving requests issued by agents.
Example 1
events = [[1,"agentA"],[2,"agentA"],[3,"agentB"],[4,"agentA"]], window_size = 3, max_calls = 24agentA, the window at timestamp 4 is [2,4], containing calls at 2 and 4 plus the earlier call at 1 is excluded. Actually calls in [2,4] are 2 and 4, so no violation there; including timestamp 3 for agentB does not matter. The first violation would not occur, so this example is not violating. Use the second example for a violating case.Example 2
events = [[1,"agentA"],[2,"agentA"],[3,"agentA"]], window_size = 3, max_calls = 23agentA has 3 calls in window [1,3], exceeding the limit of 2.1 <= len(events) <= 10^51 <= window_size <= 10^91 <= max_calls <= 10^50 <= timestamp <= 10^9events is sorted by non-decreasing timestampagent_id is a non-empty stringevents = [[1, "agentA"], [2, "agentA"], [3, "agentA"]], window_size = 3, max_calls = 2Output3WhyAt timestamp 3, `agentA` has calls at 1, 2, and 3 within the inclusive window `[1, 3]`, so the limit is exceeded.events = [[1, "agentA"], [2, "agentB"], [4, "agentA"], [5, "agentA"]], window_size = 2, max_calls = 2Output-1WhyNo agent has more than 2 calls in any inclusive 2-second window. Calls from different agents are counted separately.1 <= len(events) <= 10^51 <= window_size <= 10^91 <= max_calls <= 10^50 <= timestamp <= 10^9events is sorted by non-decreasing timestampagent_id is a non-empty stringdef first_rate_limit_violation(events, window_size, max_calls):
