Find returning users from access logs
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: This question evaluates skills in time-series data processing, timestamp parsing and time-zone normalization, scalable stream or batch handling for logs that exceed memory, algorithmic complexity analysis, and test-case design for edge conditions such as midnight boundaries and duplicate events.
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](Z|±HH:MM)
- Different days are determined after converting timestamps to UTC
- Duplicate events do not increase day counts
- Return user_ids sorted lexicographically
Hints
- Normalize timestamps to UTC and then take the calendar date (yyyy-mm-dd).
- In Python, replace a trailing 'Z' with '+00:00' and use datetime.fromisoformat, then astimezone(timezone.utc).date().
- Track per-user unique UTC dates; you only need to know whether a second, different date has been seen.
- Use a set for the resulting user_ids and sort before returning.
- Process events in a streaming manner to handle large logs without storing them all.