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 Onsite rounds at Airbnb.

What role is this question designed for?

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

Simulate pouring water onto a 1D terrain

Q: Simulate pouring water onto a 1D terrain

This question evaluates understanding of simulation of discrete physical processes, array manipulation, state tracking, and greedy/local-search movement rules, measuring algorithmic design and efficiency competencies.

Simulate pouring water onto a 1D terrain

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a 1D terrain represented by an integer array `heights`, where `heights[i]` is the height of the column at index `i`. ## Part 1 — Render terrain Write a function to print an ASCII visualization of the terrain where: - Each column is drawn using `+` characters. - The bottom row (base layer) is always shown. - Rows are printed from top to bottom. Example input: - `heights = [5,4,3,2,1,3,4,0,3,4]` Example rendering (one possible formatting): ``` + ++ + + +++ ++ ++ ++++ ++ ++ +++++++ ++ ++++++++++ <--- base layer ``` ## Part 2 — Pour water and render final state Implement `dumpWater(heights, waterAmount, column)` that simulates pouring `waterAmount` units of water onto the terrain at index `column`. ### Water movement rules (1 unit at a time) For each unit of water: 1. Start at `i = column`. 2. The unit first tries to move left to find the **closest** position with a strictly lower “effective height” (terrain height + already-settled water) by scanning left while the effective height does not increase. - More precisely: move left while `eff(left) <= eff(current)`. - Track the best (lowest) position reached; if any position has `eff < eff(column)`, settle at the leftmost position among the lowest reached. 3. If no strictly lower position exists on the left, do the symmetric process on the right. 4. If neither side has a strictly lower reachable position, the unit settles at `column`. 5. Once settled, that position’s water count increases by 1 (so its effective height increases by 1). After all water is poured, print the final ASCII visualization using: - `+` for terrain blocks - `W` for water blocks (stacked above the terrain) Example call: - `dumpWater([5,4,3,2,1,3,4,0,3,4], waterAmount=8, column=1)` Expected output should match the described final state (formatting may vary as long as block positions are correct). ## Function signatures - `renderTerrain(heights) -> void` - `dumpWater(heights, waterAmount, column) -> void` (may return the final water distribution and/or print the final rendering) ## Constraints (assume) - `1 <= len(heights) <= 10^4` - `0 <= heights[i] <= 10^5` - `0 <= column < len(heights)` - `0 <= waterAmount <= 10^5` Your solution should be correct and reasonably efficient for the above constraints.

Quick Answer: This question evaluates understanding of simulation of discrete physical processes, array manipulation, state tracking, and greedy/local-search movement rules, measuring algorithmic design and efficiency competencies.

Part 1: Render a 1D Terrain as ASCII

You are given a 1D terrain represented by a list of non-negative integers `heights`, where `heights[i]` is the number of terrain blocks stacked above column `i`. Return an ASCII rendering of the terrain from top to bottom. Rendering rules: - Use `'+'` for terrain blocks. - Use `'.'` for empty space (this makes the output unambiguous for automated testing). - There is always one extra base row at the bottom made entirely of `'+'` characters. - The base row is not included in `heights[i]`; it is added separately. - All returned rows must have the same length, equal to `len(heights)`. - If `heights` is empty, return an empty list. Example: - `heights = [1, 0, 2]` - Return `["..+", "+.+", "+++"]`

Constraints

0 <= len(heights) <= 200
0 <= heights[i] <= 200
The total rendered output size will be small enough to fit in memory

Examples

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

Expected Output: ["+.........", "++....+..+", "+++..++.++", "++++.++.++", "+++++++.++", "++++++++++"]

Explanation: Matches the sample terrain, with `.` used for empty cells and an extra full base row at the bottom.

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

Expected Output: ["..+", "+.+", "+++"]

Explanation: The tallest column has height 2, so there are 2 rows above the base.

Input: ([0, 0, 0],)

Expected Output: ["+++"]

Explanation: All columns have zero terrain height, so only the base row is shown.

Input: ([],)

Expected Output: []

Explanation: Empty input produces no rows.

Solution

def solution(heights):
    if not heights:
        return []

    n = len(heights)
    max_h = max(heights)
    rows = []

    for level in range(max_h, 0, -1):
        row = []
        for h in heights:
            row.append('+' if h >= level else '.')
        rows.append(''.join(row))

    rows.append('+' * n)
    return rows

Time complexity: O(n * H), where n is the number of columns and H is the maximum height. Space complexity: O(n * H) including the returned output, or O(1) auxiliary space aside from output.

Hints

Build the picture one row at a time, starting from the maximum terrain height down to 1.
For a given row level `L`, column `i` contains `'+'` if `heights[i] >= L`; otherwise it contains `'.'`.

Part 2: Pour Water on a 1D Terrain and Render the Final State

You are given a 1D terrain represented by a list `heights`, a number of water units `waterAmount`, and a starting column `column`. Simulate pouring water one unit at a time onto the terrain. Definitions: - `effective height(i) = heights[i] + water[i]` - `water[i]` is how much water has already settled at column `i` For each unit of water: 1. Start at `column`. 2. Try to move left by scanning while the next position does not rise: - While `effective height(i - 1) <= effective height(i)`, continue moving left. - Among all scanned positions, track the minimum effective height reached. - If at least one scanned position is strictly lower than the starting effective height, settle at the **leftmost** position among the lowest ones reached. 3. If no strictly lower position exists on the left, do the symmetric process on the right: - While `effective height(i + 1) <= effective height(i)`, continue moving right. - If at least one scanned position is strictly lower than the starting effective height, settle at the **rightmost** position among the lowest ones reached. 4. If neither side has a strictly lower reachable position, the water settles at `column`. 5. After settling, that column's water count increases by 1. After all water is poured, return the final ASCII rendering from top to bottom using: - `'+'` for terrain blocks - `'W'` for water blocks - `'.'` for empty space - one extra full base row of `'+'` at the bottom This version returns the rendering instead of printing it.

Constraints

1 <= len(heights) <= 200
0 <= heights[i] <= 100
0 <= waterAmount <= 200
0 <= column < len(heights)
The total rendered output size will be small enough to fit in memory

Examples

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

Expected Output: ["+W+.+", "+++++", "+++++"]

Explanation: Both sides have a lower reachable column, so the water must prefer the left side first and settle at index 1.

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

Expected Output: ["+W+", "+W+", "+++", "+++"]

Explanation: There is no left side, so water falls to the right valley twice, stacking there.

Input: ([1, 1, 1], 1, 1)

Expected Output: [".W.", "+++", "+++"]

Explanation: Neither side is strictly lower, so the water stays at the source column.

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

Expected Output: ["+..+", "+W.+", "++++", "++++"]

Explanation: The left scan reaches two equally low positions. The water settles at the leftmost of those lowest positions.

Input: ([0], 3, 0)

Expected Output: ["W", "W", "W", "+"]

Explanation: Single-column edge case: all water stacks in the only column above the base.

Solution

def solution(heights, waterAmount, column):
    if not heights:
        return []

    n = len(heights)
    water = [0] * n

    def eff(i):
        return heights[i] + water[i]

    for _ in range(waterAmount):
        start_eff = eff(column)

        # Try left first.
        best = column
        min_eff = start_eff
        i = column
        while i > 0 and eff(i - 1) <= eff(i):
            i -= 1
            current_eff = eff(i)
            if current_eff < min_eff:
                min_eff = current_eff
                best = i
            elif current_eff == min_eff:
                best = i

        if min_eff < start_eff:
            water[best] += 1
            continue

        # If left fails, try right.
        best = column
        min_eff = start_eff
        i = column
        while i < n - 1 and eff(i + 1) <= eff(i):
            i += 1
            current_eff = eff(i)
            if current_eff < min_eff:
                min_eff = current_eff
                best = i
            elif current_eff == min_eff:
                best = i

        if min_eff < start_eff:
            water[best] += 1
        else:
            water[column] += 1

    final_height = max(h + w for h, w in zip(heights, water))
    rows = []
    for level in range(final_height, 0, -1):
        row = []
        for h, w in zip(heights, water):
            if level <= h:
                row.append('+')
            elif level <= h + w:
                row.append('W')
            else:
                row.append('.')
        rows.append(''.join(row))

    rows.append('+' * n)
    return rows

Time complexity: O(waterAmount * n + n * H), where H is the final maximum of `heights[i] + water[i]`. Space complexity: O(n * H) including the returned output, plus O(n) auxiliary space for the water array.

Hints

Keep a separate `water` array and always compare columns using `heights[i] + water[i]`.
When scanning left or right, stop as soon as the next step would go uphill. While scanning, remember the lowest reachable effective height; on ties, prefer the direction you are scanning toward.

Simulate pouring water onto a 1D terrain

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Part 1: Render a 1D Terrain as ASCII

Constraints

0 <= len(heights) <= 200
0 <= heights[i] <= 200
The total rendered output size will be small enough to fit in memory

Examples

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

Expected Output: ["+.........", "++....+..+", "+++..++.++", "++++.++.++", "+++++++.++", "++++++++++"]

Explanation: Matches the sample terrain, with `.` used for empty cells and an extra full base row at the bottom.

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

Expected Output: ["..+", "+.+", "+++"]

Explanation: The tallest column has height 2, so there are 2 rows above the base.

Input: ([0, 0, 0],)

Expected Output: ["+++"]

Explanation: All columns have zero terrain height, so only the base row is shown.

Input: ([],)

Expected Output: []

Explanation: Empty input produces no rows.

Solution

def solution(heights):
    if not heights:
        return []

    n = len(heights)
    max_h = max(heights)
    rows = []

    for level in range(max_h, 0, -1):
        row = []
        for h in heights:
            row.append('+' if h >= level else '.')
        rows.append(''.join(row))

    rows.append('+' * n)
    return rows

Time complexity: O(n * H), where n is the number of columns and H is the maximum height. Space complexity: O(n * H) including the returned output, or O(1) auxiliary space aside from output.

Hints

Build the picture one row at a time, starting from the maximum terrain height down to 1.
For a given row level `L`, column `i` contains `'+'` if `heights[i] >= L`; otherwise it contains `'.'`.

Part 2: Pour Water on a 1D Terrain and Render the Final State

Constraints

1 <= len(heights) <= 200
0 <= heights[i] <= 100
0 <= waterAmount <= 200
0 <= column < len(heights)
The total rendered output size will be small enough to fit in memory

Examples

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

Expected Output: ["+W+.+", "+++++", "+++++"]

Explanation: Both sides have a lower reachable column, so the water must prefer the left side first and settle at index 1.

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

Expected Output: ["+W+", "+W+", "+++", "+++"]

Explanation: There is no left side, so water falls to the right valley twice, stacking there.

Input: ([1, 1, 1], 1, 1)

Expected Output: [".W.", "+++", "+++"]

Explanation: Neither side is strictly lower, so the water stays at the source column.

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

Expected Output: ["+..+", "+W.+", "++++", "++++"]

Explanation: The left scan reaches two equally low positions. The water settles at the leftmost of those lowest positions.

Input: ([0], 3, 0)

Expected Output: ["W", "W", "W", "+"]

Explanation: Single-column edge case: all water stacks in the only column above the base.

Solution

def solution(heights, waterAmount, column):
    if not heights:
        return []

    n = len(heights)
    water = [0] * n

    def eff(i):
        return heights[i] + water[i]

    for _ in range(waterAmount):
        start_eff = eff(column)

        # Try left first.
        best = column
        min_eff = start_eff
        i = column
        while i > 0 and eff(i - 1) <= eff(i):
            i -= 1
            current_eff = eff(i)
            if current_eff < min_eff:
                min_eff = current_eff
                best = i
            elif current_eff == min_eff:
                best = i

        if min_eff < start_eff:
            water[best] += 1
            continue

        # If left fails, try right.
        best = column
        min_eff = start_eff
        i = column
        while i < n - 1 and eff(i + 1) <= eff(i):
            i += 1
            current_eff = eff(i)
            if current_eff < min_eff:
                min_eff = current_eff
                best = i
            elif current_eff == min_eff:
                best = i

        if min_eff < start_eff:
            water[best] += 1
        else:
            water[column] += 1

    final_height = max(h + w for h, w in zip(heights, water))
    rows = []
    for level in range(final_height, 0, -1):
        row = []
        for h, w in zip(heights, water):
            if level <= h:
                row.append('+')
            elif level <= h + w:
                row.append('W')
            else:
                row.append('.')
        rows.append(''.join(row))

    rows.append('+' * n)
    return rows

Hints

Keep a separate `water` array and always compare columns using `heights[i] + water[i]`.
When scanning left or right, stop as soon as the next step would go uphill. While scanning, remember the lowest reachable effective height; on ties, prefer the direction you are scanning toward.

Quick Overview

Quick Overview