Return Log Entries Within an Inclusive Time Range From a Sorted Log
Company: Attentive
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a log that has already been loaded into memory as a list of entries. Each entry is a pair `(timestamp, message)`, where `timestamp` is an integer and `message` is a string. The entries are sorted by timestamp in non-decreasing order, and several entries may share the same timestamp.
Given `start_time` and `end_time`, return every entry whose timestamp `t` satisfies `start_time <= t <= end_time`.
### Function Signature
```python
def logs_in_range(logs: list[tuple[int, str]], start_time: int, end_time: int) -> list[tuple[int, str]]:
```
### Rules
- Both bounds are inclusive.
- Return the matching entries in the same order as they appear in `logs`. Because `logs` is sorted, the matching entries form one contiguous run of `logs`, and that run, in its original order, is the unique correct answer. Entries with equal timestamps keep their input order.
- Return each matching entry unchanged, as the same `(timestamp, message)` pair. Do not remove duplicates, even if two entries have the same timestamp and the same message.
- If no entry falls in the range, return an empty list. This includes the cases where `start_time` is greater than the largest timestamp, where `end_time` is smaller than the smallest timestamp, and where `logs` is empty.
- Do not modify `logs`.
### Constraints
- `0 <= len(logs) <= 10^5`
- `0 <= timestamp <= 10^9` for every entry
- `logs[i][0] <= logs[i + 1][0]` for every valid `i`
- `0 <= start_time <= end_time <= 10^9`
- Each message is a string of 1 to 100 printable ASCII characters. Messages need not be distinct.
- Every timestamp and bound fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: logs = [(1, "boot"), (3, "connect"), (3, "retry"), (5, "ready"), (8, "shutdown")]
start_time = 3, end_time = 5
Output: [(3, "connect"), (3, "retry"), (5, "ready")]
```
Both entries at timestamp `3` are included, and the entry at `5` is included because the end bound is inclusive.
**Example 2**
```text
Input: logs = [(2, "a"), (4, "b"), (6, "c")]
start_time = 7, end_time = 10
Output: []
```
`start_time` is greater than the largest timestamp, `6`, so nothing matches.
**Example 3**
```text
Input: logs = [(2, "a"), (2, "b"), (4, "c"), (6, "d")]
start_time = 0, end_time = 2
Output: [(2, "a"), (2, "b")]
```
The end bound equals the smallest timestamp, so both entries at timestamp `2` match.
Overview: Given an in-memory log sorted by integer timestamp, return every entry whose timestamp lies within an inclusive start and end time. The problem tests exact boundary handling with duplicate timestamps, empty results when the range misses the log, and locating a range efficiently in sorted data.
Read the full Attentive Software Engineer interview experience this question came from
You are given a log that has already been loaded into memory as a list `logs` of entries. Each entry is a pair `(timestamp, message)`, where `timestamp` is an integer and `message` is a string. The entries are sorted by timestamp in non-decreasing order, and several entries may share the same timestamp.
Given two integers `start_time` and `end_time`, return every entry whose timestamp `t` satisfies `start_time <= t <= end_time`.
Implement `logs_in_range(logs, start_time, end_time)`.
### Rules
- Both bounds are inclusive.
- Return the matching entries in the same order as they appear in `logs`. Because `logs` is sorted, the matching entries form one contiguous run of `logs`, and that run, in its original order, is the unique correct answer. Entries with equal timestamps keep their input order.
- Return each matching entry unchanged, as the same `(timestamp, message)` pair. Do not remove duplicates, even if two entries have the same timestamp and the same message.
- If no entry falls in the range, return an empty list. This includes the cases where `start_time` is greater than the largest timestamp, where `end_time` is smaller than the smallest timestamp, and where `logs` is empty.
- Do not modify `logs`.
### Entry representation
`logs` is passed as a single argument, a list of two-element entries, and the result uses the same entry shape:
- Python: a list of `(timestamp, message)` tuples.
- JavaScript: an array of `[timestamp, message]` arrays.
- Java: a `java.util.List<java.util.List<Object>>`; in each entry, element 0 is the timestamp (read it through `Number`) and element 1 is the `String` message.
- C++: a `std::vector<std::pair<int, std::string>>`.
Every timestamp and bound is at most 10^9 and fits in a 32-bit signed integer; no value exceeds 2^31 - 1, so `int` is sufficient in Java and C++.
### Constraints
- `0 <= len(logs) <= 10^5`
- `0 <= timestamp <= 10^9` for every entry
- `logs[i][0] <= logs[i + 1][0]` for every valid `i`
- `0 <= start_time <= end_time <= 10^9`
- Each message is a string of 1 to 100 printable ASCII characters. Messages need not be distinct.
- Every timestamp and bound fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: logs = [(1, "boot"), (3, "connect"), (3, "retry"), (5, "ready"), (8, "shutdown")]
start_time = 3, end_time = 5
Output: [(3, "connect"), (3, "retry"), (5, "ready")]
```
Both entries at timestamp `3` are included, and the entry at `5` is included because the end bound is inclusive.
**Example 2**
```text
Input: logs = [(2, "a"), (4, "b"), (6, "c")]
start_time = 7, end_time = 10
Output: []
```
`start_time` is greater than the largest timestamp, `6`, so nothing matches.
Constraints
- 0 <= len(logs) <= 10^5
- 0 <= timestamp <= 10^9 for every entry
- logs[i][0] <= logs[i + 1][0] for every valid i
- 0 <= start_time <= end_time <= 10^9
- Each message is a string of 1 to 100 printable ASCII characters. Messages need not be distinct.
- Every timestamp and bound fits in a 32-bit signed integer (no value exceeds 2^31 - 1).
Examples
Input: ([(1, 'boot'), (3, 'connect'), (3, 'retry'), (5, 'ready'), (8, 'shutdown')], 3, 5)
Expected Output: [(3, 'connect'), (3, 'retry'), (5, 'ready')]
Explanation: Source example 1: both entries at 3 and the entry at 5 match because both bounds are inclusive.
Input: ([(2, 'a'), (4, 'b'), (6, 'c')], 7, 10)
Expected Output: []
Explanation: Source example 2: start_time is greater than the largest timestamp.
Hints
- Because the entries are already sorted by timestamp, all of the matching entries sit next to each other in `logs`.
- Several entries can share a timestamp, including timestamps that equal `start_time` or `end_time` exactly; both bounds are inclusive, so none of those entries may be dropped.
- Return the matching entries exactly as they appear: same order, same pairs, duplicates included, and an empty list when nothing matches.