このレッスンは日本語に自動翻訳されたもので、まだ人によるチェックを受けていません。表現に違和感がある場合は、英語の原文が正となります。
トップの面接コーチが学ぶのに 500 ドルも請求しない秘密は次のとおりです。コーディング面接の問題の約 90% は、わずか 7 つのデータ構造を中心に展開しています。それぞれの項目に到達するタイミングと理由を深く理解できれば、すでに戦いの半分は勝ったことになります。残りの半分は練習ですが、適切なメンタルモデルがなければ、練習は単なる暗記になってしまいます。このレッスンでは地図を提供するので、遭遇するすべての問題が身近な領域のように感じられます。
すべての技術面のインタビューは同じ井戸から得られます。遭遇する構造物を頻度順に並べると次のとおりです。
|データ構造 |面接の頻度 |コアオペレーション |面接官がそれを期待するとき | |---|---|---|---| | 配列 / 文字列 | ★★★★★ |アクセス O(1)、検索 O(n)、挿入 O(n) |ほとんどすべての問題はここから始まります | | ハッシュ マップ/セット | ★★★★★ |挿入 O(1)、ルックアップ O(1)、削除 O(1) | "これを O(n²) から O(n) に最適化します" | | リンクされたリスト | ★★★★☆ |挿入 O(1)、削除 O(1)、アクセス O(n) |ポインタ操作、サイクル検出 | | スタックとキュー | ★★★★☆ |プッシュ/ポップ O(1)、エンキュー/デキュー O(1) |解析、BFS、操作の取り消し | | 木 (バイナリ、BST) | ★★★★☆ |検索 O(log n)、挿入 O(log n) |階層データ、ソート操作 | | グラフ | ★★★☆☆ |表現に応じて |関係、パス、接続性 | | 山盛り | ★★★☆☆ |挿入 O(log n)、抽出最小 O(log n) | "k 個の最大/最小を見つけます" |
配列は、ほぼすべての面接の問題の出発点です。重要な洞察は、ほとんどの配列の問題は実際には配列に関するものではなく、2 つのポインター、スライディング ウィンドウ、またはプレフィックスの合計などのパターンの認識に関するものであるということです。
# Two Sum — the most classic interview problem
# "Given an array and target, find two numbers that add to target"
def two_sum(nums, target):
seen = {} # Hash map to store complement
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# Time: O(n), Space: O(n) — trading space for time
この「配列」問題ですら、実際にはハッシュ マップの問題であることに注目してください。そのパターンは常に繰り返されます。ブルート フォースでは配列に対してネストされたループが使用され、最適なソリューションではハッシュ マップが導入されます。
何らかの問題で行き詰まっていて総当たりが O(n²) である場合は、「ハッシュ マップでこれを O(n) に減らすことができるだろうか?」と自問してください。答えは驚くほど多くの場合「はい」です。
ハッシュ マップは、次のような場合に威力を発揮します。
// Group Anagrams — a classic hash map problem
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
サインイン してディスカッションに参加
リンク リストの問題では、ノードを見失うことなくポインターを操作する能力をテストします。必要なテクニックは次の 3 つです。
# Detect a cycle in a linked list (Floyd's Algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
スタック (LIFO) とキュー (FIFO) はより単純な構造ですが、次のようなカテゴリ全体の問題を解決します。
# Valid Parentheses — classic stack problem
def is_valid(s: str) -> bool:
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
ツリー問題には通常、再帰と 3 つの走査順序 (順、前順、後順) のいずれかが含まれます。開発するメンタル モデルは次のとおりです。「左側のサブツリーと右側のサブツリーから何が必要か、そして現在のノードでそれらをどのように組み合わせるか?」
# Maximum depth of a binary tree — the template for tree recursion
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
BST (Binary Search Tree) 問題には、1 つの重要な特性が追加されます。それは、順番に走査することでソートされた要素が得られるということです。同じ問題に「sorted」と「tree」が表示されたら、すぐに BST を考えてください。
グラフの問題は恐ろしいように感じられますが、隣接リストを作成すれば、ほとんどは BFS または DFS に軽減されます。主なスキルは次のとおりです。
# BFS shortest path in an unweighted graph
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == end:
return distance
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, distance + 1))
return -1 # Not reachable
「最大の K 個を見つける」、「最も近い K 個のリストをマージする」、または「K 個のソートされたリストをマージする」という問題がある場合、ほぼ確実にヒープ (優先キュー) が答えになります。 Python では、heapq が最小ヒープを提供します。最大ヒープの場合は、値を否定します。
import heapq
# Find the K largest elements in an array
def k_largest(nums, k):
return heapq.nlargest(k, nums) # Uses a min-heap of size k internally
挿入ごとに O(log n) の数値ストリームの中央値を見つける必要があります。どのデータ構造の組み合わせが最も適切ですか?
|構造 |アクセス |検索 |挿入 |削除 |スペース | |---|---|---|---|---|---| |配列 |お(1) | O(n) | O(n) | O(n) | O(n) | |ハッシュマップ | - | O(1)* | O(1)* | O(1)* | O(n) | |リンクされたリスト | O(n) | O(n) |お(1) |お(1) | O(n) | |スタック/キュー | O(n) | O(n) |お(1) |お(1) | O(n) | | BST（バランス） | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | |ヒープ | - | O(n) | O(log n) | O(log n) | O(n) |
* 平均的なケース。最悪の場合は、ハッシュの衝突により O(n) になります。
問題を読むときは、次の心のチェックリストを作成してください。