Why Tencent Offers Are So Coveted and How to Crack the Skyline Interview Problem

Someone was surprised to see a post about a candidate who, over two years, attended six interviews at Tencent without giving up, illustrating how coveted a Tencent offer is because the company’s brand alone helps candidates pass many resume screens.

The post then introduces today’s interview question: a “skyline keeper” problem where a city is represented by a matrix of building heights, and you may increase building heights without changing the skyline when viewed from any of the four cardinal directions.

The key observation is that a building’s final height is limited only by two numbers: the maximum height in its row ( rowMax[i]) and the maximum height in its column ( colMax[j]). The allowed height is the smaller of the two, i.e., int limit = Math.min(rowMax[i], colMax[j]);. Using Math.max would be wrong because it could raise a building above the column’s skyline.

The provided Java solution first scans the matrix once to record each row’s and column’s highest building, then scans again to compute the increase for each cell:

public class SkylineKeeper {
    public int calculateIncrease(int[][] buildings) {
        int rows = buildings.length;
        int cols = buildings[0].length;
        int[] rowPeak = new int[rows];
        int[] colPeak = new int[cols];
        // record original row and column maxima
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int height = buildings[r][c];
                rowPeak[r] = Math.max(rowPeak[r], height);
                colPeak[c] = Math.max(colPeak[c], height);
            }
        }
        int total = 0;
        // each building is constrained by both skylines
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int allowedHeight = Math.min(rowPeak[r], colPeak[c]);
                total += allowedHeight - buildings[r][c];
            }
        }
        return total;
    }
}

The algorithm runs in O(m × n) time because it traverses the matrix twice, and uses O(m + n) extra space for the row and column peak arrays. A naïve approach that recomputes the maximum for each cell would repeat work and degrade performance on large matrices.

The essential insight is that a building’s increase is bounded by the stricter of its row and column limits; therefore the answer is always obtained by applying Math.min to those two maxima and summing the differences.