コーディングパターン: コーディング面接の準備に対するより賢明なアプローチ

開発者にとって、新しい資料のレビューと学習に数週間を費やすことが多いため、コーディング面接の準備は非常に困難な場合があります。 実際のところ、ほとんどの開発者はコーディング面接に向けて完全に準備ができているとは決して感じていません。開発者が LeetCode の問題の解決に何週間も費やしたにもかかわらず、まだ準備ができていないと感じることは珍しくありません。このアプローチには明らかに問題があります。 従来のコーディング面接の準備に関連するいくつかの問題を詳しく見てみましょう。 従来の面接準備の落とし穴 従来の面接準備で最もよくある落とし穴の 1 つは、 このアプローチには、明確な計画や戦略を持たずに、できるだけ多くの 問題を解決することが含まれます。これは生産的な戦略のように見えるかもしれませんが、いくつかの欠点があります。 「研磨」の練習です。 LeetCode の 構造化されたアプローチなしで問題を解決すると、自分の弱点に気づかない可能性があります。研究には意図的な計画はありません。目標は単にできるだけ多くの問題を解決することです。その結果、多くのことを学んだように感じるかもしれませんが、知識には大きなギャップがある可能性があります。 さらに、これの問題は、本質的に、多数の問題に対する解決策を暗記することを中心に展開していることです。面接官がこれまでに遭遇したものから少しでも逸脱する質問を提示した場合、100 の異なるコーディング問題の解決策を覚えようとしても効果がありません。そのため、さまざまな問題に対処する準備ができていないように感じる可能性があります。 この戦略に関する私の最後の問題は、長期的にはより多くのストレスと頭痛を引き起こすということです。転職するたびに同じ数週間の詰め込み授業を受けなければならないとしたら、毎回苦労することになるでしょう。物事を再学習し、以前と同じ問題を解決するのに何週間も費やすことになります。 これらの課題を考慮すると、より良い方法が必要です。 より良い方法: コーディング パターンを採用する では、面接の準備をコーディングするための、より効果的で持続可能なアプローチはあるのでしょうか?答えは、コーディング パターンを理解し、活用することにあります。 コーディング面接の準備をするとき、私は問題の根本的なパターンを把握することを優先します。これらのパターンには、 、 、 、 などのテクニックが含まれており、幅広いコーディングの問題に取り組むための多用途で強力なフレームワークを提供します。重点は、解決策の暗記から実証済みの問題解決テクニックに移ります。 Two-Pointers Sliding Window Modified Binary Search Topological Sort コーディング パターンに焦点を当てることで、面接の準備を大幅に合理化し、効率を高めることができます。 準備は難しくするのではなく、賢く行ってください。 何を期待します？ この記事ではこんなことをまとめてみました コーディングに関する質問に答えるために知っておく必要があります。それぞれのパターンがどのようなもので、どのように機能するのかを詳しく説明します。パターンを特定するのに役立つ主要な指標を共有し、最後に理解を確実にするのに役立つテンプレート コードを含む詳細なグラフィックを提供します。 上位 15 のコーディング パターン この記事では多くのことを取り上げていますが、より詳細なトレーニング、説明、コーディングの練習が必要な場合は、Techinterviews.io で チェックしてください 、 、さらには などの重要なトピックも取り上げます。 包括的なコーディング面接準備コースを 。 データ構造 行動面接 給与交渉 それでは、これらのコーディング パターンについて詳しく見ていきましょう。 1. リンクリストの反転 リンク リストの反転には、リンク リスト内のポインタの方向を変更して要素の順序を逆にすることが含まれます。これはデータ構造における基本的な操作であり、多くの場合、ノード参照の慎重な操作が必要になります。 これは、リンクされたリストを処理する場合に便利で、制約はその場で反転することです。 リンクされたリストを元に戻すプロセスは次のとおりです。 まずは 3 つの変数 、 、 を定義します。 current をリンク リストの先頭として設定し、previous と next を None として初期化します。 current previous next 現在の変数が ではない場合は、次の手順を実行します。 None ノードを一時変数に保存します。 次の ノードのポインタを反転して、 ノードを指すようにします。 現在の 前の 現在のノードになるように更新し、 ノードを ノードになるように更新します。 前を 現在の 次の 最後に、反転リストの 、 変数に格納されている最後に到達したノードに設定します。 先頭を 前の 主要な指標: リンクされたリスト内の要素の順序を逆にする必要があります。 問題には、リンクされたリスト内の回文のチェックが含まれます。 リスト内の特定のサブリスト内の要素の順序を逆にしたいとします。 テンプレートコード: パイソン def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev JS function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; } ジャワ public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; } 2. 修正された二分探索 さまざまな問題を解決するために古典的な二分探索アルゴリズムを適応させます。バリエーションには、要素の最初/最後の出現の検索や、回転された配列の検索が含まれます。中間点と条件を慎重に扱う必要があります。 修正二分探索は、 並べ替えられた配列、リンク リスト、または行列が与えられた場合は、 使用を検討してください。 修正された二分探索の このパターンを並べ替えられたデータ構造に適用する方法の内訳は次のとおりです。 まず、 位置と 位置の間の中間点を特定します。潜在的な整数オーバーフローを回避するには、次のように中間を計算する方が安全です: 。 開始 終了 middle = start + (end - start) / 2 キーが インデックスの要素と一致するかどうかを確認します。存在する場合は、結果として インデックスを返します。 中央の 中央の キーが インデックスの要素と一致しない場合は、次の手順に進みます。 中間 キーがインデックス の要素より小さいかどうかを評価します。そうである場合は、 を に更新して検索範囲を狭めます。 middle end middle - 1 逆に、キーがインデックス の要素より大きい場合は、 を に更新して検索範囲を調整します。 middle start middle + 1 主要な指標: ソートされたデータ構造を操作しています。 特定の要素、境界、またはピボット ポイントを効率的に見つける必要があります。 問題には、回転してソートされた配列での検索が含まれます。 テンプレートコード: パイソン def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index JS function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; } ジャワ public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; } 3. 2 つのポインタ では、データ構造 (通常は配列またはリンク リスト) を横断する 2 つのポインターを維持する必要があり、ペアまたは部分配列が関係する問題によく使用されます。異なる位置にある要素間の比較が必要な問題を最適化します。 2 つのポインター手法 この手法の利点は、特に最初に 1 つのポインターだけを使用する配列や文字列などの線形データ構造を扱う場合に、その単純さと効率にあります。 2 つのポインターを使用することで、冗長な操作を回避し、実行時の効率を大幅に向上させ、潜在的に から に削減できます。 O(n^2) O(n) パターンにはいくつかのバリエーションが含まれており、それぞれが特定のシナリオに合わせて調整されています。これらのバリエーションには、 、 、およびデータ構造内を異なる速度で移動する 2 つのポインタを含む として知られる独自の方法 テクニックとも呼ばれる) が含まれます。サイクル。 「Two Pointers」 同じ方向 反対方向 、「高速と低速」 (「ウサギとカメ」 データ構造をトラバースするために複数のポインターを使用する場合、そのアプローチは パターンに従うものとして分類できます。 「2 つのポインター」 主要な指標: 異なる位置にある要素を比較または操作する必要があります。 問題では、ソートされた配列内の要素のペアを検索する必要があります。 ソートされた配列から重複を効率的に削除したいと考えています。 線形データ構造 (配列、文字列、リンク リスト) を扱い、二次時間計算量 ( の総当たり解法) に直面する場合は、ツー ポインターの使用を検討してください。 O(n^2) テンプレートコード: バリエーションのテンプレート 「反対方向」 パイソン def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans JS function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; } ジャワ public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; } 4. スライディングウィンドウ は、配列、文字列、リンク リストなどの線形データ構造上で動的ウィンドウを維持することが含まれます。ウィンドウのサイズは特定の実装に応じて異なりますが、固定値として設定することもできます。このウィンドウの主な目的は、特定の基準を満たすデータを継続的に監視してキャプチャすることであり、サブ配列または部分文字列の問題を効率的に解決するのに特に役立ちます。 スライディング ウィンドウ手法に このパターンでは、多くの場合、ハッシュ マップを利用して、ウィンドウ内の個々のデータの追跡を容易にします。ただし、このアプローチでは時空間の複雑さが になる可能性があることに注意することが重要です。 O(n) 主要な指標: 連続または不連続の部分配列または部分文字列を分析する必要があります。 問題には、より大きなデータセット内の可変長シーケンスの追跡が含まれます。 固定長の最大合計部分配列を見つけたいとします。 問題の入力は、配列、リンク リスト、文字列などの線形データ構造です。 テンプレートコード: パイソン def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans JS function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; } ジャワ public static int slidingWindow(int[] nums) { int left = 0; List window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; } 5. 上位 K 要素 このパターンには、コレクション内の K 個の最大または最小の要素を見つけることが含まれ、多くの場合、ヒープや優先キューなどのデータ構造を使用して実装されます。これは、値または頻度に基づいて要素のサブセットを選択する場合に便利です。 特定のデータセット内で最も頻繁に出現する要素、最小の要素、または上位の 'K' 要素を見つけるように求められた場合は常に、このパターンの使用を検討できます。 仕組みは簡単です。 「K」個の要素を最小ヒープまたは最大ヒープに挿入します (これは実装によって異なります)。 ヒープに追加するときは常に、頻繁/最小/上位の「K」要素が常に維持されるように調整する必要があります。 このアプローチの利点はその効率性にあります。ヒープ自体が必要な順序を自然に維持するため、並べ替えアルゴリズムに頼る必要はありません。 主要な指標: コレクション内の最大または最小の K 個の要素を特定する必要があります。 問題には、特定の基準に基づいて要素をランク付けする必要があります。 データセット内で頻繁に使用される上位 K 個の要素を見つけたいと考えています。 テンプレートコード: パイソン import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap] JS function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); } ジャワ import java.util.*; public List topKElements(int[] arr, int k) { PriorityQueue heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; } 6. 2 つのヒープ 2 つのヒープは、2 つのヒープ (最大ヒープと最小ヒープ) を利用して、データセット内の中央値の検索など、特定の問題を最適化します。このパターンは、バランスの取れた構造を維持するのに特に役立ちます。 仕組みは次のとおりです。 最大ヒープは最大の要素を特定し、最小ヒープは最小要素を特定します。 2 つのヒープを使用します。 最大ヒープに数値の前半を入力し、その中で最大のものを見つけます。 最小ヒープに数値の後半を入力して、この部分の最小値を特定します。 現在の数値セットの中央値は、両方のヒープの最上位要素を調べることでいつでも計算できます。 主要な指標: 中央値を効率的に見つけるには、バランスの取れた構造を維持する必要があります。 問題には、動的中央値を使用したスライディング ウィンドウの問題の処理が含まれます。 値に基づいてコレクション内の要素に優先順位を付けたいとします。 テンプレートコード: パイソン import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median) JS class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median); ジャワ import java.util.*; class TwoHeaps { private PriorityQueue minHeap; // Right heap to store larger half private PriorityQueue maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median); 7. 単調なスタック 単調 - (関数または量が) 決して減少しない、または決して増加しないように変化すること。 単調スタックは、要素のスタックを非増加または非減少の順序で維持し、配列内の最も近い小さい/大きい要素を見つけるためによく使用されます。これは、特定の問題を最適化するための強力なツールです。 順序は厳密で、スタックの先頭にあるものよりも小さい (または大きい) 要素に遭遇した場合は、追加しようとしている要素が最小 (または最大) になるまで単調スタックからポップする必要があります。彼ら。 主要な指標: 要素を非増加または非減少の順序で維持する必要があります。 問題には、最も近い小さい要素または大きい要素を見つけることが含まれます。 順序を維持しながらスタックベースの操作を最適化したいと考えています。 テンプレートコード: パイソン def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] 0 && stack[stack.length - 1] stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; } 8. 深さ優先検索 ( は、後戻りする前に分岐に沿ってできるだけ深く探索するトラバーサル手法です。これは、ツリーやグラフに関係する問題、特にトラバース操作や検索操作に広く適用されます。 DFS 深さ優先検索) ツリー上で DFS を実行するには、ルートから開始する必要があります。次に、以下の手順に従います。 現在のノードを探索するには、通常は から にその子ノードにアクセスします。 左 右 、ツリーの奥深くまで進みます。 DFS プロセスを各子ノードに再帰的に適用し すべての子ノードにアクセスしたら、親ノードに 。 戻ります ツリー内のすべてのノードを訪問するまで、現在のノードの未訪問の子ごとに 。 手順 1 ～ 3 を繰り返します ツリー DFS とグラフ DFS の主な違いは、サイクルの存在にあります。ツリーには定義上サイクルがないため、ツリー DFS は各ノードが 1 回だけアクセスされることを保証し、ツリー全体が走査されると自然に終了します。対照的に、グラフ DFS では、グラフ内の循環構造を処理するための追加の手段を組み込む必要があります。サイクル内のノードを無期限に再訪問することを避けるために、グラフ DFS には、 、 なメカニズムが必要です。この違いにより、サイクルが存在すると無限ループが発生する可能性があるため、グラフ DFS はツリー DFS よりも複雑になります。 グラフ上の DFS との違い: 訪問したノードをマークしたり バックトラックを適切に処理したりするよう 主要な指標: ツリー構造を扱っているため、特定の走査順序を調べる必要があります。 問題には、パスの検索、深さの計算、または事前/順序内/事後走査の実行が含まれます。 2 つのノード間にパスが存在するかどうかを確認したいとします。 テンプレートコード: パイソン def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree JS function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree } ジャワ public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree } 9. 幅優先検索 BFS は、次のレベルに移動する前に現在の深さのすべてのノードを探索するツリーとグラフのトラバーサル手法です。 ツリー上で BFS を実行するには、ルートから開始する必要があります。次に、以下の手順に従います。 空のキュー データ構造を初期化して、アクセスするノードを追跡します。 ルートノードをキューに 。 入れます キューが空になるまでループに入ります。 キューの先頭にあるノードをデキューします。 デキューされたノードを処理します (たとえば、ノードにアクセスするか、ノードに対して何らかの操作を実行します)。 ノードのすべての子 (存在する場合) をキューに入れます。 キューが空になるまで 。 ステップ 3a ～ 3c を繰り返します BFS トラバーサルは、ツリー内のすべてのノードが左から右にレベルごとにアクセスされると完了します。 基本的に、ツリー上の BFS は、 探索します。これにより、次のレベルに移動する前に各レベルのノードを確実に訪問できるため、重み付けされていないツリー内の最短パスを見つけたり、レベルごとにツリーを探索したりするようなタスクに特に役立ちます。 ルートから開始して子に移動してから、次のレベルに進む前に、ノードをレベルごとに DFS と同様に、グラフ BFS はノード間のサイクルと複数のパスの存在に適応します。訪問したノードのマーク付けや特殊な終了条件などのメカニズムを採用し、グラフ内の複雑な関係ネットワークを効率的にナビゲートします。 グラフ上の BFS との違い: 主要な指標: ツリーをレベルごとに移動する必要があります。 問題には、重み付けされていないグラフで最短経路を見つけることが含まれます。 幅優先の方法でツリーまたはグラフを探索したいとします。 テンプレートコード: パイソン from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND JS function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached } ジャワ import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached } 10. ユニオン検索 (素集合ユニオン) としても知られる データ構造は、素セットまたは接続されたコンポーネントに関連する問題を効率的に管理および解決するために使用されます。これは、セットをマージする (結合) および要素が属するセットを決定する (検索) ための操作を提供します。 Union-Find は、クラスカルの最小スパニング ツリーやグラフのサイクル検出などのアルゴリズムでよく使用されます。 Disjoint Set Union (DSU) Union-Find Union Find は次のように実装されます。 要素のコレクションから開始します。各要素は、別々の素のセットと見なされます。各セットに一意の代表者 (多くの場合、要素自体) を割り当てます。 初期化: 2 つのセットをマージするには、ユニオン操作を実行します。 1 つのセットの代表を選択し (多くの場合、ランクやサイズなどの基準に基づいて)、それをもう一方のセットの代表の親にします。これにより、2 つのセットが効果的に接続されます。 ユニオン操作: 要素が属するセットを決定する必要がある場合は、検索操作を使用します。問題の要素から始めてツリーを上にたどって、そのセットのルート ノード (代表) を見つけます。ここでパス圧縮技術を適用すると、パスに沿った要素が直接ルートを指すようにすることで、今後の検索操作を最適化できます。 検索操作: Union-Find は、グラフ内のサイクルを検出するためによく使用されます。結合演算を実行するときに、両方の要素が同じセットに属している (つまり、同じ代表を持っている) 場合、ノード間にエッジを追加するとグラフにサイクルが作成されることを示します。 サイクル検出: ランクによる結合やパス圧縮などの結合検索操作の効率を向上させるために、さまざまな最適化手法を適用できます。 最適化: テンプレートコード: パイソン class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y) JS class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } } ジャワ import java.util.*; class UnionFind { private Map id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } } 11. トポロジカルソート 有向非巡回グラフ (DAG) は、有向サイクルのない有向グラフです。 有向非巡回グラフ ( ) のノードを線形順序で配置するアルゴリズムであり、各ノードは後続ノードの前に表示されます。これは、依存関係のスケジュール設定、コードのコンパイル、さまざまなアプリケーションにおけるタスクの優先順位の分析などのタスクにとって非常に重要です。 トポロジカル ソートは、 DAG トポロジカル ソートの段階的な内訳は次のとおりです。 依存関係のあるタスクまたはノードを表す有向非巡回グラフ ( ) から始めます。ソートされたノードを保持するキューを初期化します。 初期化: DAG グラフ内の各ノードの次数 (入力エッジの数) を計算します。 in-degree が 0 のノードには依存関係がなく、トポロジカル ソートの開始点として適しています。 次数の計算: 入次数が 0 のすべてのノードをキューに入れます。これらのノードを最初に処理できます。 初期キュー充填: キューが空でない間に、次の手順を実行します。 トポロジカル ソート ループ: キューの先頭からノードをデキューします。 ノードを処理します(たとえば、ソートされたリストにノードを追加します)。 ノードの近隣ノード (ノードが指すノード) ごとに、その入次数を 1 ずつ減分します。 デクリメントの結果として近隣の入次数が 0 になった場合は、それをキューに入れます。 トポロジの並べ替えループが完了すると、キューは空になり、並べ替えられたリストには有効なトポロジの順序ですべてのノードが含まれます。 完了: トポロジカル ソート プロセス中のいずれかの時点で、入次数 0 のノードがキューに残っていない場合、グラフ内にサイクルが存在することを示し、トポロジカル ソートが不可能になります。 サイクル検出: トポロジカル ソートの結果は、依存関係を考慮したノードの線形順序付けとなり、タスクのスケジュール設定やさまざまなアプリケーションでの実行順序の分析に適しています。 主要な指標: この問題には、依存関係のあるタスクのスケジュールまたは順序付けが含まれます。 有向非巡回グラフ (DAG) を使用しています。 タスクは、依存関係を守りながら、特定の順序で実行する必要があります。 テンプレートコード: パイソン from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None JS /** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } } ジャワ import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map findIndegree(Map > graph) { Map indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List topologicalSort(Map > graph) { List result = new ArrayList<>(); Queue queue = new LinkedList<>(); Map indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } } 12. トライ (プレフィックスツリー) 、効率的な文字列マッチングと単語の保存に使用されるツリー状のデータ構造です。共通のプレフィックスを持つ文字列を保存および検索する必要がある問題に優れています。 トライは Trie を実装する方法は次のとおりです。 空のトライから開始します。これは通常、関連付けられた文字のないルート ノードで構成されます。 初期化: トライに単語を挿入するには、ルート ノードから開始して、一度に 1 文字ずつツリーを下にたどります。単語内の各文字について: 挿入: 現在のノードの下にその文字を持つ子ノードが存在するかどうかを確認します。 存在する場合は、子ノードに移動します。 そうでない場合は、キャラクターを含む新しい子ノードを作成し、そこに移動します。 単語がトライ内に存在するかどうかを確認するには、挿入と同様の方法でトライを走査します。単語内の各文字が現在のノードの子ノードに対応していることを確認してください。トラバースが単語の終わりに到達し、最後の文字ノードに有効な終了マーカー (ブール フラグなど) がある場合、その単語はトライ内に存在します。 単語の補完: Trie は前方一致検索に優れています。特定の接頭辞を持つすべての単語を検索するには、ルート ノードでトラバースを開始し、接頭辞の文字に従ってツリーを下に移動します。接頭辞の最後の文字に到達したら、そのノードから深さ優先検索 (DFS) を実行して、同じ接頭辞を共有するすべての単語を検索できます。 前方一致検索: トライから単語を削除するには、単語の検索を実行します。単語の終わりに到達したら、終了マーカー (存在する場合) を削除します。ノードに他に子がない場合は、単語を表すトライのブランチ全体を安全に削除できます。 削除: トライは、特に大きな語彙の場合、メモリを大量に消費する可能性があります。メモリを最適化するには、圧縮 (各ノードの文字配列の代わりにマップを使用するなど) や枝刈り (子孫を持たないノードを削除する) などの手法を適用できます。 トライは、効率的な文字列マッチング、オートコンプリート候補、スペル チェッカー、および共通の接頭辞を持つ単語のインデックス作成に特に役立ちます。これらは、共有接頭辞を持つ単語や文字列をツリー状の構造に保存および検索するための、高速かつスペース効率の高い方法を提供します。 主要な指標: 文字列を扱っているため、効率的な文字列マッチングが必要です。 問題には、オートコンプリートの候補、スペル チェッカー、または共通の接頭辞を持つ単語の検索が含まれます。 単語を効率的に保存して検索したい。 テンプレートコード: パイソン class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1) JS class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } } ジャワ import java.util.*; class TrieNode { char value; Map children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } } 13. 動的プログラミング 、コンピューター科学と数学で広範囲にわたる複雑な問題を効率的に解決するために使用される強力な問題解決手法です。これは、問題をより単純なサブ問題に分割でき、これらのサブ問題の解決策を組み合わせて問題全体を解決できる場合に特に役立ちます。 動的プログラミングは その主な特徴とその仕組みは次のとおりです。 最適な下部構造: この特性は、より大きな問題に対する最適な解決策が、その小さな部分問題に対する最適な解決策から構築できるという特性を指します。 言い換えれば、DP 問題は再帰的な構造を示し、問題の最適解はその部分問題の最適解に依存します。 たとえば、グラフ内の 2 点間の最短経路を見つける場合、任意の 2 つの中間点間の最短経路も最適である必要があります。 重複するサブ問題: 計算中に同じサブ問題が複数回解決されると、重複するサブ問題が発生し、冗長な作業が発生します。 動的プログラミングは、部分問題の解をデータ構造 (多くの場合、テーブルまたはメモ化配列) に保存して再計算を回避することで、この問題に対処することを目的としています。 この部分問題解決策の保存と再利用により、アルゴリズムの時間の複雑さが大幅に軽減されます。 動的プログラミングの仕組み: DP を使用して問題を解決する最初のステップは、副次的な問題を特定することです。問題を、より小さく管理しやすいサブ問題に分割し、解決すると主要な問題の解決に貢献します。 副次的な問題を特定する: より小さな部分問題の解決策の観点から、より大きな問題の解決策を表現する再帰的解決策を開発します。この再帰的定式化により、最適な部分構造が得られます。 再帰的解決策: 重複する部分問題に対処するには、次の 2 つの一般的な手法から選択できます。 メモ化または表化: 部分問題の結果を計算時にデータ構造 (通常は配列またはハッシュ テーブル) に保存します。副問題が再び発生した場合は、その解を再計算するのではなく、ストレージからその解を取得します。これは アプローチとも呼ばれます。 メモ化: トップダウン 表 (多くの場合 2D 配列) を作成して、部分問題の解決策を 形式で保存します。最小のサブ問題を解決することから始めて、徐々に主要な問題に到達していきます。 表作成: ボトムアップ すべての副問題が解決されると、問題の再帰構造に従って副問題の解決策を組み合わせることで、主な問題の解決策を得ることができます。 最適な解決策: 動的プログラミングは、グラフ内の最短パスの検索、リソース割り当ての最適化、組み合わせのカウント、ナップザック問題の解決など、幅広い問題に適用されます。複雑な問題をより単純な部分に分解し、冗長な計算を回避することでソリューションを最適化する機能により、アルゴリズムの設計と最適化における基本的な手法となっています。 ボトムアップ アプローチ、トップダウン、メモ化、表作成 重要な概念: 主要な指標: この問題は、重複する小さなサブ問題に分割できます。 部分問題に対する解決策を保存して再利用することで最適化する必要があります。 最適化またはカウントに関する問題を解決したいと考えています。 テンプレートコード: トップダウンのメモ化のテンプレートは、動的プログラミングを実装する多くの方法の 1 つです。 パイソン def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state) JS function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); } ジャワ import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; } 14. バックトラッキング 、さまざまな可能性を試し、解決につながらない場合は元に戻すことで、段階的に問題を解決するための一般的なアルゴリズム手法です。徹底的な検索が必要な場合に使用されます。 バックトラッキングは ここでは、バックトラッキングがどのように機能するかを詳しく説明します。 バックトラッキングでは、ソリューションを一度に 1 つずつ段階的に構築することで問題空間を探索します。各ステップで決定を下し、前進します。 問題空間の探索: バックトラッキングには再帰が含まれることがよくあります。最初の部分的な解決策から始めて、それを拡張する可能なすべての方法を検討します。このプロセスは、完全な解決策が見つかるまで、または有効な解決策が存在しないことが明らかになるまで、再帰的に続きます。 再帰的な構造: 各ステップには、アルゴリズムが利用可能なオプションから選択する必要がある決定点があります。これらの選択により、探索プロセスの分岐が生じます。 決定点: 選択を行った後、アルゴリズムは現在の部分ソリューションが有効かどうかを確認します。有効な場合、アルゴリズムは次のステップに進みます。そうでない場合は、元に戻り、前の選択を取り消し、他のオプションを検討します。 ソリューションの検証: バックトラックは、次の 2 つの条件のいずれかが満たされるまで続行されます。 終了条件: 有効な解が見つかった場合、アルゴリズムは停止して解を返します。 有効な解決策が存在しないと判断され、その時点でアルゴリズムは前の決定点に戻り、さまざまなオプションを検討します。 検索を最適化するために、バックトラックには枝刈り戦略が含まれることがよくあります。枝刈りには、無効なソリューションにつながることが確実なパスの探索を回避することが含まれ、探索スペースが大幅に削減されます。 枝刈り: バックトラッキングの応用: バックトラッキングは、次のようなさまざまな問題領域で使用されます。 Sudoku や N-Queens などのパズルを解く。 順列と組み合わせの生成。 グラフやツリー内のパスの検索。 制約満足問題 (巡回セールスマン問題など)。 ゲームプレイのアルゴリズム (チェス AI など)。 主要な指標: この問題には、複数の可能性を段階的に探索することが含まれます。 さまざまなオプションを試さなければならない決定点や制約があります。 徹底的な検索を通じて、考えられるすべての解決策を見つけるか、特定の条件を満たす必要があります。 テンプレートコード: パイソン def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans JS function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; } ジャワ public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; } 15. マージ間隔 間隔のマージには、重複する間隔または隣接する間隔を統合セットに結合することが含まれます。これは、時間間隔やスケジュールに関する問題でよく使用されます。これにより、間隔ベースの操作が簡素化されます。 ここでは、マージ間隔がどのように機能するかを詳しく見ていきます。 間隔は通常 と 点のペアとして表されます (例: )。 間隔の表現: 、開始点 終了 [start, end] 間隔を効率的にマージするには、開始点に基づいて間隔を並べ替えることから始めます。これにより、重複する間隔または隣接する間隔が並べ替えられたリスト内で隣接することが保証されます。 並べ替え: マージされた間隔を保持する空のリストを初期化します。次に、ソートされた間隔を 1 つずつ繰り返します。 マージ プロセス: 現在の間隔が前の間隔と重複していない場合は、それをマージされた間隔のリストに追加します。 重複がある場合は、以前のマージされた間隔のエンドポイントを更新して、現在と以前の間隔の両方を包含し、それらを効果的にマージします。 すべての間隔を処理した後、マージされた間隔のリストには、重複しない統合された間隔が含まれます。 完了: マージ間隔の用途: マージ間隔は一般的に次の場合に使用されます。 スケジュールおよび時間管理アプリケーション。 カレンダー システムでの重複イベントの検出。 データベース クエリなどの間隔ベースのデータ分析。 リソースの割り当てと会議のスケジュールに関する問題を解決します。 この技術は、重複する間隔をマージすることにより、間隔ベースの操作を簡素化し、さまざまなアプリケーションの効率を高めます。 主要な指標: 間隔または時間ベースのデータを扱っています。 問題には、重複する区間または隣接する区間のマージが含まれます。 間隔ベースの操作を簡素化するか、イベントのスケジュールを最適化したい。 テンプレートコード: パイソン def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals JS function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; } ジャワ public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } } もっと詳しく知りたいですか? これらのパターンと、次回のコーディング インタビューでそれらをより効果的に実装する方法について詳しく知りたい場合は、今すぐ をチェックしてください。次のコーディング面接に備えるための包括的なカリキュラムを提供しており、 、 、 、さらには などのトピックもカバーしています。練習できる組み込みのコーディング ワークスペースもあります。 techinterviews.io データ構造 アルゴリズム 行動面接 給与交渉 プロモーション コード 30 ドル割引で利用して、コーディング面接の準備を今すぐ強化しましょう! TECH30 を @Limarc による注目の画像 「コードを書く開発者」 で作成されたグラフィック Okso.app