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
- 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.
- 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.
- 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.