AI面接コーディング問題でよく出る10アルゴリズム：勾配降下法からアテンション実装まで
AI面接でよく出る10のコーディング問題の詳細解説：線形回帰、ロジスティック回帰、K-Means、KNN、決定木分割、バックプロパゲーション、Self-Attention、Layer Norm、Beam Search、RAGパイプライン、各問題に評価ポイント+コードフレームワーク+注意事項
背景紹介
AI面接のコーディング問題は通常のアルゴリズム問題とは異なり、ML/DLのコアアルゴリズムをスクラッチで実装することが求められることが多いです。私は秋採用で線形回帰、Self-Attention、K-Meansなどのスクラッチ実装を求められ、最初は苦戦しましたが、1週間集中して練習し、よく出る10のアルゴリズムを筋肉記憶にまで鍛えました。今日はこの10のよく出るアルゴリズムを整理し、それぞれ評価ポイント、コードフレームワーク、注意事項を含めます。
本記事のすべてのコードはPython/NumPyで実装し、深層学習フレームワークには依存しません。面接では一般的にNumPyでのスクラッチ実装が求められ、PyTorchは使用できません。
1. 線形回帰のスクラッチ実装（勾配降下法）
評価ポイント：勾配降下法の原理、損失関数の導出、学習率の選択、特徴量の正規化
コードフレームワーク：
class LinearRegression:
def __init__(self, lr=0.01, n_iters=1000):
self.lr = lr
self.n_iters = n_iters
def fit(self, X, y):
n_samples, n_features = X.shape
self.w = np.zeros(n_features)
self.b = 0
for _ in range(self.n_iters):
y_pred = X @ self.w + self.b
dw = (2 / n_samples) * (X.T @ (y_pred - y))
db = (2 / n_samples) * np.sum(y_pred - y)
self.w -= self.lr * dw
self.b -= self.lr * db
def predict(self, X):
return X @ self.w + self.b
注意事項：①特徴量は正規化が必要、そうしないと勾配降下法の収束が遅い；②学習率が大きすぎると収束せず、小さすぎると収束が遅い、loss曲線を描いてデバッグ；③面接官は閉形式解（w = (X^T X)^{-1} X^T y）について追問する可能性あり、閉形式解が使えない場合（X^T Xが非可逆、データ量が大きすぎる）を知っておく。
2. ロジスティック回帰のスクラッチ実装
評価ポイント：Sigmoid関数、クロスエントロピー損失、勾配計算、多クラス拡張
コードフレームワーク：
class LogisticRegression:
def __init__(self, lr=0.01, n_iters=1000):
self.lr = lr
self.n_iters = n_iters
def sigmoid(self, z):
return 1 / (1 + np.exp(-np.clip(z, -500, 500)))
def fit(self, X, y):
n_samples, n_features = X.shape
self.w = np.zeros(n_features)
self.b = 0
for _ in range(self.n_iters):
z = X @ self.w + self.b
y_pred = self.sigmoid(z)
dw = (1 / n_samples) * (X.T @ (y_pred - y))
db = (1 / n_samples) * np.sum(y_pred - y)
self.w -= self.lr * dw
self.b -= self.lr * db
def predict(self, X):
return (self.sigmoid(X @ self.w + self.b) >= 0.5).astype(int)
注意事項：①Sigmoidは数値オーバーフローを防ぐためにclipが必要；②クロスエントロピー損失の勾配導出を手書きできること；③面接官は多クラス分類（Softmax回帰）について質問する可能性あり。
3. K-Meansのスクラッチ実装
評価ポイント：クラスタリング原理、初期化戦略、収束判定、K値の選択
コードフレームワーク：
class KMeans:
def __init__(self, k=3, max_iters=100):
self.k = k
self.max_iters = max_iters
def fit(self, X):
idx = np.random.choice(len(X), self.k, replace=False)
self.centroids = X[idx]
for _ in range(self.max_iters):
distances = np.linalg.norm(X[:, None] - self.centroids[None, :], axis=2)
labels = np.argmin(distances, axis=1)
new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(self.k)])
if np.allclose(self.centroids, new_centroids):
break
self.centroids = new_centroids
self.labels = labels
注意事項：①ランダム初期化は局所最適に陥る可能性、面接官はK-Means++初期化について質問する；②空クラスタの処理（ランダムに再初期化）；③K値の選択：エルボー法、シルエット係数。
4. KNNのスクラッチ実装
評価ポイント：距離度量、K値の選択、投票戦略、時間計算量
コードフレームワーク：
class KNN:
def __init__(self, k=3):
self.k = k
def fit(self, X, y):
self.X_train = X
self.y_train = y
def predict(self, X):
predictions = []
for x in X:
distances = np.linalg.norm(self.X_train - x, axis=1)
k_indices = np.argsort(distances)[:self.k]
k_labels = self.y_train[k_indices]
predictions.append(np.bincount(k_labels).argmax())
return np.array(predictions)
注意事項：①予測の時間計算量はO(ndk)、nは訓練サンプル数、dは次元数；②面接官はKD木による高速化について質問する可能性；③Kが小さすぎると過学習、大きすぎると学習不足；④距離加重KNN（距離が近いほど重みが大きい）。
5. 決定木の分割のスクラッチ実装
評価ポイント：情報利得/情報利得率/ジニ指数、分割戦略、連続値の処理
コードフレームワーク（ジニ指数の例）：
def gini(y):
classes, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 - np.sum(probs ** 2)
def best_split(X, y, feature_idx):
values = np.sort(np.unique(X[:, feature_idx]))
best_gini, best_threshold = 1, None
for i in range(len(values) - 1):
threshold = (values[i] + values[i + 1]) / 2
left_mask = X[:, feature_idx] <= threshold
gini_split = (left_mask.sum() * gini(y[left_mask]) + (~left_mask).sum() * gini(y[~left_mask])) / len(y)
if gini_split < best_gini:
best_gini, best_threshold = gini_split, threshold
return best_threshold, best_gini
注意事項：①ID3は情報利得、C4.5は情報利得率、CARTはジニ指数を使用；②情報利得は多値特徴量に偏り、利得率はこれを補正；③連続値特徴量はソート後に候補分割点を走査。
6. バックプロパゲーションのスクラッチ実装
評価ポイント：順伝播、損失計算、逆伝播、勾配更新
コードフレームワーク（単隠れ層ネットワーク）：
class NeuralNetwork:
def __init__(self, input_size, hidden_size, output_size, lr=0.01):
self.W1 = np.random.randn(input_size, hidden_size) * 0.01
self.b1 = np.zeros(hidden_size)
self.W2 = np.random.randn(hidden_size, output_size) * 0.01
self.b2 = np.zeros(output_size)
self.lr = lr
def relu(self, z):
return np.maximum(0, z)
def relu_grad(self, z):
return (z > 0).astype(float)
def forward(self, X):
self.z1 = X @ self.W1 + self.b1
self.a1 = self.relu(self.z1)
self.z2 = self.a1 @ self.W2 + self.b2
return self.z2
def backward(self, X, y, y_pred):
m = X.shape[0]
dz2 = (y_pred - y) / m
dW2 = self.a1.T @ dz2
db2 = np.sum(dz2, axis=0)
da1 = dz2 @ self.W2.T
dz1 = da1 * self.relu_grad(self.z1)
dW1 = X.T @ dz1
db1 = np.sum(dz1, axis=0)
self.W2 -= self.lr * dW2
self.b2 -= self.lr * db2
self.W1 -= self.lr * dW1
self.b1 -= self.lr * db1
注意事項：①重みの初期化は小さなランダム値を使用、ゼロ初期化は不可（対称性の問題）；②勾配はバッチサイズで割る；③面接官は勾配消失問題とその解決策について追問する可能性。
7. Self-Attentionのスクラッチ実装
評価ポイント：QKV計算、スケールドット積アテンション、マルチヘッドアテンション、マスク
コードフレームワーク：
def self_attention(X, W_q, W_k, W_v, mask=None):
Q = X @ W_q
K = X @ W_k
V = X @ W_v
d_k = Q.shape[-1]
scores = Q @ K.T / np.sqrt(d_k)
if mask is not None:
scores = np.where(mask == 0, -1e9, scores)
attn_weights = np.exp(scores - scores.max(axis=-1, keepdims=True))
attn_weights = attn_weights / attn_weights.sum(axis=-1, keepdims=True)
output = attn_weights @ V
return output, attn_weights
注意事項：①sqrt(d_k)で割ることで、ドット積が大きすぎてSoftmaxの勾配が消失するのを防ぐ；②Softmaxの数値安定性（最大値を引く）；③マスクはDecoderで未来の情報を見ないようにするために使用；④マルチヘッドアテンションは複数のSelf-Attentionを連結後に線形変換。
8. Layer Normのスクラッチ実装
評価ポイント：正規化原理、Batch Normとの違い、なぜTransformerはLayer Normを使うのか
コードフレームワーク：
def layer_norm(x, gamma=1.0, beta=0.0, eps=1e-5):
mean = x.mean(axis=-1, keepdims=True)
var = x.var(axis=-1, keepdims=True)
x_norm = (x - mean) / np.sqrt(var + eps)
return gamma * x_norm + beta
注意事項：①Layer Normは特徴次元に沿って正規化、Batch Normはバッチ次元に沿って正規化；②Transformerはシーケンス長が可変のためBatch Normが不安定になり、Layer Normを使用；③gammaとbetaは学習可能パラメータ；④RMSNormはLayer Normの簡略版（平均を引かない）。
9. Beam Searchのスクラッチ実装
評価ポイント：デコード戦略、Beam Sizeの選択、貪欲探索/サンプリングとの違い
コードフレームワーク：
def beam_search(model_init_state, decode_step, beam_width, max_len, start_token, end_token):
sequences = [[[], 0.0, model_init_state]]
for _ in range(max_len):
all_candidates = []
for seq, score, state in sequences:
if seq and seq[-1] == end_token:
all_candidates.append((seq, score, state))
continue
logits, new_state = decode_step(state, seq[-1] if seq else start_token)
log_probs = logits - np.max(logits)
log_probs = log_probs - np.log(np.sum(np.exp(log_probs)))
top_indices = np.argsort(log_probs)[-beam_width:]
for idx in top_indices:
all_candidates.append((seq + [idx], score + log_probs[idx], new_state))
sequences = sorted(all_candidates, key=lambda x: x[1], reverse=True)[:beam_width]
return sequences[0][0]
注意事項：①確率の乗算の代わりにlog確率の加算を使用し、数値アンダーフローを防止；②Beam Sizeが大きいほど探索は徹底するが遅くなる；③長さペナルティ（length penalty）で短いシーケンスへの偏りを防止；④面接官はSampling、Top-k、Top-pなどのデコード戦略との比較を質問する可能性。
10. シンプルなRAGパイプラインのスクラッチ実装
評価ポイント：ドキュメント分割、ベクトル化、類似度検索、プロンプト構築
コードフレームワーク：
def simple_rag(query, documents, embed_fn, generate_fn, top_k=3):
chunks = []
for doc in documents:
words = doc.split()
for i in range(0, len(words), 200):
chunk = " ".join(words[i:i+200])
chunks.append(chunk)
chunk_embeddings = np.array([embed_fn(c) for c in chunks])
query_embedding = embed_fn(query)
scores = chunk_embeddings @ query_embedding
top_indices = np.argsort(scores)[-top_k:][::-1]
retrieved = [chunks[i] for i in top_indices]
context = "\n".join(retrieved)
prompt = f"Based on the following context:\n{context}\n\nQuestion: {query}\nAnswer:"
answer = generate_fn(prompt)
return answer, retrieved
注意事項：①ドキュメント分割戦略（固定長 vs 意味的分割 vs 再帰的分割）；②検索はコサイン類似度を使用（正規化後にドット積）；③面接官はハイブリッド検索（ベクトル+キーワード）、リランキング（Reranker）、関連ドキュメントが検索できない場合の処理について質問する可能性。
出題まとめ
1. 線形回帰のスクラッチ実装（勾配降下法）
2. ロジスティック回帰のスクラッチ実装
3. K-Meansのスクラッチ実装
4. KNNのスクラッチ実装
5. 決定木の分割のスクラッチ実装
6. バックプロパゲーションのスクラッチ実装
7. Self-Attentionのスクラッチ実装
8. Layer Normのスクラッチ実装
9. Beam Searchのスクラッチ実装
10. シンプルなRAGパイプラインのスクラッチ実装
心得とアドバイス
1. 各アルゴリズムを最低3回はスクラッチ実装する：1回目は見ながら、2回目は記憶から、3回目は時間制限内（30分以内）で。筋肉記憶になって初めて、面接で詰まらない。
2. 数値安定性に注意：Softmaxで最大値を引く、Sigmoidでclipする、確率の積の代わりにlog確率の和を使う——これらのテクニックは面接官が重視する。
3. 暗記より理解が重要：コードを暗記するのではなく、各ステップがなぜそうなっているかを理解する。面接官はコードの修正（例：MSEをMAEに変更）を求めることがあり、理解があれば柔軟に対応できる。
4. 行列演算に習熟する：AIコーディング問題は行列演算を多用する。NumPyのブロードキャストと次元操作を完全にマスターすること。紙に次元を描いてからコードを書くことをお勧めする。
5. 書きながら説明する：面接で黙々とコードを書かず、考えを説明しながら書く。面接官は完璧な最終コードよりも思考プロセスを重視する。
FAQ
Q：面接ではどの言語を使うべきですか？
A：大部分の企業はPythonを受け入れる。一部の企業はC++を要求する。Python + NumPyが推奨。
Q：コードは実行できる必要がありますか？
A：実行できるのが理想だが、面接官は論理的正確さをより重視する。時間が足りない場合はコアロジックを書けばよい。
Q：PyTorchを使ってもいいですか？
A：一般的に不可。面接官は基盤演算の理解を見たいので、PyTorchのnn.Linear()一行では意味がない。
Q：時間が足りず書ききれない場合は？
A：コアロジック（例：Self-AttentionのQKV計算とアテンション重み）を先に書き、補助部分（マスク、Dropout）は口頭で説明する。
Q：この10個以外によく出るアルゴリズムは？
A：NMS、IoU、畳み込み操作、プーリング操作、Focal Loss、クロスエントロピー損失。これらも練習することをお勧めする。