Coding interview: Uniformly sample a square and scan the longest increasing subarray

Prompt and scope

The public interview record splits the exercise into two short tasks: call a function rand01() that returns a uniform value between 0 and 1 to sample a point inside a square of side side, then find the longest strictly increasing contiguous segment of an array. This article places the square's lower-left corner at (0, 0), treats the random source as [0, 1), and returns an empty result for an empty array.

What the interviewer is testing

The exercise combines probability modeling, range mapping, a one-pass invariant, and precise result semantics. Cornell's lecture notes explain that two independent uniform variables on [0,1] form a point uniform with respect to area on the unit square; MIT's square-probability material gives the same area interpretation. The scan tests whether the candidate preserves contiguity, treats equality as a break, and chooses a deterministic tie-break.

Clarifying questions to ask

1. Is rand01() closed or half-open? This answer assumes [0, 1).
2. Is the square translated? This answer starts at the origin; translation adds offsets.
3. Is increasing strict? This answer requires a[i] > a[i-1].
4. Which longest run wins a tie? This answer returns the earliest start.
5. Is deduplication or cryptographic randomness required? The base exercise does not require either.

A 30-second answer

“I call rand01() independently twice and multiply the values by the side length. Independent uniform coordinates make every small rectangle's probability equal to its area. For the array, I keep the start of the current strictly increasing run and the best start/end indices. A non-increase resets the current start; I update the answer only when the current run is strictly longer. Sampling is O(1), scanning is O(n), and extra space is O(1). I will test bounds, equality, empty input, monotone arrays, and ties.”

Step-by-step solution

1. Derive the uniform sample

Let U and V be independent uniform variables on [0,1). For any axis-aligned rectangle [a,b) × [c,d), the probability of landing inside it is (b-a)(d-c), exactly its area. Therefore (side × U, side × V) is uniform in the square. Reusing one draw would make the coordinates perfectly correlated and place every point on a diagonal.

2. Maintain the linear-scan invariant

At index i, currentStart is the start of the longest strictly increasing run ending at i; bestStart and bestEnd describe the best run in the prefix. If a[i] > a[i-1], extend the run. Otherwise set currentStart = i. Update only on a strictly larger length, which keeps the earliest run among ties.

3. Reference implementation

from typing import Callable


def sample_square(side: float, rand01: Callable[[], float]) -> tuple[float, float]:
    if side < 0:
        raise ValueError("side must be non-negative")
    u, v = rand01(), rand01()
    if not (0 <= u < 1 and 0 <= v < 1):
        raise ValueError("rand01 must return values in [0, 1)")
    return side * u, side * v


def longest_increasing_run(values: list[int]) -> tuple[int, int] | None:
    if not values:
        return None
    current_start = best_start = best_end = 0
    for i in range(1, len(values)):
        if values[i] <= values[i - 1]:
            current_start = i
        current_length = i - current_start + 1
        best_length = best_end - best_start + 1
        if current_length > best_length:
            best_start, best_end = current_start, i
    return best_start, best_end

4. Complexity and tests

Sampling makes two random-source calls, so time and extra space are O(1). The scan visits each element once, taking O(n) time and O(1) extra space; materializing the returned values would additionally cost O(k). Use a fixed rand01 sequence to test coordinate mapping, [1, 2, 2, 3] to test strictness, and [5, 4, 3] to test the single-element answer.

Model answer

“I model the two coordinates as independent uniform variables: call rand01 twice and scale by the side length. That makes the probability of any small rectangle equal to its area. I find the increasing run with one start pointer and best indices in a linear scan, resetting on a non-increase and updating only for a strictly longer run, so ties choose the earliest segment. Sampling is O(1), scanning is O(n), and both use O(1) extra space. I will verify the random-source contract, negative sides, equal values, and empty arrays.”

Common mistakes

• Reuse one random draw → coordinates are correlated and lie on a diagonal → draw independently twice.
• Assume an arbitrary rand01 range → coordinates can leave the square → state and validate the [0,1) contract.
• Sort or use dynamic programming for a contiguous run → order is lost or space is added → keep one scan state.
• Use >= for increasing → equal values are incorrectly joined → require >.
• Overwrite on equal best lengths → tie behavior becomes accidental → update only on a strictly larger length.
• Recursively scan the array → stack depth grows with input size → use iteration.

Follow-ups and extensions

How do you sample a rectangle or translated square?

Use x = xmin + (xmax-xmin)U and y = ymin + (ymax-ymin)V for a rectangle. A translation simply adds an offset to both coordinates and preserves independence.

How would you diagnose uniformity?

Partition the square into equal-area cells, draw many samples, and compare cell counts. This is a diagnostic, not a proof; a fixed seed is useful for regression but does not guarantee visual uniformity.

What if every longest run must be returned?

Keep the current best length and a list. Clear the list on a longer run and append on an equal run; the additional space is O(r), where r is the number of tied runs.

What if the array arrives as a stream?

Keep only the previous value, current start, best indices, and current position. Emit the best interval at end of stream, with memory independent of total input length.