题目重点：扫描 userId action timestamp 日志，匹配 signin 到下一次 signout，找出时差不超过阈值的用户并说明异常日志规则。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练输入按 timestamp 非降序排列，每个用户的操作交替为 signin、signout；跨用户交错允许，同时间事件按输入顺序处理。
- 重复 signin、无前置 signin 的 signout、未知 action 或时间倒退视为非法输入；未闭合 signin 不构成有效 session。
- 返回去重的 userId 列表并按字典序排序；题目只要求找出所有 id，未公开输出顺序。
解题路线
- 维护 open[userId]=最近尚未结束的 signin 时间，并用 valid set 保存已有有效会话的用户。
- 扫描 signin 时确保该用户当前未打开会话后记录时间；扫描 signout 时取出打开时间并比较 0≤timestamp−start≤maxTime，满足则把 userId 加入 valid。
- 扫描结束后的 open 项没有下一次 signout，不计入。最后对 valid 排序返回；若只需集合，可省去排序。
- 流式输入可边读边处理，但必须明确排序保证；若日志会乱序，需要按事件时间缓存与 watermark，并重定义迟到事件如何修正结果。
手动走一遍
日志 A signin@0、B signin@2、A signout@5、B signout@10，maxTime=5，则 A 的会话时长 5 有效，B 时长 8 无效。若 A 之后再有一段无效会话，A 仍应出现在结果中。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training variant: chronological alternating signin/signout per user."""
def users_with_valid_session(
logs: list[tuple[str, str, int]], max_time: int
) -> list[str]:
if max_time < 0:
raise ValueError("max_time must be nonnegative")
opened: dict[str, int] = {}
valid: set[str] = set()
previous_time: int | None = None
for user, action, timestamp in logs:
if previous_time is not None and timestamp < previous_time:
raise ValueError("logs must be chronological")
previous_time = timestamp
if action == "signin":
if user in opened:
raise ValueError("duplicate signin")
opened[user] = timestamp
elif action == "signout":
if user not in opened:
raise ValueError("signout without signin")
start = opened.pop(user)
if timestamp - start <= max_time:
valid.add(user)
else:
raise ValueError("unknown action")
return sorted(valid)
复杂度
N 条日志、U 个用户，单次扫描期望 O(N) 时间与 O(U) 状态空间；若按字典序返回 V 个有效用户，再加 O(V log V) 排序。乱序排序输入会增加 O(N log N)。
易错点与追问
容易失分的边界
- 一旦某用户出现无效会话就删除其此前有效资格，违背“至少一次”。
- 比较时使用严格小于而不是小于等于 maxTime。
- 把不同用户交错的 signin/signout 按全局栈匹配。
- 未说明重复登录、无匹配退出与乱序，直接写出貌似完整的通用解。
继续深挖
- 若同用户可重复 signin，匹配第一次、最近一次还是每个 signin 都形成会话？需先约定。
- 如果只需要过去 24 小时内有效会话用户，如何过期状态并处理撤销？
