Toggle Inspection Ranges
Medium About 30 min Free, no account needed
Count the slots left on after overlapping range toggles when the board is too large to visit slot by slot.
The brief
An inspection board has numbered slots, all initially off. An operator selects ranges and flips every slot in each selected range. A second flip turns a slot off again. The board may contain more than two billion slots, while the command log is much smaller.
Implement long Solve(int[] ranges, int length). Slots are numbered 0 through length - 1. The array stores command pairs [start0, end0, start1, end1, ...]; each command flips the half-open range [start, end). Return how many slots are on after all commands.
With length 10 and commands [1, 6, 4, 8], slots 1, 2, 3, 6, 7 finish on, so return 5. Slots 4 and 5 were flipped twice. Two copies of any range cancel each other.
An empty range has no effect. Touching ranges do not overlap: [0, 3) and [3, 7) leave all seven slots on. Commands may appear in any order and may repeat.
The board length is between 0 and int.MaxValue, with at most 200,000 commands. The array has even length and every pair satisfies 0 <= start <= end <= length. Return 0 for no commands or a zero-length board. Preserve the caller's array; do not allocate storage proportional to the board length.
Starter code
using System;
public class Solution
{
public long Solve(int[] ranges, int length)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Intervals and sweep lines
- Sort or sweep interval boundaries, including difference arrays for range updates.
Related katas
- Partition Labels Medium Free Cut a string into the most pieces so no letter spans two pieces.
- Last Patch Wins Hard Free Recover the final contents of a strip after a long log of overlapping range assignments.
- Match Two Money Streams Hard Pro Allocate ordered payments across ordered invoices by intersecting their cumulative monetary spans.
- The Busiest Instant Hard Pro Find peak concurrency with a signed boundary sweep that respects half-open intervals and simultaneous handoffs.