Find returning users from access logs

Given an unordered log of web access events, identify which users are returning (i.e., they have visited on at least two different calendar days). Each event is a tuple (user_id, timestamp_iso 8601). Output the set of user_ids that meet the criterion. Address:

1. parsing and time-zone normalization;
2. handling large logs that don't fit in memory;
3. algorithmic complexity;
4. test cases including edge cases near midnight and duplicate events.

Find Returning Users by UTC Days

You are given an unordered list of web access events. Each event is [user_id, timestamp_iso8601]. A user is considered returning if they have at least two visits on different UTC calendar dates. The timestamp always includes a timezone (e.g., 'Z' or '+HH:MM'). Normalize each timestamp to UTC before extracting the date. Return the list of user_ids who are returning, sorted in ascending lexicographic order. Ignore duplicate events (same user_id and identical timestamp).

Constraints

• 0 <= len(events) <= 200000
• events[i] = [user_id, timestamp_iso8601]
• user_id is a non-empty string of length <= 64
• timestamp_iso8601 format: YYYY-MM-DDTHH:MM:SS.ffffff
• Different days are determined after converting timestamps to UTC
• Duplicate events do not increase day counts
• Return user_ids sorted lexicographically

Examples

Example 1

Input: events = [["alice","2021-03-01T23:30:00-01:00"],["alice","2021-03-02T00:15:00+02:00"],["bob","2021-03-05T10:00:00Z"],["bob","2021-03-05T23:59:59+00:00"],["carol","2021-04-10T00:00:00Z"],["alice","2021-03-02T08:00:00Z"]]
Output: ["alice"]

Explanation: After UTC normalization, alice visited on 2021-03-01 and 2021-03-02; bob only on 2021-03-05; carol has one event.

Example 2

Input: events = [["u1","2021-12-31T23:59:59-00:30"],["u1","2022-01-01T00:00:00+00:00"],["u1","2022-01-02T00:00:00Z"],["u2","2022-06-01T12:00:00Z"],["u2","2022-06-01T12:00:00Z"]]
Output: ["u1"]

Explanation: The first two u1 events normalize to the same UTC date (2022-01-01); the third is 2022-01-02, so u1 is returning. u2 has a duplicate single-day event.

Hints

1. Normalize timestamps to UTC and then take the calendar date (yyyy-mm-dd).
2. In Python, replace a trailing 'Z' with '+00:00' and use datetime.fromisoformat, then astimezone(timezone.utc).date().
3. Track per-user unique UTC dates; you only need to know whether a second, different date has been seen.
4. Use a set for the resulting user_ids and sort before returning.
5. Process events in a streaming manner to handle large logs without storing them all.

Approach

Convert each timestamp to a UTC date and count unique UTC dates per user. Maintain a dictionary mapping user_id to the (small) set of dates seen. When a user is observed on a different UTC date than previously recorded, add them to the result and stop tracking them to save memory. Duplicates (same user and timestamp) do not change the set of dates. Finally, return sorted user_ids for deterministic output. This approach can be streamed and does not require loading the entire log into memory at once.

• Time complexity: O(n + r log r), where n is the number of events and r is the number of returning users (sorting cost).
• Space complexity: O(u), where u is the number of users not yet classified as returning.