Average Height of Buildings in Each Segment

Average Height of Buildings in Each Segment

What is this problem about?

The Average Height of Buildings in Each Segment interview question involves a set of buildings, each defined by a start position, an end position, and a height. Buildings can overlap. You need to divide the entire range into non-overlapping segments where the average height of buildings covering that segment is constant. This Average Height of Buildings in Each Segment coding problem is a coordinate-based sweep-line task.

Why is this asked in interviews?

Microsoft uses this to test a candidate's ability to handle interval-based data. It requires understanding how to "sweep" across a number line, tracking the cumulative sum of heights and the count of active buildings at every transition point. It's a more complex variation of the "Meeting Rooms" or "Skyline" problem.

Algorithmic pattern used

This utilizes the Array, Sorting, Heap (Priority Queue), Prefix Sum interview pattern, specifically the Sweep Line algorithm.

1. Collect all "start" and "end" points as events.
2. Sort events by coordinate.
3. Traverse the sorted coordinates. At each step, update the total_height and building_count.
4. If the building_count > 0, the average height for the segment between the current and previous coordinate is total_height / building_count.
5. Merge adjacent segments if they have the same average height.

Example explanation

Building 1: [1, 5, height 10], Building 2: [3, 8, height 20].

• Segment [1, 3]: Only Bldg 1. Total H=10, Count=1. Avg=10.
• Segment [3, 5]: Both Bldg 1 & 2. Total H=30, Count=2. Avg=15.
• Segment [5, 8]: Only Bldg 2. Total H=20, Count=1. Avg=20. Result segments: [1, 3, avg 10], [3, 5, avg 15], [5, 8, avg 20].

Common mistakes candidates make

• Not Merging Segments: Failing to combine consecutive segments that happen to have the same average height.
• Incorrect Event Handling: Not correctly adding/subtracting heights when multiple buildings start or end at the exact same coordinate.
• Precision Issues: Using floating-point numbers when the problem might require integer division or specific rounding.

Interview preparation tip

Master the "Difference Array" or "Sweep Line" technique. It is the go-to pattern for any problem involving intervals, overlaps, or changes in state across a 1D timeline.