Design ID allocator with resizable bucket ranges
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a fixed global ID space [0, 999] and an initial list of bucket specifications, where each bucket has a unique name and an inclusive ID range [start, end], implement two functions:
(
1) assign(buckets): validate and normalize the ranges so they are within bounds, non-overlapping, and returned as a sorted array of {name, start, end}; leave any unassigned IDs free.
(
2) resize(buckets, name, desired_size): adjust the array so bucket 'name' has exactly desired_size IDs by expanding or shrinking its range while preserving non-overlap and staying within [0, 999]. Prefer consuming immediately adjacent free space; if insufficient, borrow from neighboring buckets using a deterministic policy (e.g., take from the nearest bucket with the largest surplus). If the request cannot be satisfied, return an error. Describe your data structures, the time/space complexity of typical operations, and how you would handle concurrent calls or conflicting resize requests.
Quick Answer: This question evaluates a candidate's proficiency in interval and resource-allocation algorithms, deterministic conflict-resolution policies, data structure selection for range management, time/space complexity analysis, and concurrency control.