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 Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at TikTok during technical interviews.

Compute city skyline silhouette | TikTok Coding Question

Quick Overview

Compute city skyline silhouette evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Compute city skyline silhouette

Company: TikTok

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Compute the outer silhouette of a 2D skyline. You are given n axis-aligned rectangular buildings; each building i is (Li, Ri, Hi) with 0 <= Li < Ri and Hi > 0. Return the list of critical points (x, h) where the silhouette height changes, sorted by x ascending; consecutive points must have different heights, and the final point should drop to height 0 when the skyline ends. Aim for O(n log n) time and near-linear space. Implement and explain an efficient approach (e.g., sweep line with a max-structure or divide-and-conquer). Specify and handle tie cases when multiple edges share the same x (e.g., entering edges before leaving; among entering edges process higher heights first; among leaving edges process lower heights first). Discuss correctness, complexity, and edge cases such as identical buildings, fully nested intervals, touching borders (Ri == Lj), and very large coordinates.

Quick Answer: Compute city skyline silhouette evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given `n` axis-aligned rectangular buildings on a flat ground. Each building `i` is described by `(Li, Ri, Hi)` where `0 <= Li < Ri` is its left/right x-coordinate and `Hi > 0` is its height. Compute the outer silhouette (skyline) formed by the union of all buildings. Return the list of **critical points** `[x, h]` — the points where the silhouette height changes — sorted by `x` ascending. The first coordinate of each key point is the x position; the second is the height there. Consecutive key points must have **different** heights (no redundant points), and the silhouette must terminate at a key point of height `0` where the rightmost building ends. If there are no buildings, return an empty list. This is the classic 'Skyline Problem'. Aim for `O(n log n)` time. **Tie handling (important):** when multiple building edges share the same x, the algorithm must process them so the reported height is the true maximum across that x. Entering edges should be considered before leaving edges, among entering edges higher heights take effect first, and among leaving edges lower heights leave first — a sweep-line with a max-heap (and lazy deletion of ended buildings) achieves this naturally. **Example:** `buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]` → `[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]`.

Constraints

0 <= n (n is the number of buildings; n may be 0)
Each building is [L, R, H] with 0 <= L < R and H > 0
Coordinates and heights may be large; the algorithm only compares values, so very large coordinates are fine
Return key points sorted by x ascending with strictly alternating heights, ending at height 0

Examples

Input: [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]

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

Explanation: Canonical LC218 example. The silhouette rises as taller buildings begin, drops to 0 in the gap between x=12 and x=15, then resumes for the second cluster.

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

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

Explanation: Two equal-height buildings touching at x=2 (Ri == Lj). The shared border produces no spurious key point — height stays 3 until the right end.

Input: [[1,2,1],[1,2,2],[1,2,3]]

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

Explanation: Three identical-span buildings of heights 1,2,3. Only the tallest is visible, giving a single rise to 3 and a drop to 0.

Input: [[1,5,4],[2,4,4]]

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

Explanation: A fully nested building of the same height as its container contributes nothing to the silhouette.

Input: [[0,5,7],[1,3,9],[2,4,9]]

Expected Output: [[0, 7], [1, 9], [4, 7], [5, 0]]

Explanation: Two equal-height taller buildings overlap on top of a lower base; height stays 9 across the union [1,4) then falls back to the base 7.

Input: []

Expected Output: []

Explanation: Empty input yields an empty skyline.

Input: [[3,10,8]]

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

Explanation: A single building gives exactly two key points: the rise at its left edge and the drop to 0 at its right edge.

Input: [[2,9,10],[9,12,10]]

Expected Output: [[2, 10], [12, 0]]

Explanation: Adjacent same-height buildings sharing the border x=9 form one continuous plateau; no key point is emitted at x=9.

Hints

Convert each building into two sweep-line events at its left and right edge, then sweep x from left to right while tracking the current maximum height among 'live' buildings.
Use a max-heap keyed by height. The hard part is removal: a binary heap can't pop an arbitrary element, so use lazy deletion — store each building's right edge alongside its height and discard heap-top entries whose right edge has already been passed.
Handle ties at a shared x carefully: process all events at the same x together, and emit a key point only when the resulting max height differs from the last emitted height. Encoding start edges as (x, -H, R) and end edges as (x, 0, 0) makes the sort order do the tie-breaking for you (starts before ends; taller starts first).

Quick Overview