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 Take-home Project rounds at Optiver.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Optiver during technical interviews.

Solve a Skyscraper puzzle efficiently | Optiver Coding Question

Solve a Skyscraper puzzle efficiently

Company: Optiver

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Design and implement a solver for the Skyscraper logic puzzle on an N×N grid (3 ≤ N ≤ 7). Each row and column must contain the numbers 1..N without repetition. Edge clues indicate how many buildings are visible from that side given building heights. Given a set of clues (possibly some blanks), return one valid grid or report that none exists. Describe your modeling (e.g., constraint propagation with Latin-square domains, visibility predicates), search strategy (backtracking, MRV/degree heuristics, forward checking), pruning techniques, and how you would verify uniqueness. Provide the expected input/output formats and analyze worst-case complexity.

Quick Answer: This question evaluates understanding of constraint satisfaction and combinatorial search, testing competency in modeling Latin-square domains with visibility constraints, pruning and uniqueness verification, and algorithmic complexity analysis.

Solve the **Skyscraper** logic puzzle on an `N x N` grid (`3 <= N <= 7`). Fill the grid with building heights so that: - Every **row** and every **column** is a permutation of `1..N` (a Latin square whose symbols are exactly `1..N`). A cell's value is the height of the building there. - **Edge clues** around the border state how many buildings are **visible** looking down a row/column from that side. A building is visible iff it is taller than every building between it and the viewer (taller buildings hide shorter ones behind them). Equivalently, the visible count equals the number of left-to-right running maxima along that line. - Some clues may be **blank** (encoded as `0`). Return **one** valid completed grid that satisfies every present clue plus the Latin-square rules, or `None`/`null` if no such grid exists. ### Function Implement `solution(N, clues)`. - `N` is the side length. - `clues` is a dictionary with optional keys `'top'`, `'bottom'`, `'left'`, `'right'`, each a list of length `N` (`0` = blank). An omitted side defaults to all-blank. ### Direction convention (pinned) - `top[c]` : looking **down** column `c` (top -> bottom) - `bottom[c]`: looking **up** column `c` (bottom -> top) - `left[r]` : looking **right** along row `r` (forward) - `right[r]` : looking **left** along row `r` (reversed) ### Output Return the solved grid as `N` rows of `N` integers, or `None` if the clue set is unsatisfiable. Any grid consistent with the clues is acceptable (uniqueness is not required). ### Example ``` N = 4 clues = {'top': [4,3,2,1], 'bottom': [1,2,2,2], 'left': [4,3,2,1], 'right': [1,2,2,2]} -> [[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]] ```

Constraints

3 <= N <= 7
Each present clue value lies in 1..N; blanks are encoded as 0.
Each of top/bottom/left/right, when present, is a list of length N; an omitted side is treated as all-blank.
Heights inside the grid are exactly the integers 1..N with no repeats per row/column.
Return any grid consistent with the clues, or None if none exists (uniqueness not required).

Examples

Input: (4, {'top': [0, 0, 1, 2], 'bottom': [0, 0, 0, 0], 'left': [0, 2, 0, 0], 'right': [0, 0, 0, 0]})

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

Explanation: Under-constrained clue set (admits many grids). The solver returns the first consistent grid in canonical order; column 2 read top-down is [4,3,2,1] -> 1 visible matching top[2]=1, and row 1 [2,4,3,1] -> 2 visible matching left[1]=2.

Input: (4, {'top': [4, 3, 2, 1], 'bottom': [1, 2, 2, 2], 'left': [4, 3, 2, 1], 'right': [1, 2, 2, 2]})

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

Explanation: Fully clued. left[0]=4 and top[0]=4 force the first row and column to be strictly increasing; the cyclic Latin square satisfies every clue. Clues were derived programmatically from this target grid.

Input: (3, {'top': [3, 2, 1], 'left': [3, 2, 1]})

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

Explanation: left[0]=3 forces row 0 = [1,2,3]; top[0]=3 forces column 0 = [1,2,3]. Only the cyclic square fits with the remaining clues blank or consistent.

Input: (4, {'left': [1, 0, 0, 0], 'right': [1, 0, 0, 0]})

Expected Output: None

Explanation: Edge case: left[0]=1 forces the first cell of row 0 to be N=4, and right[0]=1 forces the last cell of row 0 to also be N=4. A row cannot hold 4 in two positions, so no valid grid exists.

Input: (3, {})

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

Explanation: All-blank: the task reduces to producing any Latin square of 1..3; the solver returns the first one found.

Input: (5, {'top': [5, 4, 3, 2, 1], 'left': [5, 0, 0, 0, 0]})

Expected Output: [[1, 2, 3, 4, 5], [2, 3, 4, 5, 1], [3, 4, 5, 1, 2], [4, 5, 1, 2, 3], [5, 1, 2, 3, 4]]

Explanation: left[0]=5 forces row 0 = [1,2,3,4,5] (clue N => strictly increasing) and top[0]=5 forces column 0 = [1,2,3,4,5]; the cyclic 5x5 square satisfies the descending top clues.

Hints

A building is visible exactly when it is a new running maximum reading the line from the viewer's side, so the visible count = number of left-to-right maxima. Read a line from the opposite side by reversing it.
Enumerate each row's permutations of 1..N and pre-filter by that row's left/right clues; then assign rows top-to-bottom, enforcing column AllDifferent and column (top/bottom) visibility.
Keep rows in true index order 0..N-1 so a partial column [grid[0][c], grid[1][c], ...] is a genuine top-down prefix; otherwise top/bottom visibility is computed on a scrambled column. Cheap exact facts: clue N forces the line to be 1..N increasing, clue 1 forces the nearest cell to be N, and opposite-end clues on a line satisfy c_left + c_right <= N+1.

Quick Overview

This question evaluates understanding of constraint satisfaction and combinatorial search, testing competency in modeling Latin-square domains with visibility constraints, pruning and uniqueness verification, and algorithmic complexity analysis.