パターン認識チートシート
15種類の一般的な問題の手がかり（ソート済み配列、すべての組み合わせが必要、制約下で値を最大化するなど）を、それらを最も速く解くアルゴリズムパターンに対応付けます。
「パターン認識チートシート」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
60秒パターン認識ゲーム
実際の面接では、問題を読んでから、面接官がコーディングの開始を期待するまでに、どのアルゴリズムパターンが当てはまるかを特定する時間はおよそ60秒です。身につけるべき最も重要なスキルは、実装を暗記することではなく、どのツールを使うべきかを認識することです。
パターン認識は、問題文に含まれる問題のシグナル（単語や制約）を、既知のアルゴリズムファミリーに対応付けることで身につきます。パターンを特定できれば、実装はテンプレートに当てはめる作業になります。このレッスンでは、最もよくある15個の問題のシグナルと、それに対応するパターンを体系的なチートシートとしてまとめます。
# The recognition process
recognition_steps = [
'1. Read the problem once fully (do not start coding)',
'2. Identify the data structure: array, string, tree, graph, matrix?',
'3. Identify the ask: find min/max, count ways, enumerate, detect cycle...?',
'4. Note the constraint: n<=20 (bitmask), sorted (binary search), DAG (topo sort)?',
'5. Map signal -> pattern',
'6. State the pattern and complexity to the interviewer before coding',
'7. Handle edge cases mentally before writing',
]
for step in recognition_steps:
print(step)シグナル1〜3：配列と文字列のパターン
配列と文字列で頻出する問題のシグナルは次のとおりです。
- ソート済み配列から対象を探す → 二分探索 O(log n)
- 合計が対象値になるペアまたは3要素組を探す → ソート済みならツーポインタ O(n)、未ソートならハッシュマップ O(n)
- 条件を満たす最長または最短の部分配列・部分文字列 → スライディングウィンドウ O(n)
- 連続する部分配列の最大または最小の合計 → Kadaneのアルゴリズム O(n)
- 重複の検出 → ハッシュセット O(n) またはソート O(n log n)
配列がソート済みなら、まず二分探索を必ず検討してください。未ソートの配列で、対象の合計値を求め、O(n)が必要なら、ほとんどの場合は補数の検索にハッシュマップを使います。
# Quick recognition: array/string signals
signals = [
('Sorted array, find element', 'Binary search O(log n)'),
('Find two elements summing to K', 'Sort+two-ptr O(n log n) or hash O(n)'),
('Longest subarray with property P', 'Sliding window (variable size) O(n)'),
('Max sum contiguous subarray', 'Kadane algorithm O(n)'),
('Anagram/permutation check', 'Frequency map (Counter) O(n)'),
('Contains duplicate', 'Hash set O(n)'),
('Merge two sorted arrays/lists', 'Two pointers O(n+m)'),
('Rotate / shift array', 'Reverse trick O(n) in-place'),
('Next permutation', 'Find rightmost ascent + swap + reverse'),
('Maximum product subarray', 'Track max and min (handles negatives)'),
]
for signal, pattern in signals:
print(f'{signal:45s} => {pattern}')シグナル4〜6：木とグラフのパターン
木とグラフの問題のシグナルと、それに対応するパターンは次のとおりです。
- レベルごとの走査／重みなしグラフでの最短経路 → dequeを使ったBFS O(V+E)
- すべての経路の探索／サイクル検出／DFSの順序 → 再帰または反復によるDFS O(V+E)
- BST＋中順走査の性質（k番目の要素、ソート順） → 中順DFS O(n)
- 最小共通祖先 → 経路を追跡する再帰的な下降 O(n)
- 連結成分／2つのグループの統合 → DSU O(n × alpha(n))
# Tree/graph signal recognition
tree_graph_signals = [
('Level-order / minimum depth / word ladder', 'BFS with deque'),
('All paths / path sum / all permutations tree', 'DFS recursive'),
('Cycle detection (undirected)', 'DFS with parent / DSU'),
('Cycle detection (directed) / course schedule', 'DFS three-color / Kahn topo sort'),
('Shortest path weighted graph', 'Dijkstra (non-neg) / Bellman-Ford (neg)'),
('All-pairs shortest path', 'Floyd-Warshall O(V^3)'),
('Topological order', 'Kahn BFS topo sort'),
('Min spanning tree', 'Kruskal (DSU) / Prim (heap)'),
('Dynamic connectivity / union-find', 'DSU path compression + union by rank'),
('Autocomplete / prefix search', 'Trie'),
('BST kth smallest / range sum', 'In-order DFS'),
]
for signal, pattern in tree_graph_signals:
print(f'{signal:50s} => {pattern}')シグナル7〜9：動的計画法のシグナル
DPのシグナルは、最も認識が難しいものです。次のキーワードに注目してください。
- 「…する方法の数」 → カウントDP（部分問題の個数を加算）
- 「…を達成するための最小または最大コスト」 → 最適化DP（部分問題の最小値または最大値を選択）
- 「…を達成できるか」（実現可能性） → ブールDP（部分問題のOR）
- 2つの文字列インデックスで定義される部分問題 → 2次元DP（LCS、編集距離）
- 容量制約の下で項目を選択またはスキップする → ナップサックDP
- 最適部分構造＋重複する部分問題 → 再帰木で同じ呼び出しが繰り返されていないか確認 → DP
# DP signal recognition
dp_signals = [
('Number of ways to climb stairs / decode string', '1D DP (Fibonacci-like)'),
('Minimum cost to reach end / coin change', '1D DP (greedy fails)'),
('Longest increasing subsequence', '1D DP O(n^2) or patience sort O(n log n)'),
('Longest common subsequence of two strings', '2D DP O(mn)'),
('Edit distance between two strings', '2D DP O(mn) (LCS variant)'),
('Partition array into two equal subsets', '0/1 knapsack boolean DP'),
('Fill knapsack with max value under weight limit', '0/1 knapsack optimisation DP'),
('Burst balloons / matrix chain multiplication', 'Interval DP'),
('Palindrome partitioning minimum cuts', 'Interval DP + prefix palindrome'),
('Rob houses in circle', '1D DP × 2 (linear sub-problems)'),
]
for signal, pattern in dp_signals:
print(f'{signal:55s} => {pattern}')シグナル10〜12：ヒープ、スタック、貪欲法のシグナル
ヒープ、単調スタック、貪欲法の問題で見られるシグナルは次のとおりです。
- 上位K個の要素／k番目に大きいまたは小さい要素 → ヒープ（上位K個の最大要素には最小ヒープ、k番目に小さい要素には最大ヒープ） O(n log k)
- ストリーミング中央値 → 2つのヒープ（小さい側の最大ヒープ＋大きい側の最小ヒープ）
- 次に大きいまたは小さい要素 → 単調スタック O(n)
- 最大面積の長方形／雨水のトラッピング → 単調スタック O(n)
- 区間スケジューリング／重複しない区間の最大化 → 貪欲法（終了時刻でソート）
# Heap / stack / greedy signals
heap_stack_greedy = [
('Top-K frequent elements', 'Min-heap size K: O(n log k)'),
('Kth largest in array', 'Max-heap pop K times: O(n + k log n)'),
('Streaming median', 'Two heaps (max + min): O(log n) per insert'),
('Merge K sorted lists', 'Min-heap of (val, list_idx): O(n log k)'),
('Next greater element', 'Monotonic decreasing stack: O(n)'),
('Largest rectangle in histogram', 'Monotonic increasing stack: O(n)'),
('Sliding window maximum', 'Monotonic decreasing deque: O(n)'),
('Trapping rain water', 'Two pointers OR monotonic stack: O(n)'),
('Jump game reachability / minimum jumps', 'Greedy range expansion: O(n)'),
('Merge overlapping intervals', 'Sort by start, linear scan: O(n log n)'),
('Gas station circular', 'Greedy: start from reset point: O(n)'),
('Task scheduler with cooldown', 'Greedy: sort by frequency: O(n log n)'),
]
for signal, pattern in heap_stack_greedy:
print(f'{signal:45s} => {pattern}')シグナル13〜15：バックトラッキングとビット操作
バックトラッキングとビット操作の問題で見られるシグナルは次のとおりです。
- すべての部分集合／順列／組み合わせを生成する → バックトラッキング O(2^n または n!)
- 制約充足（Nクイーン、数独） → 枝刈りを伴うバックトラッキング
- 1つだけ欠けている要素／一意の要素を探す → XOR O(n)、空間計算量O(1)
- 小さな集合のすべての部分集合を列挙する（n ≤ 20） → ビットマスクによる2^n列挙
- セットビットの個数を数える／2の累乗かどうかを確認する → ビットトリック（n & (n-1)）
- 小さな集合を使った状態圧縮DP → ビットマスクDP O(2^n × n)
# Backtracking and bit signals
bt_bit_signals = [
('Generate all subsets of array', 'Backtracking O(n * 2^n) / bitmask'),
('Generate all permutations', 'Backtracking O(n * n!)'),
('Combination sum with target', 'Backtracking with pruning'),
('Word search in grid', 'Backtracking DFS on grid O(m*n*4^L)'),
('N-queens placement', 'Backtracking with column/diag sets'),
('Find single unique element (all others x2)', 'XOR all: O(n) O(1)'),
('Missing number in 0..n', 'XOR or sum formula: O(n) O(1)'),
('Count set bits in n', 'n &= n-1 loop or DP O(n)'),
('Check power of two', 'n > 0 and n & (n-1) == 0'),
('Travelling salesman (n<=20)', 'Bitmask DP O(2^n * n^2)'),
('Number with max XOR in array', 'Trie on binary representation'),
]
for signal, pattern in bt_bit_signals:
print(f'{signal:50s} => {pattern}')制約の分析：Nからわかること
入力サイズの制約nから、許容される時間計算量、ひいては使うべきアルゴリズムファミリーが直接わかります。
- n ≤ 20：O(2^n)またはO(n!)が許容されます — ビットマスクDP、バックトラッキング
- n ≤ 500：O(n³)が許容されます — Floyd-Warshall、総当たりDP
- n ≤ 5000：O(n²)が許容されます — 素朴なDP、二次時間のソート
- n ≤ 10^6：O(n log n)が必要です — マージソート、ヒープ、二分探索
- n ≤ 10^8：O(n)が必要です — ツーポインタ、スライディングウィンドウ、線形DP
この制約分析は、問題を読んだ直後、どのアルゴリズムを選ぶか決める前に行う最初のステップにしてください。
# Constraint -> acceptable complexity -> algorithm family
complexity_map = [
('n <= 20', 'O(2^n) or O(n!)', 'Bitmask DP, backtracking/permutations'),
('n <= 500', 'O(n^3)', 'Floyd-Warshall, cubic DP, brute force'),
('n <= 5000', 'O(n^2)', 'Quadratic DP, bubble/insertion sort'),
('n <= 100000', 'O(n log n)', 'Merge sort, heap, binary search, topo sort'),
('n <= 1000000', 'O(n)', 'Linear DP, two pointers, sliding window, hash'),
('n <= 10^8', 'O(n) tight', 'Only simplest O(n) — no large constants'),
('n <= 10^18', 'O(log n) or O(1)', 'Math / number theory, binary search on answer'),
]
print(f'{'Constraint':15s} {'Complexity':15s} {'Algorithm Family'}')
print('-'*70)
for constraint, complexity, algorithms in complexity_map:
print(f'{constraint:15s} {complexity:15s} {algorithms}')問題 → パターン：早押し練習
この対応付けが自動的にできるようになるまで練習してください。各問題の説明を読み、解答を見る前にパターンを特定します。速度が重要です。面接では60秒未満でパターンを特定できるようにしてください。
- 「ソート済み配列が与えられたとき、合計がKになる2つの要素があるか調べる」
- 「木が与えられたとき、直径（任意の2ノード間の最長経路）を求める」
- 「クールダウン時間kがあるn個のタスクが与えられたとき、CPU区間の最小数を求める」
- 「文字列が与えられたとき、最長の回文部分文字列を求める」
- 「1〜nの数列から1つだけ欠けているとき、欠けている数を求める」
# Quick-fire pattern recognition answers
problems = [
('Sorted array: two elements sum to K',
'Two pointers (left from start, right from end): O(n)'),
('Tree diameter (longest path)',
'DFS returning (height, max_diameter) pair: O(n)'),
('Task scheduler with cooldown k',
'Greedy: (max_freq - 1)*(k+1) + count_of_max_freq: O(n log n)'),
('Longest palindromic substring',
'Expand around centre OR Manacher: O(n^2) or O(n)'),
('Missing number in 1..n',
'XOR all indices and values: O(n) O(1)'),
('Number of islands in binary grid',
'BFS/DFS flood fill counting connected components: O(m*n)'),
('Decode string like 3[a2[bc]] -> aaabcbcaabcbc',
'Stack to handle nested brackets: O(n)'),
('Valid parentheses [(){[]}]',
'Stack push open, pop+match on close: O(n)'),
]
for problem, solution in problems:
print(f'Q: {problem}\nA: {solution}\n')危険信号：パターンがうまくいかないとき
経験豊富なエンジニアでも、最初に間違ったパターンを選ぶことがあります。現在のアプローチが間違っていることを示す次のシグナルを認識し、方針を切り替えてください。
- O(n²)の解法は小さなテストには通るが、大きな入力ではTLEになる → ハッシュマップ、二分探索、または単調なデータ構造が必要です
- 貪欲法が反例で失敗する → DPを試してください
- DPの状態空間が大きすぎる → 貪欲法の証明、またはより賢い状態定義を検討してください
- BFSで誤った答えになる → 重みなしグラフ用のBFSではなく、重み付きグラフ用のDijkstraが必要か確認してください
- nullポインタ例外が発生する → 実装を始める前に、基本ケースとエッジケースのガードを追加してください
# Red flags and recovery strategies
red_flags = [
('TLE on large n', 'Check complexity; switch from O(n^2) to O(n log n) or O(n)'),
('WA with greedy', 'Find a counter-example; switch to DP or prove exchange arg'),
('DP table huge', 'State compression (bitmask/rolling array) or different state'),
('BFS gives wrong shortest path', 'Check if edges have weights; use Dijkstra instead'),
('Stack overflow in recursion', 'Add memoisation or convert to iterative with explicit stack'),
('Off-by-one in binary search', 'Use half-open intervals [lo, hi); verify with 2-element test'),
('DSU wrong answer', 'Check 0-indexed vs 1-indexed; check union direction'),
('Backtracking TLE', 'Add pruning conditions; ensure undo step is correct'),
]
print('Pattern | Recovery')
print('-'*70)
for flag, recovery in red_flags:
print(f'{flag:40s} => {recovery}')面接でパターン認識を伝える
面接でパターン認識を言葉にすると、専門知識を示せるだけでなく、方向性が間違っている場合に面接官から助言を受ける機会にもなります。次の構成を使って説明してください。
- 「配列がソート済みなので、二分探索を使うことを考えています……」
- 「この問題は最大部分配列を求めるものなので、典型的なKadaneのアルゴリズムの問題です……」
- 「すべての部分集合が必要なので、再帰木を使ったバックトラッキングが考えられます……」
- 「制約n ≤ 20から、2^n = 1Mは許容されるため、ビットマスクDPが使えそうです……」
パターンを述べた後、コードを1行も書かないうちに、時間計算量と空間計算量を説明してください。これにより、実装の前に効率を考えていることを示せます。
# Interview communication template
def communicate_approach(problem, pattern, time_complexity, space_complexity, edge_cases):
print(f'Problem: {problem}')
print(f'Pattern: {pattern}')
print(f'Time: {time_complexity}, Space: {space_complexity}')
print(f'Edge cases to handle: {", ".join(edge_cases)}')
print()
# Example communications
communicate_approach(
problem='Find longest substring without repeating characters',
pattern='Sliding window with a set tracking current window characters',
time_complexity='O(n)',
space_complexity='O(min(n, alphabet_size))',
edge_cases=['empty string', 'all same characters', 'all unique characters']
)
communicate_approach(
problem='Given sorted matrix, find if target exists',
pattern='Binary search or staircase search (top-right corner): eliminate row or column each step',
time_complexity='O(m + n)',
space_complexity='O(1)',
edge_cases=['empty matrix', 'single element', 'target at corners']
)パターン認識の語彙を増やす
パターン認識を身につける最も速い方法は、問題を無作為に解くのではなく、テーマごとにまとめて解くことです。1週間はスライディングウィンドウの問題だけに取り組み、次にツーポインタの問題、続いてDPの問題に取り組みます。同じ種類の問題を20問解くと、そのパターンを一目で認識する直感が急速に身につきます。
各問題を解いた後に、「パターンメモ」を1行で書いてください。問題のシグナルと、それによって導かれたパターンを記録します。自分専用のチートシートを作りましょう。テーマごとにまとめて200問解けば、面接問題のおよそ90%を30秒未満で認識できるようになります。残りの10%は、経験豊富なエンジニアでも注意深い分析が必要です。
# Personal pattern note template
pattern_notes = [
{'signal': 'sorted array + two sum', 'pattern': 'two pointers', 'example': 'LC 167 Two Sum II'},
{'signal': 'longest X without repeating', 'pattern': 'sliding window + set', 'example': 'LC 3 Longest Substring'},
{'signal': 'max sum subarray', 'pattern': 'Kadane', 'example': 'LC 53 Max Subarray'},
{'signal': 'permutations/subsets', 'pattern': 'backtracking', 'example': 'LC 46 Permutations'},
{'signal': 'tree path sum', 'pattern': 'DFS with accumulator', 'example': 'LC 112 Path Sum'},
{'signal': 'course schedule', 'pattern': 'Kahn topo sort', 'example': 'LC 207 Course Schedule'},
{'signal': 'top-K elements', 'pattern': 'min-heap size K', 'example': 'LC 215 Kth Largest'},
]
print(f'{'Signal':40s} {'Pattern':30s} {'Example'}')
print('-'*90)
for note in pattern_notes:
print(f'{note["signal"]:40s} {note["pattern"]:30s} {note["example"]}')理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、パターン認識によって問題のシグナルをアルゴリズムファミリーに対応付けられること、ソート済み配列は二分探索、「すべての部分集合」はバックトラッキング、「最小コスト」はDPを示すこと、制約nから許容される計算量がわかること：n ≤ 20ならO(2^n)が許容され、n ≤ 10^6ならO(n log n)以下が必要になること、そしてコーディング前にパターンと計算量を言葉にすると、専門知識を示し、面接官からフィードバックを受けられることを学びました。次は、簡単な問題と中程度の問題を時間制限付きの模擬面接で解き、パターン認識を実践します。
よくある質問
「パターン認識チートシート」レッスンは無料ですか？
はい。「パターン認識チートシート」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「パターン認識チートシート」で何を学びますか？
15種類の一般的な問題の手がかり（ソート済み配列、すべての組み合わせが必要、制約下で値を最大化するなど）を、それらを最も速く解くアルゴリズムパターンに対応付けます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「パターン認識チートシート」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。