Airbnb's Terrain Water-Drop Coding Question

Airbnb loves a problem you can picture. This terrain water-drop question is a recurring on-site: first you render a heightmap, then you simulate water physics as drops settle into the lowest reachable ground. Here is the full question, Java for both parts, and the rubric.

The question

heights = [5,4,3,2,1,3,4,0,3,4]
dumpWater(heights, amount=8, column=1)

Part 1 · Render the terrain

Scan from the tallest level down to 1. On each row, a column is filled if its height reaches that level. This warm-up also fixes your mental model of the grid for Part 2.

import java.util.*;

class Terrain {
    // Part 1: each row is one height level, top to bottom.
    List<String> render(int[] heights) {
        int maxH = 0;
        for (int h : heights) maxH = Math.max(maxH, h);
        List<String> rows = new ArrayList<>();
        for (int level = maxH; level >= 1; level--) {
            StringBuilder row = new StringBuilder();
            for (int colH : heights) row.append(colH >= level ? '+' : ' ');
            rows.add(row.toString());
        }
        return rows;
    }
}

Part 2 · Drop the water

For each unit of water released at the spring column, try to flow left to the lowest reachable position; if it cannot fall left, try right; otherwise it settles where it is. The effective height of a column is terrain plus water already resting there.

int[] pourWater(int[] heights, int amount, int spring) {
    for (int drop = 0; drop < amount; drop++) {
        int pos = flow(heights, spring, -1);      // try to fall left first
        if (pos == spring) pos = flow(heights, spring, +1);  // else right
        heights[pos]++;                            // settle one unit here
    }
    return heights;
}

// Walk in 'dir' while the next cell is not higher; return the lowest reachable
// position, breaking ties toward the cell closest to the spring.
private int flow(int[] h, int start, int dir) {
    int pos = start, best = start;
    while (pos + dir >= 0 && pos + dir < h.length && h[pos + dir] <= h[pos]) {
        pos += dir;
        if (h[pos] < h[best]) best = pos;
    }
    return best;
}

The left-before-right rule and the tie-break toward the spring are the whole game. Get them wrong and the water settles in the wrong valley. Complexity is O(amount x n) in the worst case, which is the trade-off to name.

How Airbnb scores it

Airbnb interview FAQ