Checkpoint: stacks, search, and intervals
54 / 170Checkpoint: stacks, search, and intervalsLesson 2 of 3About 125 min
One stack, one repair, one answer-space search, and two interval sweeps, with no labels.
Normalize an absolute Unix-style path, resolving . and .. and collapsing repeated slashes. You have written the core of this once already, in a reading rather than as a problem.
Remove the fewest parentheses so the string becomes valid, keeping everything else in place. Deciding which ones to remove is the work, and a stack of positions rather than characters is the hint worth taking.
Split a sequence into at most k contiguous groups so that the largest group sum is as small as possible. Write down the candidate range, the feasibility test, and the monotonicity argument before you write any code.
Trips each pick up some passengers at one point and drop them at another. Decide whether the vehicle ever exceeds its capacity. The count going up and down by more than one at a time is the only change from what you already know.
Merge the overlapping intervals, then report the smallest gap left between consecutive merged blocks. You built both halves of this in a lab.