コーディング面接：正方形の一様サンプリングと最長増加連続部分配列のスキャン

課題とスコープ

公開されている面接記録では、この課題は 2 つの短いタスクに分かれています。0 から 1 までの値を一様に返す関数 rand01() を呼び出して一辺が side の正方形内の点をサンプリングすること、そして配列内で最長の狭義増加連続セグメントを見つけることです。本記事では、正方形の左下隅を (0, 0) に配置し、乱数生成元を [0, 1) として扱い、空の配列に対しては空の結果を返します。

面接官が見ているポイント

この課題は、確率モデリング、範囲マッピング、ワンパス不変量、そして正確な結果セマンティクスを組み合わせてテストします。Cornell の講義ノートでは、[0,1] 上の 2 つの独立した一様変数が単位正方形上で面積に関して一様な点を形成すると説明されています。MIT の正方形確率教材でも同様の面積解釈がなされています。スキャン処理では、候補者が連続性を維持しているか、等しい値を途切れとして扱うか、そして決定論的なタイブレーク（同点処理）を選択しているかが試されます。

確認すべき明確化のための質問

rand01() は閉区間ですか、それとも半開区間ですか？本回答では [0, 1) を前提とします。
正方形は平行移動されていますか？本回答は原点から開始しますが、平行移動はオフセットを加算するだけです。
増加は狭義（厳密）ですか？本回答では a[i] > a[i-1] を要求します。
最長の連続部分列が複数ある場合、どれを優先しますか？本回答では最も早い開始位置を返します。
重複排除や暗号論的ランダム性は必要ですか？基本的な課題ではどちらも不要です。

30秒で答える要約

「rand01() を独立して 2 回呼び出し、その値に一辺の長さを掛けます。独立した一様座標により、あらゆる微小な長方形の確率がその面積と等しくなります。配列については、現在調査中の狭義増加部分列の開始位置と、これまでに見つかった最適な開始・終了インデックスを保持します。非増加になると現在の開始位置がリセットされ、現在の部分列が厳密により長い場合にのみ解を更新します。サンプリングは O(1)、スキャンは O(n)、追加空間は O(1) です。境界値、等しい値、空の入力、単調配列、タイブレークをテストします。」

ステップごとの解説

1. 一様サンプルの導出

U と V を [0,1) 上の独立した一様変数とします。任意の軸に平行な長方形 [a,b) × [c,d) について、その内部に入る確率は (b-a)(d-c) となり、まさにその面積と一致します。したがって、(side × U, side × V) は正方形内で一様です。1 回の乱数取得結果を再利用すると、座標間に完全な相関が生じ、すべての点が対角線上に配置されてしまいます。

2. 線形スキャンの不変量を維持する

インデックス i において、currentStart は i で終わる最長狭義増加部分列の開始位置です。bestStart と bestEnd は、そのプレフィックスにおける最適な部分列を表します。a[i] > a[i-1] であれば、部分列を拡張します。そうでなければ currentStart = i を設定します。厳密により大きい長さの場合にのみ更新することで、同点の場合に最も早い部分列が保持されます。

3. 参照実装

python

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. 計算量とテスト

サンプリングは乱数生成元を 2 回呼び出すため、時間計算量と追加空間計算量は O(1) です。スキャンは各要素を 1 回走査するため、O(n) の時間と O(1) の追加空間を要します。戻り値の値を具体的に実体化する場合は、さらに O(k) がかかります。座標マッピングのテストには固定の rand01 シーケンスを、狭義性のテストには [1, 2, 2, 3] を、単一要素の回答テストには [5, 4, 3] を使用します。

模範解答

「2 つの座標を独立した一様変数としてモデル化します。rand01 を 2 回呼び出し、一辺の長さでスケールします。これにより、任意の微小長方形の確率がその面積と等しくなります。線形スキャンでは、1 つの開始ポインタと最適インデックスを用いて増加部分列を探索し、非増加時にリセットし、厳密により長い部分列の場合にのみ更新することで、同点時は最も早いセグメントを選択します。サンプリングは O(1)、スキャンは O(n) で、どちらも O(1) の追加空間を使用します。乱数生成元の契約、負の一辺の長さ、等しい値、空配列を検証します。」

よくある間違い

1 回の乱数取得を再利用する → 座標が相関して対角線上に並ぶ → 独立して 2 回取得する。
任意の rand01 範囲を前提とする → 座標が正方形の外に出る可能性がある → [0,1) の契約を明示し検証する。
連続部分列に対してソートや動的計画法を使用する → 順序が失われるか空間が余分にかかる → 単一のスキャン状態を維持する。
増加条件に >= を使用する → 等しい値が誤って結合される → > を要求する。
同じ最適長で上書きする → タイブレークの動作が偶発的になる → 厳密により長い長さの場合にのみ更新する。
配列を再帰的にスキャンする → 入力サイズに応じてスタックの深さが増加する → 反復処理を使用する。

フォローアップと発展課題

長方形や平行移動された正方形をサンプリングするにはどうすればよいですか？

長方形には x = xmin + (xmax-xmin)U と y = ymin + (ymax-ymin)V を使用します。平行移動は両方の座標にオフセットを加算するだけであり、独立性は保持されます。

一様性をどのように診断・検証しますか？

正方形を等面積のセルに分割し、多数のサンプルを取得して、各セルのカウントを比較します。これは診断であり証明ではありません。固定シードはリグレッションテストに役立ちますが、視覚的な一様性を保証するものではありません。

最長の部分列をすべて返す必要がある場合はどうしますか？

現在の最適長とリストを保持します。より長い部分列が見つかったらリストをクリアし、同じ長さの部分列が見つかったら追加します。追加空間は O(r)（r は同点となる部分列の数）です。

配列がストリームとして渡される場合はどうしますか？

直前の値、現在の開始位置、最適インデックス、現在の位置のみを保持します。ストリームの終了時に最適な区間を出力します。メモリ使用量は入力全体の長さに依存しません。