Katkat
Back

Data Center Rack Units: Can a Centered Equipment Bay Be Reserved?

RobloxSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Process an online stream of rack-unit reservations and span-availability checks over an infinite 1D coordinate line, answering each availability check with the data seen so far.

A data center numbers rack units along an infinite integer line (negative units are allowed; they represent units below a reference point). Initially no unit is reserved. Process a sequence of operations, in order:

  • ["reserve", x] — permanently reserves unit x. Guaranteed that x is not already reserved when this runs.
  • ["check", x, span] — asks whether an equipment bay centered on unit x, extending span - 1 units in each direction, could be installed without touching a reserved unit — i.e., whether every unit from x - (span - 1) to x + (span - 1) is currently free. This only answers the question; it never reserves anything.

Return the answers to every "check" operation, in order, concatenated into one string of "1" (free) and "0" (blocked).

Function signature

def check_bays(operations: list[list]) -> str:

Rules

  • A "check" only sees reservations made by operations before it in the list.
  • The checked range is inclusive on both ends and spans 2 * span - 1 units. With span = 1, only x itself is checked.
  • Each "check" contributes exactly one character to the output, in order. If there are no "check" operations, return "".

Examples

operations = [["reserve", 2], ["check", 0, 3], ["check", 0, 2],
              ["reserve", -5], ["check", -3, 3], ["check", -3, 2]]
output = "0101"

check(0, 3) covers -2..2 and hits the reservation at 2 → "0". check(0, 2) covers -1..1, clear → "1". After reserving -5, check(-3, 3) covers -5..-1 and hits it → "0"; check(-3, 2) covers -4..-2, clear → "1".

operations = [["check", 7, 1], ["reserve", 7], ["check", 7, 1]]
output = "10"

Constraints

  • 1 <= len(operations) <= 10^5
  • -10^9 <= x <= 10^9, 1 <= span <= 10^9
  • No unit is reserved twice.
  • All checked range endpoints fit comfortably in a 64-bit integer.

Hints

Hint 1

You only ever care about reserved units, which are sparse compared to the full coordinate range — don't build an array over the whole line.

Hint 2

Keep reserved units in a structure you can binary-search: if the smallest reserved unit at or above the range's low end is also at or below the range's high end, the range is blocked.

Hint 3

Python's `bisect` module gives you that search for free over a sorted list.

Hint 4

Think about what happens if you need this to scale past 10^5 operations with guaranteed O(log n) per call — coordinate-compress all `reserve` targets up front and back them with a Fenwick tree instead of a plain list.

Follow-up questions

  • How would you support releasing a reservation, and how does that change your data structure choice?
  • How would you answer 'what is the largest free span centered at x' instead of a yes/no check?
  • Walk through why the Fenwick-tree approach still needs the operations to be known in advance (offline), and what you'd do if reservations could target unit values never seen before the stream starts.
  • How would this change if reservations could cover a range of units instead of a single unit?