Design adjustable ID allocator
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
You manage a fixed global integer ID space `[0, 999]` (1000 IDs total) and a set of named buckets. Each bucket has a unique name and occupies a contiguous, inclusive range of IDs `[start, end]`. Ranges must always stay non-overlapping, in bounds, and (depending on the variant) in a fixed order; any IDs not owned by a bucket are considered free. Design the data structures and APIs, then implement the following operations.
1. **Initial allocation / assignment.** Implement an operation that takes the initial bucket specifications and assigns each bucket a valid contiguous range. Support both common framings:
- Given a list of `(name, desired_size)` in a fixed order, pack the buckets contiguously from low IDs to high IDs, preserving the given order, and return `[(name, start_id, end_id), ...]`. Fail with a clear error if the sum of desired sizes exceeds 1000 (capacity).
- Given a list of buckets that already carry proposed `[start, end]` ranges, validate and normalize them so they are within `[0, 999]`, non-overlapping, and returned sorted by start. Leave any unassigned IDs free (allow gaps between buckets).
2. **Resize a bucket.** Implement `resize(name, new_desired_size)` (or `resize(buckets, name, desired_size)`) that grows or shrinks the named bucket so it owns exactly `new_desired_size` IDs, while keeping every range contiguous, disjoint, in bounds, and (where required) in order:
- When growing, prefer consuming immediately adjacent free space first.
- If adjacent free space is insufficient, recover space by minimally shifting only the neighboring ranges, or by borrowing from neighboring buckets using a deterministic policy (e.g., take from the nearest bucket that has the largest surplus). Shifts/borrows must be the minimum needed to satisfy the request.
- When shrinking, return the freed IDs to the free pool (or to neighbors per policy).
- If the request cannot be satisfied within total capacity, return a clear, well-defined error and leave the layout unchanged.
3. **Analysis and follow-ups.**
- State the data structures you chose and the time/space complexity of each operation.
- Describe how you would test boundary cases: empty bucket list, a zero-size bucket, full utilization (sum == 1000), expansions that would overflow capacity, resizing the first/last bucket, and resizing a non-existent name.
- Discuss how you would handle concurrent or conflicting `resize` calls (e.g., locking, optimistic versioning, or a deterministic ordering/serialization of requests).
Quick Answer: A Pinterest software-engineer onsite coding problem: design an adjustable ID allocator over a fixed [0, 999] ID space with named, contiguous, non-overlapping bucket ranges. It covers initial allocation (packing from desired sizes and validating/normalizing proposed ranges), a resize operation that grows or shrinks a bucket by consuming adjacent free space and then minimally shifting or borrowing from neighbors under a deterministic policy, plus complexity analysis, boundary-case testing, and concurrency handling.
Adjustable ID Allocator — Pack Buckets Contiguously
You manage a fixed global integer ID space `[0, 999]` (1000 IDs total). Given a list of `(name, desired_size)` buckets in a fixed order, pack them contiguously from low IDs to high IDs, preserving the given order.
Return a list `[[name, start_id, end_id], ...]` where each non-empty bucket owns the inclusive range `[start_id, end_id]` (so `size = end_id - start_id + 1`). The first bucket starts at ID `0`, and each subsequent bucket starts right after the previous one ends — no gaps.
Rules:
- A bucket with `desired_size == 0` owns no IDs; represent it as `[name, -1, -1]` and do not advance the cursor.
- If any `desired_size` is negative, raise a `ValueError`.
- If the sum of all desired sizes exceeds the capacity `1000`, raise a `ValueError` (the allocation is infeasible).
Example: `[['a', 100], ['b', 200], ['c', 50]]` -> `[['a', 0, 99], ['b', 100, 299], ['c', 300, 349]]`.
Constraints
- ID space is fixed at [0, 999] (capacity = 1000).
- 0 <= number of buckets.
- Each desired_size is an integer >= 0; a negative size is an error.
- Buckets are packed in the given order with no gaps.
- Sum of all desired sizes must be <= 1000, otherwise the allocation fails.
Examples
Input: [['a', 100], ['b', 200], ['c', 50]]
Expected Output: [['a', 0, 99], ['b', 100, 299], ['c', 300, 349]]
Explanation: a takes IDs 0-99 (100 IDs), b takes 100-299 (200 IDs), c takes 300-349 (50 IDs), packed contiguously with no gaps.
Input: []
Expected Output: []
Explanation: No buckets to place; the entire ID space stays free and the result is empty.
Input: [['only', 1000]]
Expected Output: [['only', 0, 999]]
Explanation: A single bucket consumes the full capacity exactly, owning every ID from 0 to 999.
Input: [['x', 0], ['y', 10]]
Expected Output: [['x', -1, -1], ['y', 0, 9]]
Explanation: Zero-size bucket x owns no IDs and does not advance the cursor, so y still starts at 0.
Input: [['p', 1], ['q', 1], ['r', 1]]
Expected Output: [['p', 0, 0], ['q', 1, 1], ['r', 2, 2]]
Explanation: Three size-1 buckets get single consecutive IDs 0, 1, and 2.
Hints
- Keep a running cursor that points at the next free ID, starting at 0.
- For a bucket of size s, it owns [cursor, cursor + s - 1], then advance cursor past its end.
- Validate feasibility (sum <= 1000) before laying anything out so the operation is all-or-nothing.
- A zero-size bucket owns no IDs and must not advance the cursor.
Adjustable ID Allocator — Resize a Bucket (Minimal Shift)
You are given a packed layout of buckets over the ID space `[0, 999]`: a list `[[name, start, end], ...]` in order, with each non-empty bucket owning the inclusive range `[start, end]` and no gaps between consecutive non-empty buckets (an empty bucket is `[name, -1, -1]`). Implement `resize(buckets, name, new_size)` that makes the named bucket own exactly `new_size` IDs while keeping the layout contiguous, disjoint, in bounds, and in order.
Policy (deterministic minimal shift):
- Compute the change `delta = new_size - current_size`. If `delta == 0`, return the layout unchanged.
- Check feasibility against the WHOLE layout first: if `total_size - current_size + new_size > 1000`, raise a `ValueError` and leave the layout unchanged (all-or-nothing).
- When growing, the target keeps its start and extends its end; every bucket after it shifts right by exactly `delta` so the layout stays packed.
- When shrinking, the target keeps its start and pulls its end in; every bucket after it shifts left so the freed IDs are reclaimed. Shrinking to `0` makes the target empty (`[-1, -1]`).
- If `name` is not present, raise a `KeyError`. A negative `new_size` is a `ValueError`.
Return the new layout as `[[name, start, end], ...]`.
Example: resizing `a` from 100 to 150 in `[['a', 0, 99], ['b', 100, 299], ['c', 300, 349]]` shifts b and c right by 50 -> `[['a', 0, 149], ['b', 150, 349], ['c', 350, 399]]`.
Constraints
- ID space is fixed at [0, 999] (capacity = 1000).
- Input layout is packed and in order; an empty bucket is [name, -1, -1].
- new_size is an integer >= 0; negative is an error.
- Feasibility is checked globally (total - current + new_size <= 1000) before mutating.
- Resizing a non-existent name is an error; a rejected resize leaves the layout unchanged.
Examples
Input: ([['a', 0, 99], ['b', 100, 299], ['c', 300, 349]], 'a', 150)
Expected Output: [['a', 0, 149], ['b', 150, 349], ['c', 350, 399]]
Explanation: Grow a by 50: a now owns 0-149, and b and c each shift right by 50 to stay packed.
Input: ([['a', 0, 99], ['b', 100, 299], ['c', 300, 349]], 'a', 50)
Expected Output: [['a', 0, 49], ['b', 50, 249], ['c', 250, 299]]
Explanation: Shrink a by 50: a now owns 0-49 and the freed 50 IDs are reclaimed by shifting b and c left.
Input: ([['a', 0, 99], ['b', 100, 299], ['c', 300, 349]], 'c', 700)
Expected Output: [['a', 0, 99], ['b', 100, 299], ['c', 300, 999]]
Explanation: Grow the last bucket c from 50 to 700 IDs: it extends to 999, consuming the free tail. Total = 100+200+700 = 1000, exactly at capacity.
Input: ([['a', 0, 99], ['b', 100, 299], ['c', 300, 349]], 'b', 0)
Expected Output: [['a', 0, 99], ['b', -1, -1], ['c', 100, 149]]
Explanation: Shrink b to zero: b becomes empty and c shifts left to start right after a, reclaiming all of b's former IDs.
Input: ([['a', 0, 99], ['b', 100, 299], ['c', 300, 349]], 'a', 100)
Expected Output: [['a', 0, 99], ['b', 100, 299], ['c', 300, 349]]
Explanation: Resizing a to its current size (delta = 0) is a no-op; the layout is returned unchanged.
Input: ([['a', 0, 499]], 'a', 1000)
Expected Output: [['a', 0, 999]]
Explanation: Grow the only bucket from 500 to 1000 IDs: it consumes the entire universe 0-999, exactly at capacity.
Hints
- First find the target bucket and compute delta = new_size - current_size.
- Validate against the entire layout, not just the adjacent gap: total - current_size + new_size must be <= 1000.
- On grow or shrink, the target keeps its start; only its end moves and the suffix re-packs.
- Re-pack everything after the target from a single cursor so the layout stays contiguous and ordered.
- Shrinking to 0 turns the bucket into [name, -1, -1] and the cursor continues from where it would have started.