Question presented to candidate: "You get an array where each value is the height of a vertical line. Pick two lines that, together with the x-axis, hold the most water, and return that amount. Please code it in Python, and convince me your approach cannot miss the best pair."
What a strong answer should cover:
- The area of a pair is min(height[i], height[j]) × (j − i); the brute force checks all pairs in O(n²).
- Two pointers from both ends, always moving the shorter wall: O(n) time, O(1) space.
- The elimination argument: every container that keeps the shorter wall is narrower and capped by that same wall, so discarding it is safe; moving the taller wall can never help.
- Equal walls (move either) and edge cases: fewer than two lines, zeros, best pair adjacent.
- Python specifics:
min()/max()built-ins and tuple assignment keep it short; Python integers never overflow, so height × width is always exact.
Clarifying questions expected:
- "Do you want the area only or the two indices too?"
- "How large can heights and n get?" — decides whether the area needs a 64-bit type.
Code / implementation expected: Yes — a max_area(height) function in Python, ideally returning the pair of indices as well.