Coding Challenges
6 questions
/
6 questions
Implementations from Scratch
Implement softmax with numerical stability.▶
Subtract max before exponentiation to prevent overflow. This doesn't change the result (exp(x-c)/Σexp(xi-c) = exp(x)/Σexp(xi)).
python
import numpy as np
def softmax(x):
"""x: (..., n_classes) - handles arbitrary batch dims"""
x = x - x.max(axis=-1, keepdims=True) # stability
e_x = np.exp(x)
return e_x / e_x.sum(axis=-1, keepdims=True)
def softmax_grad(x):
"""Jacobian of softmax. Useful for backprop derivations."""
s = softmax(x) # (n,)
return np.diag(s) - np.outer(s, s) # (n, n)Implement cross-entropy loss and its gradient.▶
Cross-entropy loss for multi-class classification. Gradient is beautifully clean: predictions minus one-hot labels.
python
import numpy as np
def cross_entropy_loss(logits, labels):
"""
logits: (batch, n_classes)
labels: (batch,) integer class indices
"""
probs = softmax(logits)
n = logits.shape[0]
# select log-prob of correct class for each example
loss = -np.log(probs[np.arange(n), labels] + 1e-9)
return loss.mean()
def cross_entropy_grad(logits, labels):
"""Returns dL/d_logits. Shape: (batch, n_classes)"""
probs = softmax(logits)
n = logits.shape[0]
probs[np.arange(n), labels] -= 1 # subtract 1 for correct class
return probs / nImplement a 2-layer MLP forward and backward pass in pure NumPy.frontier▶
Core exercise in understanding backprop. Store activations in forward pass, reuse in backward.
python
import numpy as np
class MLP:
def __init__(self, d_in, d_h, d_out, lr=0.01):
# He initialization for ReLU
self.W1 = np.random.randn(d_in, d_h) * np.sqrt(2 / d_in)
self.b1 = np.zeros(d_h)
self.W2 = np.random.randn(d_h, d_out) * np.sqrt(2 / d_h)
self.b2 = np.zeros(d_out)
self.lr = lr
def relu(self, x): return np.maximum(0, x)
def forward(self, x):
self.x = 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 # logits
def backward(self, dL_dz2):
"""dL_dz2: gradient of loss w.r.t. output logits, shape (batch, d_out)"""
self.dW2 = self.a1.T @ dL_dz2 # (d_h, d_out)
self.db2 = dL_dz2.sum(0) # (d_out,)
dL_da1 = dL_dz2 @ self.W2.T # (batch, d_h)
dL_dz1 = dL_da1 * (self.z1 > 0) # ReLU grad
self.dW1 = self.x.T @ dL_dz1 # (d_in, d_h)
self.db1 = dL_dz1.sum(0) # (d_h,)
def step(self):
self.W1 -= self.lr * self.dW1
self.b1 -= self.lr * self.db1
self.W2 -= self.lr * self.dW2
self.b2 -= self.lr * self.db2Implement K-Means clustering with K-Means++ initialization.▶
K-Means++ initialization spreads initial centers proportional to squared distance, avoiding poor local minima.
python
import numpy as np
def kmeans(X, k, n_iter=100, seed=42):
rng = np.random.default_rng(seed)
n = len(X)
# K-Means++ initialization
centers = [X[rng.integers(n)]]
for _ in range(k - 1):
dists = np.array([min(np.sum((x - c)**2) for c in centers) for x in X])
probs = dists / dists.sum()
centers.append(X[rng.choice(n, p=probs)])
centers = np.array(centers)
for _ in range(n_iter):
# Assign: (n, k) squared distances
dists = np.sum((X[:, None] - centers[None])**2, axis=-1)
labels = dists.argmin(axis=1)
# Update centers
new_centers = np.array([
X[labels == j].mean(0) if (labels == j).any() else centers[j]
for j in range(k)
])
if np.allclose(centers, new_centers, atol=1e-6):
break
centers = new_centers
inertia = sum(np.sum((X[labels == j] - centers[j])**2) for j in range(k))
return centers, labels, inertiaImplement precision, recall, F1, and BLEU score from scratch.▶
These metrics come up in both classification and NLP evaluation questions.
python
import numpy as np
from collections import Counter
def classification_metrics(y_true, y_pred):
tp = np.sum((y_pred == 1) & (y_true == 1))
fp = np.sum((y_pred == 1) & (y_true == 0))
fn = np.sum((y_pred == 0) & (y_true == 1))
precision = tp / (tp + fp + 1e-9)
recall = tp / (tp + fn + 1e-9)
f1 = 2 * precision * recall / (precision + recall + 1e-9)
return {"precision": precision, "recall": recall, "f1": f1}
def bleu_score(reference, hypothesis, max_n=4):
"""Simplified BLEU for a single reference."""
import math
ref_tokens = reference.split()
hyp_tokens = hypothesis.split()
# Brevity penalty
bp = 1.0 if len(hyp_tokens) >= len(ref_tokens) else math.exp(1 - len(ref_tokens) / len(hyp_tokens))
log_score = 0
for n in range(1, max_n + 1):
ref_ngrams = Counter(
tuple(ref_tokens[i:i+n]) for i in range(len(ref_tokens) - n + 1))
hyp_ngrams = Counter(
tuple(hyp_tokens[i:i+n]) for i in range(len(hyp_tokens) - n + 1))
clipped = sum(min(count, ref_ngrams[gram])
for gram, count in hyp_ngrams.items())
total = max(len(hyp_tokens) - n + 1, 1)
log_score += math.log(clipped / total + 1e-9) / max_n
return bp * math.exp(log_score)Implement a basic RAG pipeline in Python.startup▶
Connects embedding, vector search, and LLM generation into a single pipeline.
python
from openai import OpenAI
import numpy as np
client = OpenAI()
def embed(text):
return np.array(client.embeddings.create(
input=text, model="text-embedding-3-small"
).data[0].embedding)
def cosine_sim(a, b):
return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b) + 1e-9)
class SimpleRAG:
def __init__(self):
self.chunks = [] # list of (text, embedding)
def ingest(self, documents, chunk_size=500):
for doc in documents:
# Simple fixed-size chunking
words = doc.split()
for i in range(0, len(words), chunk_size - 50):
chunk = " ".join(words[i:i + chunk_size])
emb = embed(chunk)
self.chunks.append((chunk, emb))
def retrieve(self, query, k=3):
q_emb = embed(query)
scores = [(cosine_sim(q_emb, emb), text)
for text, emb in self.chunks]
scores.sort(reverse=True)
return [text for _, text in scores[:k]]
def query(self, question, k=3):
retrieved = self.retrieve(question, k)
context = "
---
".join(retrieved)
prompt = f"""Answer based on the context below.
Context:
{context}
Question: {question}
Answer:"""
resp = client.chat.completions.create(
model="gpt-4o-mini",
messages=[{"role": "user", "content": prompt}]
)
return resp.choices[0].message.content