Quick Overview

Process chronological sign-in and sign-out logs to find users with any completed session at or below a maximum duration.

Find Users with at Least One Session Within a Duration Limit

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given chronological sign-in and sign-out logs and a maximum session duration, return every user who has at least one completed session whose duration is at most the maximum. ### Function Signature `users_with_short_sessions(logs: list[list[int]], max_time: int) -> list[int]` ### Input Each log is `[user_id, timestamp, action]`, where `action = 0` means sign in and `action = 1` means sign out. Timestamps are integer seconds and are nondecreasing across the input. For equal timestamps, process logs in input order. For this exercise, each user starts signed out, their actions alternate between sign in and sign out, and every sign-in has a later matching sign-out in input order. Users may have multiple sessions, and sessions of different users may overlap. These validity rules remove unspecified malformed-log behavior. ### Output Return qualifying user IDs exactly once, sorted in ascending numerical order. A user qualifies if any session has `sign_out_timestamp - sign_in_timestamp <= max_time`. Return an empty list if no user qualifies. ### Constraints - `0 <= len(logs) <= 200000`. - `0 <= user_id <= 1000000000`. - `0 <= timestamp <= 1000000000`. - `0 <= max_time <= 1000000000`. - A session may have zero duration. ### Examples Input: `logs = [[7,1,0],[2,2,0],[7,6,1],[2,20,1],[2,21,0],[2,23,1]], max_time = 5` Output: `[2,7]` User 7 qualifies with duration 5. User 2's first session is too long, but the second has duration 2. Input: `logs = [[3,10,0],[3,10,1]], max_time = 0` Output: `[3]` Input: `logs = [], max_time = 10` Output: `[]`

Overview: Process chronological sign-in and sign-out logs to find users with any completed session at or below a maximum duration.

You are given chronological sign-in and sign-out logs for a set of users, plus a maximum session duration `max_time`. Return every user who has at least one completed session whose duration is at most `max_time`. Each log is `[user_id, timestamp, action]`, where `action = 0` means sign in and `action = 1` means sign out. Timestamps are integer seconds and are nondecreasing across the input. For equal timestamps, process the logs in input order. For this exercise the logs are well formed: each user starts signed out, that user's actions alternate between sign in and sign out, and every sign-in has a later matching sign-out in input order. Users may have multiple sessions, and sessions of different users may overlap. A session's duration is `sign_out_timestamp - sign_in_timestamp`, and a session may have zero duration. Return the qualifying user IDs exactly once each, sorted in ascending numerical order. A user qualifies if any of that user's sessions satisfies `sign_out_timestamp - sign_in_timestamp <= max_time`. Return an empty list if no user qualifies. All user IDs, timestamps, durations, and `max_time` are at most 1000000000, so every value fits in a signed 32-bit integer; no 64-bit type is required. Example 1: Input: `logs = [[7,1,0],[2,2,0],[7,6,1],[2,20,1],[2,21,0],[2,23,1]]`, `max_time = 5` Output: `[2,7]` User 7 qualifies with duration `6 - 1 = 5`. User 2's first session lasts `20 - 2 = 18` and is too long, but the second lasts `23 - 21 = 2`, so user 2 qualifies as well. The IDs are returned in ascending numerical order. Example 2: Input: `logs = [[3,10,0],[3,10,1]]`, `max_time = 0` Output: `[3]` The single session has duration `10 - 10 = 0`, which is at most `max_time = 0`.

Constraints

  • 0 <= len(logs) <= 200000.
  • Each log is [user_id, timestamp, action], where action = 0 means sign in and action = 1 means sign out.
  • 0 <= user_id <= 1000000000.
  • 0 <= timestamp <= 1000000000.
  • 0 <= max_time <= 1000000000.
  • Timestamps are nondecreasing across the input; for equal timestamps, process the logs in input order.
  • Each user starts signed out, that user's actions alternate between sign in and sign out, and every sign-in has a later matching sign-out in input order.
  • Users may have multiple sessions, and sessions of different users may overlap.
  • A session may have zero duration.
  • Every value fits in a signed 32-bit integer; no value can exceed 2^31 - 1.

Examples

Input: ([], 10)

Expected Output: []

Explanation: No logs means no completed session, so the answer is the empty list.

Input: ([[1, 0, 0], [1, 3, 1]], 5)

Expected Output: [1]

Explanation: User 1 has one session of duration 3 - 0 = 3, which is at most 5.

Hints

  1. Only one session per user is open at any moment, so you never need to remember more than one unmatched timestamp per user while scanning.
  2. A user is decided by its best session, not its first one: keep scanning after a long session, and make sure a user that has several short sessions is still reported only once.
  3. The required output order is numerical on the user ID; it is unrelated to the order in which users appear in the logs.

Loading coding console...

Show the approach

Approach

Algorithm: scan the logs once in input order, keeping a map pending from user ID to the timestamp of that user's currently open sign-in, and a set qualifying of user IDs already known to have a short session. On a sign-in log (action = 0) store the timestamp for that user. On a sign-out log (action = 1) remove the user's pending timestamp, compute timestamp - start, and add the user to qualifying when that duration is at most max_time. Finally return the qualifying IDs in ascending numerical order.

Invariant: after processing a prefix of the logs, pending[u] holds the sign-in timestamp of user u's single open session (u is absent when u is signed out), and qualifying contains exactly the users with at least one completed session of duration at most max_time among the sessions closed in that prefix.

Correctness: the statement guarantees each user starts signed out and alternates sign in / sign out, so at most one session per user is open at a time and every sign-out closes the immediately preceding sign-in of that same user. Storing one timestamp per user therefore reconstructs exactly the intended pairing, and it is unaffected by other users' interleaved logs because the map is keyed by user. Processing the input array front to back honours the tie-break rule that equal timestamps are handled in input order. Each closed session is tested once against max_time with a <= comparison, matching the definition of qualifying, and membership in a set makes each qualifying user reported exactly once regardless of how many of its sessions are short. Sorting the set at the end produces the required ascending numerical order, which is independent of appearance order.

Edge cases: empty logs produces an empty map and set, hence []. A zero-duration session (sign_in == sign_out) yields duration 0 and qualifies for every max_time >= 0, including max_time = 0. A duration exactly equal to max_time qualifies; one greater does not. A long first session does not prevent a later short session from qualifying the same user. Deeply nested or interleaved sessions of distinct users are paired per user. All values are bounded by 1000000000, so durations never overflow 32-bit arithmetic and stay well inside the exact-integer range of IEEE-754 doubles in JavaScript.

Time complexity:
O(n + k log k), where n is the number of logs and k is the number of qualifying users (a single linear scan with expected O(1) map operations, plus the final sort).
Space complexity:
O(u), where u is the number of distinct users appearing in the logs (the pending map plus the qualifying set).