How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Compute city skyline outline | Google Coding Question

Q: Compute city skyline outline

This question evaluates a candidate's understanding of interval processing and skyline/contour computation within computational geometry, focusing on reasoning about overlapping ranges and height aggregation.

Compute city skyline outline

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a list of rectangular buildings in a 2D city skyline. Each building is represented by three integers `[L, R, H]`: - `L`: the x-coordinate of the left edge of the building, - `R`: the x-coordinate of the right edge of the building (`L < R`), - `H`: the height of the building. All buildings stand on a flat horizontal line (y = 0) and extend vertically up to height `H`. Buildings may overlap in the x-dimension. Your task is to compute the *skyline* formed by these buildings, as seen from a distance. The skyline should be represented as a list of **key points** `[x, height]` that describe the outer contour of the union of all buildings. A **key point** is a point where the height of the skyline changes. The output list must satisfy all of the following: 1. The list is sorted by increasing `x`. 2. No two consecutive points have the same height (i.e., the height must change at each key point). 3. The first point has a height greater than 0. 4. The last point has height 0, marking the end of the skyline. ### Input - An integer `n` — the number of buildings. - A list of `n` buildings, where each building is given as a triple `[L, R, H]` of integers. You may assume: - `1 <= n <= 10^4` - `0 <= L < R <= 10^9` - `1 <= H <= 10^9` ### Output Return a list of key points representing the skyline. Each key point is a pair `[x, height]` (or a 2-element array/tuple) of integers. ### Example Input: - `n = 3` - buildings = `[[2, 9, 10], [3, 7, 15], [5, 12, 12]]` One valid output: - `[[2, 10], [3, 15], [7, 12], [12, 0]]` Explanation (informal): - From x = 2 to 3, the highest building has height 10. - From x = 3 to 7, the highest building has height 15. - From x = 7 to 12, the remaining highest building has height 12. - After x = 12, there are no buildings, so the height drops to 0. Design an algorithm to compute the skyline key points for the given buildings.

Quick Answer: This question evaluates a candidate's understanding of interval processing and skyline/contour computation within computational geometry, focusing on reasoning about overlapping ranges and height aggregation.

You are given a list of rectangular buildings in a 2D city skyline. Each building is represented by three integers `[L, R, H]` where `L` is the x-coordinate of the left edge, `R` the x-coordinate of the right edge (`L < R`), and `H` the height. All buildings stand on the line y = 0 and may overlap in the x-dimension. Compute the *skyline* — the outer contour of the union of all buildings — as a list of **key points** `[x, height]`, where each key point marks a position at which the skyline height changes. The output must satisfy: 1. Sorted by increasing `x`. 2. No two consecutive points share the same height. 3. The first point has height > 0. 4. The last point has height 0, marking the end of the skyline. **Input:** an integer `n` (number of buildings) and a list of `n` triples `[L, R, H]`. **Output:** the list of key points `[x, height]`. **Constraints:** `1 <= n <= 10^4`, `0 <= L < R <= 10^9`, `1 <= H <= 10^9`. Example: buildings `[[2,9,10],[3,7,15],[5,12,12]]` -> `[[2,10],[3,15],[7,12],[12,0]]`.

Constraints

1 <= n <= 10^4
0 <= L < R <= 10^9
1 <= H <= 10^9
Each building is a triple [L, R, H] of integers.
Output must be sorted by x, with no two consecutive equal heights, first height > 0, last height = 0.

Examples

Input: (3, [[2, 9, 10], [3, 7, 15], [5, 12, 12]])

Expected Output: [[2, 10], [3, 15], [7, 12], [12, 0]]

Explanation: The prompt example: height 10 from x=2, rises to 15 at x=3, drops to 12 at x=7 once the tallest ends, then to 0 at x=12.

Input: (1, [[0, 2, 3]])

Expected Output: [[0, 3], [2, 0]]

Explanation: A single building: height 3 from x=0 to x=2, then ground.

Input: (2, [[0, 5, 3], [0, 5, 3]])

Expected Output: [[0, 3], [5, 0]]

Explanation: Two identical overlapping buildings form one rectangle; only one rise and one fall remain.

Input: (2, [[1, 3, 5], [3, 6, 5]])

Expected Output: [[1, 5], [6, 0]]

Explanation: Edge-touching buildings of equal height merge into a flat top from x=1 to x=6; no spurious point at the shared x=3.

Input: (2, [[2, 4, 7], [2, 4, 5]])

Expected Output: [[2, 7], [4, 0]]

Explanation: The shorter building is fully hidden behind the taller one over the same span, so it never appears in the outline.

Input: (2, [[0, 10, 5], [3, 6, 8]])

Expected Output: [[0, 5], [3, 8], [6, 5], [10, 0]]

Explanation: A taller building nested inside a wider one creates a bump: 5, up to 8, back to 5, then 0.

Input: (3, [[1, 5, 6], [2, 8, 6], [10, 12, 4]])

Expected Output: [[1, 6], [8, 0], [10, 4], [12, 0]]

Explanation: Two overlapping equal-height buildings form one block ending at x=8 (drop to 0), then a disjoint building gives a separate segment from x=10 to x=12.

Hints

Think of each building as two events: a 'start' at x = L (height rises) and an 'end' at x = R (height may fall). Sort all events by x.
At any x, the skyline height equals the tallest building currently spanning that x. A max-heap of active building heights gives this in O(log n).
Use lazy deletion: instead of removing a building's height when it ends, store its right edge with it in the heap and pop entries whose end <= current x before reading the top.
Emit a key point only when the current max height differs from the last emitted height. When several events share the same x, collapse them so only the final height at that x is recorded.

Quick Overview

This question evaluates a candidate's understanding of interval processing and skyline/contour computation within computational geometry, focusing on reasoning about overlapping ranges and height aggregation.