Filter Invalid Data Events

Problem Statement

In telemetry and audit logging systems, raw events must often be sanitized and validated before being forwarded to downstream analytics pipelines. You are tasked with implementing a data filtering function that accepts a list of raw event objects and returns only the valid events, preserving their original order.

An event dictionary has the following structure:

• event_id (str): Unique identifier for the event.
• timestamp (int): Unix epoch timestamp in milliseconds.
• event_type (str): Category of the event.
• user_id (str): Identifier of the user triggering the event.

An event is considered valid if and only if it satisfies all of the following rules:

1. Completeness: All four fields (event_id, timestamp, event_type, user_id) exist, are not None, and strings are non-empty.
2. Time Window: timestamp falls within the inclusive range [start_time, end_time].
3. Allow-list: event_type is present in the allowed_types set.
4. Deduplication: If multiple events with the same event_id pass the first three criteria, keep only the first occurrence and discard subsequent ones.

Function Signature

def filter_events(
    events: list[dict],
    allowed_types: set[str],
    start_time: int,
    end_time: int
) -> list[dict]:
    pass

Examples

Example 1

events = [
    {"event_id": "e1", "timestamp": 1000, "event_type": "PAGE_VIEW", "user_id": "u1"},
    {"event_id": "e2", "timestamp": 500, "event_type": "PAGE_VIEW", "user_id": "u2"},   # timestamp < start_time
    {"event_id": "e3", "timestamp": 1200, "event_type": "UNKNOWN", "user_id": "u3"},     # not in allowed_types
    {"event_id": "e1", "timestamp": 1100, "event_type": "PAGE_VIEW", "user_id": "u1"},   # duplicate event_id
    {"event_id": "e4", "timestamp": 1500, "event_type": "CLICK", "user_id": ""},         # empty user_id
    {"event_id": "e5", "timestamp": 1300, "event_type": "CLICK", "user_id": "u4"}
]

allowed_types = {"PAGE_VIEW", "CLICK"}
start_time = 1000
end_time = 2000

output = filter_events(events, allowed_types, start_time, end_time)
# Output: [events[0], events[5]]

Constraints

• 0 <= len(events) <= 100,000
• 1 <= len(allowed_types) <= 1,000
• 0 <= start_time <= end_time <= 2^63 - 1
• Time Complexity requirement: O(N) where N is the number of events.
• Space Complexity requirement: O(N) to store deduplication keys and results.

Edge Cases

• Empty input list events should return an empty list.
• Events missing one or more required keys completely.
• Invalid events sharing an event_id with a subsequent valid event: the invalid event should be dropped and must not prevent the later valid event from being accepted.