Implement a URL-Prefix Sliding-Window Alert Monitor

Design the implementation of a URL-prefix alert monitor that ingests request logs. Each request belongs to its exact path and every parent path prefix. For example, `/users/objects` contributes once to each of `/`, `/users`, and `/users/objects`. For every prefix, track request and error counts in the most recent 10 minutes. A prefix qualifies for an alert when its window contains at least 10 requests and its error rate is strictly greater than 30%. Explain the data structures, log ingestion, expiration, and alert evaluation. Compare a tree of path segments with a dictionary keyed by full prefixes. The timestamp representation, handling of late logs, precise cutoff inclusion, and repeated-alert policy are unspecified. Identify those choices and state the assumptions under which your implementation works. ### What a Strong Answer Covers - Segment-aware parent prefixes, including the root, with each log counted exactly once per relevant prefix. - Request and error counters that lose an expired log's contribution at every ancestor. - Correct handling of the minimum count and strict percentage threshold, including exactly 30% errors. - An explicit distinction between a prefix satisfying the predicate and a notification being emitted repeatedly or only on a state transition. - Time and memory costs expressed in active logs and path depth, plus a policy for out-of-order input and inactive paths. ```hint Expiration can change the ratio Removing successful requests can increase an error rate even when no new error arrives. Decide which prefixes must be reevaluated when an old log expires. ``` ### Follow-up Questions - What changes if alerts must react to expiration while no new logs arrive? - How would you avoid treating `/users2` as a descendant of `/users`?