Rebalance shard ranges under overlap limit
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You maintain a set of data shards. Each shard owns an **inclusive** integer key range `[start, end]`.
```python
class Shard:
id: str
start: int
end: int
class Shards:
def __init__(self, limit: int):
# provided
...
def add_shard(self, shard: Shard):
# provided
...
def remove_shard(self, shard_id: str):
# provided
...
def rebalance(self):
# TODO
...
```
### Goal
Implement `rebalance()` so that after it runs, the shard ranges satisfy all of the following:
1. **Overlap constraint:** For every key `k`, the number of shards whose ranges contain `k` is **≤ `limit`**.
2. **No gaps within the global span:** Let `L = min(original starts)` and `R = max(original ends)` over the shards currently stored. After rebalancing, every key in `[L, R]` must be covered by **at least 1** shard.
3. **Minimize data movement heuristic (tie-breaking rule):** When you must adjust ranges to eliminate overlaps, prefer modifying the shard(s) that start **later** (i.e., with larger `start`) before modifying earlier shards. (Intuition: moving later ranges tends to move less data.)
4. **Valid ranges:** Every remaining shard must have `start <= end`. If a shard becomes empty (e.g., `start > end`) after adjustments, it should be removed.
You may reorder internal storage as needed, and you may modify shard `start/end`, remove shards, and/or create/extend ranges as needed to satisfy the constraints.
### Example
`limit = 1`
Input shards:
- `('A', 0, 100)`
- `('B', 80, 180)`
One valid rebalance result (using the “modify later shard first” rule):
- `('A', 0, 100)`
- `('B', 101, 180)`
Because keys `80..100` overlapped with `limit=1`, shard `B` (which starts later) is shifted to start at `101`.
### Notes / Constraints
- Shards may be provided in any order.
- Assume up to `N` shards (e.g., `N` can be large), and key values can be large integers.
- Define clearly in your implementation whether `rebalance()` returns the final list (for testing) or just mutates internal state (either is acceptable as long as it is consistent).
Quick Answer: This question evaluates skills in interval and range management, constraint enforcement, and algorithmic problem solving related to overlapping integer ranges and minimizing data movement when adjusting shard boundaries.
You are given a set of shards, each responsible for an **inclusive** integer key range `[start, end]`.
Due to historical changes, shards may:
- overlap too much (more than an allowed maximum), and/or
- leave gaps (keys not covered by any shard).
Your task is to rebalance the shards under a maximum overlap limit.
### Definitions
- A key `k` is *covered* by a shard `(id, start, end)` if `start <= k <= end`.
- The *overlap count* at key `k` is the number of shards that cover `k`.
### Rebalance rules
Given `limit`:
1. After rebalancing, for every integer key between `min_start` and `max_end` (computed from the original shards), the overlap count must satisfy:
- `1 <= overlap_count(k) <= limit`
2. To reduce data movement, you must resolve excessive overlap by **only moving shard starts to the right** (never modifying other shards to fix that overlap):
- If starting a shard at its current `start` would cause overlap to exceed `limit`, delay that shard by moving its `start` to `earliest_active_end + 1`, where `earliest_active_end` is the smallest `end` among shards currently covering the start position.
- Repeat delaying if needed.
- If delaying makes `start > end`, that shard becomes empty and must be removed.
3. After enforcing the overlap limit, fill any uncovered gaps within `[min_start, max_end]` by **extending shard ends to the right** (this does not increase overlap because gaps have 0 coverage):
- If there is a gap between covered keys, extend the shard that currently reaches farthest right to cover the gap.
Return the final set of shards as a list of tuples `(id, start, end)` sorted by `(start, id)`.