Quick Overview

Given open and close event logs in which each event has a timestamp, an order id and a batch id, answer queries for the start and end time of an order or of a whole batch. It tests careful handling of the earliest-start and latest-end rule for batches, the zero end for unclosed orders and efficient answers to many queries.

Order and Batch Time Spans from Open and Close Event Logs

Company: Hudson River Trading

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A system records the lifetime of orders in two event logs. The open log has one event for each order when it starts, and the close log has one event for each order when it finishes. Every event carries a timestamp, an order id and a batch id; a batch groups several orders. An existing function reads both logs and reports when an order started and ended. Extend it so that a query can name either an order or a batch: - For an order, report its open time and its close time. - For a batch, report the earliest open time and the latest close time among its orders. - An end time of 0 means "not closed yet": an order without a close event has end 0, and so does a batch that contains at least one such order. The task was given verbally and its exact semantics took several clarifying questions to pin down; this version fixes them in Rules below and passes the two logs in as lists. ### Function Signature ```python def query_spans(open_events: list[list[int]], close_events: list[list[int]], queries: list[list[int]]) -> list[list[int]]: ``` ### Rules - Every event in `open_events` and `close_events` is `[timestamp, order_id, batch_id]`. - Every query is `[kind, id]`. `kind = 0` asks about the order whose order id is `id`; `kind = 1` asks about the batch whose batch id is `id`. - For an order query the answer is `[start, end]`: `start` is the order's open timestamp, and `end` is its close timestamp, or 0 if the order has no close event. - For a batch query, `start` is the smallest open timestamp among the batch's orders. If every order of the batch has a close event, `end` is the largest close timestamp among them; otherwise `end` is 0. - Order ids and batch ids are separate: the same number may be an order id and a batch id at once, and the query's `kind` decides which one is meant. - Events in each list may appear in any order. - Return one `[start, end]` pair per query, in the order of `queries`. ### Constraints - `1 <= len(open_events) <= 10^5` - `0 <= len(close_events) <= len(open_events)` - `1 <= len(queries) <= 10^5` - `1 <= timestamp <= 10^9` and `1 <= order_id, batch_id <= 10^9`; because timestamps are at least 1, an end of 0 is never a real close time. - Each order id appears in exactly one open event and in at most one close event. - Every close event matches an open event with the same order id and the same batch id, and its timestamp is greater than or equal to that open event's timestamp. - `kind` is 0 or 1, and every queried id exists in `open_events` as an order id (for `kind = 0`) or as a batch id (for `kind = 1`). ### Examples **Example 1** ```text Input: open_events = [[10, 1, 100], [12, 2, 100], [15, 3, 200]] close_events = [[20, 1, 100], [18, 2, 100]] queries = [[0, 1], [0, 3], [1, 100], [1, 200]] Output: [[10, 20], [15, 0], [10, 20], [15, 0]] ``` Order 1 opened at 10 and closed at 20. Order 3 has no close event, so its end is 0. Batch 100 holds orders 1 and 2: the earliest open is 10 and the latest close is `max(20, 18) = 20`. Batch 200 holds only order 3, which is still open. **Example 2** ```text Input: open_events = [[5, 7, 7], [3, 8, 7]] close_events = [[9, 7, 7]] queries = [[1, 7], [0, 7], [0, 8]] Output: [[3, 0], [5, 9], [3, 0]] ``` The number 7 is both an order id and a batch id. Batch 7 holds orders 7 and 8: the earliest open is 3, and because order 8 has no close event, the batch's end is 0 even though order 7 closed at 9.

Overview: Given open and close event logs in which each event has a timestamp, an order id and a batch id, answer queries for the start and end time of an order or of a whole batch. It tests careful handling of the earliest-start and latest-end rule for batches, the zero end for unclosed orders and efficient answers to many queries.

Read the full Hudson River Trading Software Engineer interview experience this question came from

A system records the lifetime of orders in two event logs. `open_events` holds one event for each order when it starts, and `close_events` holds one event for each order when it finishes. Every event is `[timestamp, order_id, batch_id]`; a batch groups several orders. Each query is `[kind, id]` and names either an order or a batch: - `kind = 0` asks about the order whose order id is `id`. The answer is `[start, end]`: `start` is the order's open timestamp, and `end` is its close timestamp, or `0` if the order has no close event. - `kind = 1` asks about the batch whose batch id is `id`. `start` is the smallest open timestamp among the batch's orders. If every order of the batch has a close event, `end` is the largest close timestamp among them; otherwise `end` is `0`. An end of `0` means "not closed yet": an order without a close event has end `0`, and so does a batch that contains at least one such order. Order ids and batch ids are separate: the same number may be an order id and a batch id at once, and the query's `kind` decides which one is meant. Events in each list may appear in any order. Return one `[start, end]` pair per query, in the order of `queries`. Every timestamp and id is at most 10^9, so every input and output value fits in a signed 32-bit integer (none exceeds 2^31 - 1); `int` is enough in Java and C++. ### Constraints - `1 <= len(open_events) <= 10^5` - `0 <= len(close_events) <= len(open_events)` - `1 <= len(queries) <= 10^5` - `1 <= timestamp <= 10^9` and `1 <= order_id, batch_id <= 10^9`; because timestamps are at least 1, an end of 0 is never a real close time. - Each order id appears in exactly one open event and in at most one close event. - Every close event matches an open event with the same order id and the same batch id, and its timestamp is greater than or equal to that open event's timestamp. - `kind` is 0 or 1, and every queried id exists in `open_events` as an order id (for `kind = 0`) or as a batch id (for `kind = 1`). ### Example 1 ```text Input: open_events = [[10, 1, 100], [12, 2, 100], [15, 3, 200]] close_events = [[20, 1, 100], [18, 2, 100]] queries = [[0, 1], [0, 3], [1, 100], [1, 200]] Output: [[10, 20], [15, 0], [10, 20], [15, 0]] ``` Order 1 opened at 10 and closed at 20. Order 3 has no close event, so its end is 0. Batch 100 holds orders 1 and 2: the earliest open is 10 and the latest close is `max(20, 18) = 20`. Batch 200 holds only order 3, which is still open. ### Example 2 ```text Input: open_events = [[5, 7, 7], [3, 8, 7]] close_events = [[9, 7, 7]] queries = [[1, 7], [0, 7], [0, 8]] Output: [[3, 0], [5, 9], [3, 0]] ``` The number 7 is both an order id and a batch id. Batch 7 holds orders 7 and 8: the earliest open is 3, and because order 8 has no close event, the batch's end is 0 even though order 7 closed at 9.

Constraints

  • 1 <= len(open_events) <= 10^5
  • 0 <= len(close_events) <= len(open_events)
  • 1 <= len(queries) <= 10^5
  • 1 <= timestamp <= 10^9 and 1 <= order_id, batch_id <= 10^9; because timestamps are at least 1, an end of 0 is never a real close time.
  • Each order id appears in exactly one open event and in at most one close event.
  • Every close event matches an open event with the same order id and the same batch id, and its timestamp is greater than or equal to that open event's timestamp.
  • kind is 0 or 1, and every queried id exists in open_events as an order id (for kind = 0) or as a batch id (for kind = 1).

Examples

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

Expected Output: [[5, 0], [5, 0]]

Explanation: Minimum valid input: one open event, no close events, one query of each kind; 1 is both the order id and the batch id, and both answers end at 0.

Input: ([[10, 1, 100], [12, 2, 100], [15, 3, 200]], [[20, 1, 100], [18, 2, 100]], [[0, 1], [0, 3], [1, 100], [1, 200]])

Expected Output: [[10, 20], [15, 0], [10, 20], [15, 0]]

Explanation: Example 1: batch 100 spans min open 10 to max(20, 18) = 20; order 3 and its single-order batch 200 are still open.

Hints

  1. A batch's end is 0 as soon as any one of its orders lacks a close event, no matter how many of its other orders have closed.
  2. Order ids and batch ids are separate namespaces: keep what you know about orders apart from what you know about batches, so that a query's kind alone decides which one it reads.
  3. Neither log is sorted, so a batch's start and end must come from comparing values across all of its orders, not from where an event sits in a list.

Loading coding console...

Show the approach

Approach

Precompute every answer with hash maps, then answer each query in O(1).

  1. One pass over close_events maps each order id to its close timestamp (each order closes at most once, so this map is exact).
  2. One pass over open_events gives each order its span [open timestamp, close timestamp or 0]. Each order also folds into its batch record: the minimum open timestamp, the maximum end seen, and an 'unclosed' flag set as soon as any order of the batch has no close event.
  3. An order query (kind 0) reads the order map. A batch query (kind 1) returns [min open, 0] when the unclosed flag is set, and [min open, max close] otherwise.

Invariant: after any prefix of open_events, each batch record summarizes exactly the orders of that batch seen so far. Min, max and logical OR do not depend on the order of their inputs, so after the full pass every record summarizes the whole batch no matter how either log is ordered. When the flag is clear, every order in the batch has a close timestamp of at least 1, so the stored maximum is the latest close. When the flag is set, the stored maximum is ignored, so a later close can never overwrite the required 0. Order records and batch records live in separate maps, so a number that is both an order id and a batch id is resolved by kind alone.

Edge cases: an empty close_events (every end is 0); a close timestamp equal to its open timestamp (a real close, never confused with 0 because timestamps are at least 1); single-order batches; one batch holding every order; and repeated queries, each answered independently in query order. All values are at most 10^9, so 32-bit integers suffice.

Time complexity:
O(n + m + q), where n = len(open_events), m = len(close_events), q = len(queries)
Space complexity:
O(n + q)