Katkat
Back

Implement a URL-Prefix Sliding-Window Alert Monitor

AddeparSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests the ability to manage time-based sliding windows and prefix-based path aggregation to trigger alerts based on request thresholds.

Problem Statement

Design a class AlertMonitor that tracks the number of error requests for specific URL prefixes over a rolling 10-minute time window. If the number of errors for a given prefix exceeds a specified threshold, the system should trigger an alert.

Your class needs to support the following methods:

  1. record_error(timestamp: int, url: str): Records an error for a specific URL at the given Unix timestamp. The prefix of the URL is defined as everything up to the first two path segments (e.g., for api.com/v1/users/list, the prefix is api.com/v1/users).
  2. should_alert(timestamp: int, prefix: str, threshold: int) -> bool: Returns True if the number of errors recorded for the given prefix within the range [timestamp - 600, timestamp] is strictly greater than threshold.

Constraints

  • timestamp is a positive integer.
  • threshold is a non-negative integer.
  • The system must efficiently handle many calls to record_error and should_alert.

Examples

# 10 minutes = 600 seconds
monitor = AlertMonitor()
monitor.record_error(1000, "api.com/v1/users/login")
monitor.record_error(1200, "api.com/v1/users/create")

# Returns True (2 errors in window [601, 1201])
print(monitor.should_alert(1201, "api.com/v1/users", 1))

# Returns False (threshold not exceeded)
print(monitor.should_alert(1201, "api.com/v1/users", 2))

Edge Cases

  • Multiple errors for the same prefix at the same timestamp.
  • should_alert calls with timestamps much later than the last recorded error (ensure stale data is handled).

Hints

Hint 1

Use a hash map where keys are URL prefixes and values are lists of timestamps representing when errors occurred for that prefix.

Hint 2

When calling `should_alert`, iterate through the stored timestamps for the prefix and remove those that fall outside the 10-minute (600 seconds) window.

Hint 3

For faster lookups, consider if a double-ended queue (deque) or binary search on a sorted list could optimize the removal of expired timestamps.

Follow-up questions

  • How would you optimize the memory usage if the system processes millions of unique prefixes?
  • How would you modify the design to support a rolling window of 24 hours instead of 10 minutes?
  • What changes are needed if the system must be distributed across multiple servers, and how would you handle synchronization?