0Pricing
Coding Interview Prep · レッスン

ギャップと島問題を見分ける

文章問題に現れるパターンと、核となるグループ化の考え方を特定します。

「ギャップと島問題を見分ける」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

面接官が確認しているパターン

シニア向けの面接で、何かの連続区間を見つけるよう求められたら、それはギャップとアイランド問題です。この名前は、行がまとまっている様子を思い描いたものです。まとまりを形成する行がアイランドで、その間の切れ目がギャップです。

  • アイランドとは、あるルール（連続する整数、連続する日付、または繰り返される同じステータス）に基づいて隣接する行が形成する、最大の連続区間です。
  • ギャップとは、二つのアイランドの間にある欠落部分です。

この問題の種類を即座に見抜けること自体が、シニアレベルの能力を示します。多くの候補者は複雑な自己結合に頼りますが、洗練された答えはほとんどの場合、ウィンドウ関数を使います。

アイランドを隠している文章題

難しいのは、面接官が「ギャップとアイランド」とはほとんど言わないことです。別の表現に置き換えて出題します。次のような言い回しに気付けるようにしてください。

  • 「ユーザーが継続して購読していた期間をそれぞれ求めてください」
  • 「サーバーは何日連続で稼働していましたか」
  • 「このテーブルで欠落している ID の範囲はどれですか」
  • 「同じステータスの隣接行を一つの行にまとめてください」

これらはすべて同じ形です。隣り合う行をグループ化し、そのグループの開始、終了、または欠落を報告します。言葉をアイランドに対応付けられれば、SQL は自然に書けるようになります。

核心：グループキーを作る

このテクニック全体を一文で言うと、同じアイランドに属するすべての行に同一のグループキーを割り当てられれば、単純な GROUP BY で各アイランドを一つの集約行にまとめられます。

したがって、ギャップとアイランド問題で本当に重要なのは、そのグループキーを計算することです。バリエーションによって計算方法は異なりますが、目標はすべて同じです。キーが得られれば、最後の手順は簡単です。

SELECT
  grp,
  MIN(value) AS island_start,
  MAX(value) AS island_end,
  COUNT(*)   AS island_length
FROM rows_with_group_key
GROUP BY grp
ORDER BY island_start;

具体的なデータセット

データを使って考えてみましょう。ユーザーがログインした日番号を記録する logins テーブルを想像してください。

  • 存在する日：1、2、3、7、8、10

見た目で判断すると、アイランドは{1,2,3}、{7,8}、{10}です。ギャップは 4～6 日目と 9 日目です。面接での課題は、手作業で指摘しなくても、データベースにこの三つのアイランドを認識させることです。各手法を見ていく間、この小さなデータセットを覚えておいてください。

CREATE TABLE logins (day_no INT);
INSERT INTO logins VALUES (1),(2),(3),(7),(8),(10);

単純なアプローチが失敗する理由

最初によく思い付くのは、自己結合で各行を次の行と比較し、切れ目に印を付ける方法です。一つのギャップを見つけるには使えますが、すぐに扱いにくくなります。

  • 各アイランドの開始と終了の両方を検出する必要があるため、二回の走査または二つの結合が必要になります。
  • 端の行（先頭と末尾の行そのもの）には特別な処理が必要です。
  • 追加の仕組みなしでは、「すべての連続区間の長さを求める」といった問題に一般化できません。

面接官が見ているのは、自己結合を重ねる泥沼に入るか、それともウィンドウ関数を使った一回の処理のほうが明快だと認識できるかです。

ギャップ検出の考え方

堅牢な考え方の一つは、現在の行が直前の行と隣接していないときに、新しいアイランドが始まるというものです。LAG を使って一つ前の行を参照し、比較します。

day_no - LAG(day_no) が 1 より大きい場合（または先頭行で NULL の場合）、その行が新しいアイランドの開始です。これをフラグ 1 で示し、それ以外は 0 にします。このデータでフラグがどのようになるか確認してみましょう。

SELECT
  day_no,
  CASE
    WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1 THEN 0
    ELSE 1
  END AS is_new_island
FROM logins
ORDER BY day_no;

フラグをグループキーに変換する

前の手順で得られるフラグは、日 1、2、3、7、8、10 に対して 1、0、0、1、0、1 です。ここで、フラグの累積和を取ると、アイランド内では一定で、新しいアイランドごとに増加する値になることに注目してください。結果は 1、1、1、2、2、3 です。

この累積和が、作成したグループキーです。フラグを求めるクエリを CTE で囲み、別のウィンドウ関数で合計します。

WITH flagged AS (
  SELECT
    day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new_island
  FROM logins
)
SELECT
  day_no,
  SUM(is_new_island) OVER (ORDER BY day_no) AS grp
FROM flagged;

実例を完成させる

次に、グループキーの上に最後の GROUP BY を重ねます。異なる grp の値それぞれが一つのアイランドなので、その境界とサイズを報告します。

結果は、見た目で確認した三つのアイランドと完全に一致します。1～3（長さ 3）、7～8（長さ 2）、10～10（長さ 1）です。この三層のレシピ（フラグ、累積和、グループ化）は、ほぼすべてのギャップとアイランド問題で作成する回答の基盤になります。

WITH flagged AS (
  SELECT day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new
  FROM logins
),
keyed AS (
  SELECT day_no,
    SUM(is_new) OVER (ORDER BY day_no) AS grp
  FROM flagged
)
SELECT grp, MIN(day_no) AS start_day,
       MAX(day_no) AS end_day, COUNT(*) AS len
FROM keyed GROUP BY grp ORDER BY start_day;

隣接の定義はドメイン固有

問題ごとに変わるのは、隣接の定義だけです。適切な隣接ルールを見極めることは、問題を認識することの半分に当たります。

  • 整数：差がちょうど 1 のときに隣接しています。
  • 暦日：一方の日付が次の日であるときに隣接しています（date = prev + INTERVAL '1 day'）。
  • ステータス期間：前の行からステータス値が変わっていないときに隣接しています。

骨格は同じで、CASE 内の比較だけが異なります。どの隣接ルールを適用するかを見極めることが、面接で声に出して確認すべき質問です。

確認すべき質問

SQL を一行でも書く前に、範囲を確認して得点につなげましょう。ギャップとアイランド問題で確認すべきことは次のとおりです。

  • 「データはユーザーごとに扱いますか、それとも全体で扱いますか」（これは PARTITION BY user_id を追加するかどうかを決めます。）
  • 「同じ日に重複する値が存在する可能性はありますか。その場合、連続区間を途切れさせますか、それとも延長しますか」
  • 「アイランド、ギャップ、またはその両方のどれを求めていますか」
  • 「系列はソート済みであることが保証されていますか。それとも自分で並べ替える必要がありますか」

これらを声に出して確認すると、この問題の種類を経験済みで、境界条件も理解していることを示せます。

PARTITION BY を使ったグループごとのアイランド

実際の面接データは、ほとんどの場合グループ化されています。たとえば、ユーザーごとのログインなどです。対応は機械的で、すべてのウィンドウ関数に PARTITION BY user_id を追加し、アイランドがユーザーをまたがらないようにします。

骨格は同じで、パーティションを指定するだけです。まず単一の系列の場合を習得する価値があるのは、グループごとの処理への拡張が一つの句の変更だけで済むからです。

SELECT
  user_id, day_no,
  CASE WHEN day_no - LAG(day_no)
         OVER (PARTITION BY user_id ORDER BY day_no) = 1
       THEN 0 ELSE 1 END AS is_new
FROM logins;

確認問題

パターンを見抜く直感を試してみましょう。

まとめ：問題の形を見抜く

これで、別の表現に隠されたギャップとアイランド問題を特定し、解法を説明できるようになりました。

  • 手掛かりとなる言葉：連続、継続、途切れない、連勝、欠落範囲、隣接行の統合。
  • 核心：同じ連続区間に属するすべての行に同一のグループキーを割り当て、それを GROUP BY する。
  • レシピ：LAG で新しいアイランドにフラグを付け、フラグの累積和からキーを作り、集約する。
  • 隣接の定義はドメイン固有です（整数、日付、または変化しないステータス）。
  • グループごとに分析する場合は PARTITION BY を追加し、コーディング前に範囲を確認する。

次は、最も洗練されたキー作成方法である行番号の差分テクニックをさらに詳しく見ていきます。

よくある質問

「ギャップと島問題を見分ける」レッスンは無料ですか？

はい。「ギャップと島問題を見分ける」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「ギャップと島問題を見分ける」で何を学びますか？

文章問題に現れるパターンと、核となるグループ化の考え方を特定します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「ギャップと島問題を見分ける」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. ギャップと島問題を見分ける
  2. 行番号の差分トリック
  3. 系列内のギャップを見つける
  4. 日付とステータスの変化で島を作る
← Coding Interview Prepに戻る