Estimate Page-Visit Duration from the Next User Event

Problem Statement

In event tracking pipelines, the time a user spends on a page is commonly inferred from the arrival time of their subsequent event. Given a list of event records from user browsing sessions, calculate the duration in seconds that each user spent on each visited page.

Each event record contains:

• event_id (integer): A unique identifier for the event.
• user_id (string): The identifier for the user.
• page_name (string): The name of the page visited.
• timestamp (integer): Unix timestamp in seconds when the event occurred.

Requirements

1. Group events by user_id.
2. Sort each user's events chronologically by timestamp in ascending order. If two events have the identical timestamp, break ties deterministically by event_id in ascending order.
3. The duration_seconds for an event is calculated as the timestamp of the user's immediately following event minus the current event's timestamp.
4. If an event is the user's final event in the dataset, its duration_seconds should be None.
5. The function should return the list of records with an added key duration_seconds, sorted by user_id ascending, then timestamp ascending, then event_id ascending.

Function Signature

def calculate_page_durations(events: list[dict]) -> list[dict]:
    pass

Input & Output Format

• Input: A list of dictionaries, where each dictionary represents an event with keys event_id, user_id, page_name, and timestamp.
• Output: A list of dictionaries containing the original fields plus duration_seconds (an integer or None).

Constraints

• 0 <= len(events) <= 100,000
• timestamp is a non-negative integer (Unix epoch in seconds).
• event_id is a unique positive integer across all events.
• user_id and page_name are non-empty strings.

Examples

Example 1

events = [
    {"event_id": 2, "user_id": "user_A", "page_name": "search", "timestamp": 1600000030},
    {"event_id": 1, "user_id": "user_A", "page_name": "home", "timestamp": 1600000000},
    {"event_id": 3, "user_id": "user_A", "page_name": "listing", "timestamp": 1600000100}
]

# Output:
[
    {"event_id": 1, "user_id": "user_A", "page_name": "home", "timestamp": 1600000000, "duration_seconds": 30},
    {"event_id": 2, "user_id": "user_A", "page_name": "search", "timestamp": 1600000030, "duration_seconds": 70},
    {"event_id": 3, "user_id": "user_A", "page_name": "listing", "timestamp": 1600000100, "duration_seconds": None}
]

Example 2 (Timestamp Tie)

events = [
    {"event_id": 12, "user_id": "user_B", "page_name": "checkout", "timestamp": 1600000500},
    {"event_id": 10, "user_id": "user_B", "page_name": "cart", "timestamp": 1600000500}
]

# Output:
[
    {"event_id": 10, "user_id": "user_B", "page_name": "cart", "timestamp": 1600000500, "duration_seconds": 0},
    {"event_id": 12, "user_id": "user_B", "page_name": "checkout", "timestamp": 1600000500, "duration_seconds": None}
]

Edge Cases to Consider

• Empty input list [] should return [].
• A user having only a single event must have duration_seconds: None.
• Simultaneous events (identical timestamps) resulting in duration_seconds: 0.