コーディングインタビューの解読: スライディング ウィンドウ パターンの一部

シリーズの第 2 部では、コーディング面接の質問を解決するための最も汎用性の高いパターンの 1 つであるスライディング ウィンドウについて詳しく説明します。この手法は、合計の最大化、シーケンス内の特定の条件の検索、文字列内の部分文字列の操作など、連続する要素の部分配列または部分文字列に関連する問題を最適化する場合に非常に役立ちます。

始める前に、コーディング面接の準備のための包括的なガイドをお探しの場合は、一流テクノロジー企業への就職を真剣に考えている人にとって必携の本である『コーディング面接の突破』を参照することを検討してください。

スライディング ウィンドウ パターンの概要

スライディング ウィンドウ パターンは、より大きなデータセットからのデータのサブセット (配列の部分配列や文字列の部分文字列など) を考慮する必要がある問題を効率的に解決できる手法です。この手法では、ウィンドウを移動するたびにサブセットを再計算するのではなく、累計または条件を維持し、データ全体をスライドさせて不必要な作業を最小限に抑えます。

スライディング ウィンドウを使用する場合:

• 問題には連続した部分配列または部分文字列が含まれています。
• データセットのスライド範囲内の最大または最小の合計、カウント、またはその他の条件を見つける必要があります。
• 固定ウィンドウ サイズが必要か、または拡大または縮小する動的なウィンドウが必要です。

---

スライディング ウィンドウ アプローチの種類

1. 固定サイズのスライディング ウィンドウ

• 概要: 合計や積などの実行条件を維持しながら、配列または文字列上をスライドする固定サイズのウィンドウ。
• 例: サイズ k の部分配列の最大合計を求めます。

問題例: 整数の配列と数値 k を指定して、サイズ k の部分配列の最大合計を求めます。

def max_sum_subarray(arr, k):
    # Initialize variables to store the maximum sum and the current window sum.
    max_sum = 0
    window_sum = 0

    # First, calculate the sum of the initial window (first 'k' elements).
    for i in range(k):
        window_sum += arr[i]

    # Set the max_sum to the initial window's sum.
    max_sum = window_sum

    # Now, slide the window across the array. 
    # Start from the kth element and move until the end of the array.
    for i in range(k, len(arr)):
        # Slide the window by subtracting the element that is no longer in the window 
        # (arr[i - k]) and adding the new element (arr[i]).
        window_sum += arr[i] - arr[i - k]

        # Update max_sum if the current window sum is greater than the previous max_sum.
        max_sum = max(max_sum, window_sum)

    # Return the maximum sum found.
    return max_sum

説明:

• サイズ k のウィンドウが初期化されます。
• ウィンドウが配列内を移動すると、ウィンドウ内に存在しない要素が減算され、ウィンドウに入る新しい要素が追加されることで、スライド効果が実現されます。
• これにより、反復ごとにウィンドウ全体を合計する必要がなくなるため、O(n*k) から O(n) への強引なアプローチから問題が最適化されます。

---

2. ダイナミック スライディング ウィンドウ

• 概要: ウィンドウ サイズが固定されていない場合に使用されます。ウィンドウは、問題の要件 (合計や条件を満たすなど) に基づいて拡大または縮小します。
• 例: 合計が S 以上の最小の部分配列を見つけます。

問題例: 整数の配列と数値 S を指定して、合計が S 以上である最小の連続部分配列を見つけます。

  def smallest_subarray_with_sum(arr, S):
    # Initialize variables:
    # window_sum: to store the sum of the current window.
    # min_length: to store the length of the smallest subarray found.
    # window_start: the starting index of the sliding window.
    window_sum = 0
    min_length = float('inf')  # Start with a large number to compare minimum lengths.
    window_start = 0

    # Iterate over the array with window_end being the right boundary of the window.
    for window_end in range(len(arr)):
        # Add the current element to the window_sum.
        window_sum += arr[window_end]

        # While the current window's sum is greater than or equal to S:
        while window_sum >= S:
            # Calculate the current window size and update min_length if smaller.
            min_length = min(min_length, window_end - window_start + 1)

            # Shrink the window from the left by removing the element at window_start.
            window_sum -= arr[window_start]

            # Move the start of the window to the right.
            window_start += 1

    # If min_length was updated, return it; otherwise, return 0 (meaning no valid subarray was found).
    return min_length if min_length != float('inf') else 0

説明:

• ウィンドウは、合計が S 以上になるまで window_end を増やすことによって拡張されます。
• 条件が満たされると、ウィンドウは左 (window_start) から縮小を開始し、最小のサブ配列サイズを見つけます。
• このアプローチは、再計算を回避することで問題を O(n^2) から O(n) に減らすため、効率的です。

---

スライディング ウィンドウ ソリューションを実装する手順

1. ウィンドウの境界を定義します: ウィンドウの開始と終了を定義する必要があります。

2. 初期条件を設定します: 固定ウィンドウの場合、最初のウィンドウの和/積/条件を初期化します。動的ウィンドウの場合、初期条件は問題の目標によって異なります。

3. ウィンドウをスライドさせます:

   • 固定ウィンドウ サイズの場合: 次の要素を追加し、ウィンドウ内に存在しない要素を削除して、ウィンドウを移動します。
   • 動的ウィンドウの場合: 満たそうとしている条件に基づいてウィンドウを拡大または縮小します。

4. 結果の確認と更新: ウィンドウを移動するたびに、必要に応じて結果 (最大合計、最小長など) を更新します。

---

スライディング ウィンドウを使用した一般的な面接の質問

1. 繰り返し文字を含まない最長の部分文字列

   • 問題: 文字列 s を指定して、文字を繰り返さない最長の部分文字列の長さを見つけます。
   • パターン: 動的スライディング ウィンドウを使用して、重複文字が見つかるまで拡大し、条件が満たされるまでウィンドウを縮小します。

2. サイズ K の最大合計部分配列

   • Problem: Finden Sie bei einem gegebenen Array von ganzen Zahlen und einer ganzen Zahl k die maximale Summe eines beliebigen Unterarrays der Größe k.
   • Muster: Verwenden Sie ein Schiebefenster mit fester Größe, um die Summe von k Elementen beizubehalten und die maximale Summe zu aktualisieren, während Sie das Fenster über das Array verschieben.

3. Kleinstes Subarray mit einer gegebenen Summe

   • Problem: Finden Sie bei einem gegebenen Array positiver Ganzzahlen und einer Zahl S die Länge des kleinsten zusammenhängenden Subarrays, dessen Summe größer oder gleich S ist.
   • Muster: Verwenden Sie ein dynamisches Schiebefenster, das sich erweitert, um ein gültiges Subarray zu finden, und sich verkleinert, um seine Länge zu minimieren.

---

Schiebefenster-Hacks für Vorstellungsgespräche

1. Denken Sie in Bezug auf die Fenstergrenzen: Denken Sie zunächst darüber nach, wo das Fenster beginnen und enden soll. Dies hilft Ihnen, den genauen Bereich zu identifizieren, mit dem Sie arbeiten.

2. Verwenden Sie eine Hashmap oder ein Set für dynamische Fenster: Wenn Sie mit Teilzeichenfolgen oder eindeutigen Elementen arbeiten, verwenden Sie ein Set, um die Elemente im Fenster zu verfolgen.

3. Beginnen Sie mit Brute-Force und optimieren Sie dann: Bei manchen Problemen kann Ihnen der Beginn mit einem Brute-Force-Ansatz (z. B. die Überprüfung jedes möglichen Subarrays) dabei helfen, sich vorzustellen, wie ein Schiebefenster unnötige Ergebnisse reduzieren würde Arbeit.

4. Suchen Sie nach optimalen Bedingungen: Wenn das Problem eine Optimierungskomponente hat (wie das Minimieren oder Maximieren einer Summe oder Länge), kann ein Schiebefenster eine gute Lösung sein.

---

Abschluss

Das Sliding Window-Muster ist ein leistungsstarkes Werkzeug zur Lösung vieler Codierungsinterviewprobleme, insbesondere solcher, die Sequenzen wie Arrays oder Strings betreffen. Indem Sie sowohl Fenster mit fester Größe als auch dynamische Schiebefenster beherrschen, können Sie eine Vielzahl von Problemen effizienter lösen.

Im nächsten Artikel werden wir uns mit der Zwei-Zeiger-Technik befassen, einer weiteren äußerst effektiven Strategie, die häufig den Schiebefenster-Ansatz bei Problemen ergänzt, bei denen es um Paare oder Vergleiche zwischen Elementen geht.

Bleiben Sie gespannt auf Teil 3!

以上がコーディングインタビューの解読: スライディング ウィンドウ パターンの一部の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。