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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

Q: What role is this question designed for?

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

Question

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:

Start at i = column .
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.
If no strictly lower position exists on the left, do the symmetric process on the right.
If neither side has a strictly lower reachable position, the unit settles at column .
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.