Block-Building Operations: Check Whether a Free Segment Starts at a Position
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Positions on a number line start out empty. Process a list of operations in order:
- `[1, x]`: build a block at position `x`.
- `[2, x, k]`: check whether something of length `k` can be built starting at position `x`, meaning that positions `x, x + 1, ..., x + k - 1` hold no block. Record `"1"` if all of them are free and `"0"` otherwise. A check builds nothing.
Return the recorded characters concatenated in the order of the checks.
### Function Signature
```python
def process_operations(operations: list[list[int]]) -> str:
```
### Rules
- Building at a position that already holds a block changes nothing.
- A check depends only on blocks built by earlier operations in the list.
- Only positions `x` through `x + k - 1` matter for a check; blocks at `x - 1` or `x + k` do not make it fail.
- Return the empty string if there are no checks.
### Constraints
- `1 <= len(operations) <= 10^5`
- Each operation is either `[1, x]` or `[2, x, k]`.
- `1 <= x <= 10^9` and `1 <= k <= 10^9`, so `x + k - 1 <= 2 * 10^9 - 1`, which fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: operations = [[1, 2], [1, 5], [2, 3, 2], [2, 3, 3], [2, 1, 1], [2, 1, 2]]
Output: "1010"
```
Blocks stand at 2 and 5. Positions 3 and 4 are free: `"1"`. Positions 3, 4 and 5 include the block at 5: `"0"`. Position 1 is free: `"1"`. Positions 1 and 2 include the block at 2: `"0"`.
**Example 2**
```text
Input: operations = [[2, 10, 5], [1, 12], [1, 12], [2, 10, 2], [2, 10, 3], [2, 13, 100]]
Output: "1101"
```
The first check runs before any block exists: `"1"`. The second build at 12 changes nothing. Positions 10 and 11 are free: `"1"`. Positions 10 to 12 include the block at 12: `"0"`. Positions 13 to 112 are free, and the block at 12 just before them does not matter: `"1"`.
**Example 3**
```text
Input: operations = [[1, 1]]
Output: ""
```
There are no checks.
Overview: Process operations on a number line that either place a block at a position or ask whether a segment of a given length starting at a position is free of blocks, and return the answers as a string of ones and zeros. It tests handling interleaved updates and range checks efficiently over large coordinates.
Read the full Capital One Software Engineer interview experience this question came from
Positions on a number line start out empty. You are given a list `operations` and must process the operations in order. Each operation is one of the following:
- `[1, x]`: build a block at position `x`.
- `[2, x, k]`: check whether something of length `k` can be built starting at position `x`, meaning that positions `x, x + 1, ..., x + k - 1` hold no block. Record `"1"` if all of them are free and `"0"` otherwise. A check builds nothing.
Return the recorded characters concatenated in the order of the checks.
Rules:
- Building at a position that already holds a block changes nothing.
- A check depends only on blocks built by earlier operations in the list.
- Only positions `x` through `x + k - 1` matter for a check; blocks at `x - 1` or `x + k` do not make it fail.
- Return the empty string if there are no checks.
Constraints:
- `1 <= len(operations) <= 10^5`
- Each operation is either `[1, x]` or `[2, x, k]`.
- `1 <= x <= 10^9` and `1 <= k <= 10^9`, so `x + k - 1 <= 2 * 10^9 - 1`. Every value, including `x + k - 1`, fits in a 32-bit signed integer (none exceeds 2^31 - 1).
Example 1:
Input: operations = [[1, 2], [1, 5], [2, 3, 2], [2, 3, 3], [2, 1, 1], [2, 1, 2]]
Output: "1010"
Explanation: Blocks stand at 2 and 5. Positions 3 and 4 are free: "1". Positions 3, 4 and 5 include the block at 5: "0". Position 1 is free: "1". Positions 1 and 2 include the block at 2: "0".
Example 2:
Input: operations = [[2, 10, 5], [1, 12], [1, 12], [2, 10, 2], [2, 10, 3], [2, 13, 100]]
Output: "1101"
Explanation: The first check runs before any block exists: "1". The second build at 12 changes nothing. Positions 10 and 11 are free: "1". Positions 10 to 12 include the block at 12: "0". Positions 13 to 112 are free, and the block at 12 just before them does not matter: "1".
Constraints
- 1 <= len(operations) <= 10^5
- Each operation is either [1, x] or [2, x, k]
- 1 <= x <= 10^9
- 1 <= k <= 10^9
- x + k - 1 <= 2 * 10^9 - 1, which fits in a 32-bit signed integer
Examples
Input: ([[1, 2], [1, 5], [2, 3, 2], [2, 3, 3], [2, 1, 1], [2, 1, 2]],)
Expected Output: '1010'
Explanation: Source example 1: blocks at 2 and 5; windows 3..4 and 1..1 are free, 3..5 and 1..2 are not.
Input: ([[2, 10, 5], [1, 12], [1, 12], [2, 10, 2], [2, 10, 3], [2, 13, 100]],)
Expected Output: '1101'
Explanation: Source example 2: a check before any build, a repeated build, and a block at x - 1 (12 for window 13..112) that does not fail the check.
Hints
- A check fails exactly when at least one block built by an earlier operation lies in the closed range from x to x + k - 1, so think about the blocks rather than about every position in the window.
- k can be as large as 10^9, so visiting every position in a window one by one is far too slow.
- Only earlier operations count, and building where a block already stands adds nothing: process the list strictly in order.