How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Applied Intuition.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Applied Intuition during technical interviews.

Design event timeout detector | Applied Intuition Coding Question

Design event timeout detector

Company: Applied Intuition

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Design and implement an event-timeout detector for a job scheduler. Inputs: a global timeout T and a stream of events; each event has {event_id, type ∈ {start, end, ping}, timestamp}. Behavior: an event times out if it has started, not ended, and now_ts − last_updated_ts > T; ping updates last_updated_ts; end removes the event from consideration. Provide APIs process(event) and get_timed_out(now_ts) → list[event_id]. Use efficient data structures (e.g., hash map plus LRU/min-heap) to support many concurrent events. State how you handle duplicates, out-of-order events, events without a prior start, multiple starts, and zero/negative timeouts, and analyze time/space complexity.

Quick Answer: This question evaluates a candidate's competency in designing efficient event-driven algorithms and time-based state management, including handling duplicates, out-of-order events, concurrent updates, and edge-case timeout semantics.

Implement an event-timeout detector for a job scheduler. You are given a global timeout `T` and a sequence of API calls. Each event has: - `event_id` (integer) - `type` in `{start, ping, end}` - `timestamp` (integer) An event is considered active after a `start` and remains active until a valid `end` is processed. Timeout rule: - An active event is timed out at time `now_ts` if `now_ts - last_updated_ts > T`. - `ping` updates `last_updated_ts`. - `end` removes the event from consideration. - A timed-out event stays timed out until it receives a newer `start`/`ping` or a valid `end`. Because this platform expects a single function, implement `solution(T, operations)` where: - `("process", event_id, type, timestamp)` means call `process(event)` - `("get", now_ts)` means call `get_timed_out(now_ts)` Return the result of every `get` call. Required behavior for tricky cases: - `ping` or `end` without a prior active `start`: ignore. - Duplicate or stale `start`/`ping` with `timestamp <=` the event's latest accepted timestamp: ignore. - A valid `end` for an active event is accepted only if `end.timestamp >= last_updated_ts`; otherwise it is stale and ignored. - Multiple `start` events: if the new `start` has a strictly larger timestamp, treat it as a restart/reset. - A new `start` after an `end` is allowed only if its timestamp is strictly larger than the last accepted timestamp for that event. - Zero or negative timeouts use the same strict rule `now_ts - last_updated_ts > T`. For deterministic output, each `get` must return currently timed-out `event_id`s in the order they became timed out; if multiple events become timed out on the same `get`, smaller `event_id` comes first.

Constraints

0 <= len(operations) <= 200000
event_id and timestamps are integers in the range [-10^9, 10^9]
type is one of 'start', 'ping', or 'end'
All `get` operations are given in non-decreasing `now_ts` order

Examples

Input: (5, [('process', 1, 'start', 0), ('process', 2, 'start', 1), ('process', 1, 'ping', 3), ('get', 6), ('process', 2, 'end', 7), ('get', 9)])

Expected Output: [[], [1]]

Explanation: At time 6, event 1 was updated at 3 and event 2 at 1, so neither satisfies `now - last_updated > 5`. After event 2 ends, time 9 makes event 1 timed out because `9 - 3 = 6 > 5`.

Input: (4, [('process', 10, 'start', 5), ('process', 10, 'ping', 3), ('process', 10, 'start', 5), ('process', 10, 'ping', 9), ('process', 10, 'end', 8), ('get', 13), ('get', 14)])

Expected Output: [[], [10]]

Explanation: The ping at 3 and repeated start at 5 are stale/duplicate and ignored. The end at 8 is stale because the latest accepted timestamp is 9. At time 13, `13 - 9 = 4` is not greater than 4, but at time 14 it is.

Input: (3, [('process', 1, 'end', 2), ('process', 1, 'start', 4), ('process', 1, 'start', 6), ('get', 9), ('get', 10), ('process', 1, 'start', 11), ('get', 11), ('get', 15)])

Expected Output: [[], [1], [], [1]]

Explanation: The first end is ignored because event 1 was never active. The second start at 6 restarts the event. It times out at time 10, then a newer start at 11 clears the timeout, and it times out again at 15.

Input: (-1, [('process', 2, 'start', 7), ('get', 7), ('process', 2, 'ping', 8), ('get', 8), ('process', 3, 'ping', 0), ('get', 8)])

Expected Output: [[2], [2], [2]]

Explanation: With `T = -1`, an active event satisfies the timeout rule immediately on the next `get` because `now - last_updated > -1`. The ping for event 3 is ignored because it never started.

Input: (2, [('process', 5, 'start', 0), ('process', 3, 'start', 1), ('process', 4, 'start', 0), ('get', 3), ('process', 5, 'ping', 4), ('get', 4), ('get', 7)])

Expected Output: [[4, 5], [4, 3], [4, 3, 5]]

Explanation: At time 3, events 4 and 5 time out together, and smaller `event_id` comes first. Event 5 is later refreshed by a ping, so it leaves the timed-out set. Event 3 then times out at time 4, and event 5 times out again at time 7.

Input: (0, [('process', 1, 'start', 10), ('get', 10), ('get', 11), ('process', 1, 'ping', 11), ('get', 11), ('process', 1, 'end', 11), ('get', 12)])

Expected Output: [[], [1], [], []]

Explanation: With `T = 0`, an event times out only when `now_ts` is strictly greater than its last update time. So it is not timed out at 10, is timed out at 11, the ping at 11 clears it, and the end at 11 removes it.

Solution

def solution(T, operations):
    import heapq
    from collections import OrderedDict

    # event_id -> [active, last_ts, version]
    states = {}
    heap = []  # (deadline, event_id, version)
    timed_out = OrderedDict()
    result = []

    for op in operations:
        if not op:
            continue

        if op[0] == 'process':
            _, event_id, event_type, ts = op
            state = states.get(event_id)

            if event_type == 'start':
                if state is None:
                    states[event_id] = [True, ts, 1]
                    heapq.heappush(heap, (ts + T, event_id, 1))
                else:
                    active, last_ts, version = state
                    if ts <= last_ts:
                        continue
                    version += 1
                    state[0] = True
                    state[1] = ts
                    state[2] = version
                    timed_out.pop(event_id, None)
                    heapq.heappush(heap, (ts + T, event_id, version))

            elif event_type == 'ping':
                if state is None:
                    continue
                active, last_ts, version = state
                if (not active) or ts <= last_ts:
                    continue
                version += 1
                state[1] = ts
                state[2] = version
                timed_out.pop(event_id, None)
                heapq.heappush(heap, (ts + T, event_id, version))

            elif event_type == 'end':
                if state is None:
                    continue
                active, last_ts, version = state
                if (not active) or ts < last_ts:
                    continue
                state[0] = False
                state[1] = ts
                timed_out.pop(event_id, None)

        elif op[0] == 'get':
            _, now_ts = op
            while heap and heap[0][0] < now_ts:
                deadline, event_id, version = heapq.heappop(heap)
                state = states.get(event_id)
                if state is None:
                    continue
                active, last_ts, current_version = state
                if not active or current_version != version:
                    continue
                if event_id not in timed_out:
                    timed_out[event_id] = None
            result.append(list(timed_out.keys()))

    return result

Time complexity: Overall O(m log m + total_output), where m is the number of operations. Each accepted start/ping adds one heap entry, and each heap entry is popped at most once.. Space complexity: O(m) in the worst case because the heap may contain stale entries from lazy deletion, plus O(n) event states..

Hints

Use a hash map to store the current state of each event: whether it is active, its latest accepted timestamp, and a version number.
Use a min-heap of expiration deadlines (`last_updated_ts + T`) plus lazy deletion so old heap entries do not need to be removed immediately.

Quick Overview

This question evaluates a candidate's competency in designing efficient event-driven algorithms and time-based state management, including handling duplicates, out-of-order events, concurrent updates, and edge-case timeout semantics.