"AI Engineer" job postings have grown exponentially over the past two years. But here's the reality at the interview table: companies aren't looking for someone who can call openai.chat.completions.create(). They want someone who can build the system around that call. Why did vector search slow down? Why does the model keep repeating the same sentence? Why does non-English text cost more tokens? Why is the RAG pipeline retrieving irrelevant documents?
The answers to all of these live in a handful of fundamental algorithms quietly running behind the libraries. In this guide, we implement the 10 algorithms that form the backbone of LLM, RAG, and vector search systems in pure Python, with no external libraries. Each section covers where the algorithm sits in an AI system, working code, complexity, and the follow-up question you're likely to hear in an interview.
Why pure Python? In production you'll obviously use NumPy, FAISS, or Hugging Face. But when an interviewer says "write it without libraries," the candidate who knows the mechanism instantly separates from the one who memorized the API.
At a Glance: 10 Algorithms and Their Role in AI Systems
| # | Algorithm | Role in AI Systems | Complexity |
|---|---|---|---|
| 1 | Cosine Similarity | Comparing embeddings | O(d) |
| 2 | Top-K with a Heap | Nearest K results in vector search | O(n log k) |
| 3 | Stable Softmax + Top-p | LLM token sampling | O(V log V) |
| 4 | BPE Tokenization | Turning text into tokens | O(m · n) |
| 5 | Sliding Window Chunking | Splitting documents for RAG | O(n) |
| 6 | BM25 | Keyword-based retrieval | O(N · q) |
| 7 | Reciprocal Rank Fusion | Merging hybrid search results | O(Σ L) |
| 8 | Beam Search | Sequence decoding | O(T · B · V) |
| 9 | Gradient Descent | Model training | O(E · n · d) |
| 10 | K-Means (IVF) | Vector indexing | O(I · n · k · d) |
1. Cosine Similarity
The heart of every RAG system: the user's question is converted into a vector (embedding) and compared against document vectors. The standard metric for that comparison is cosine similarity. It measures the angle between two vectors, regardless of their magnitude.
import math
def dot(a: list[float], b: list[float]) -> float:
return sum(x * y for x, y in zip(a, b))
def norm(a: list[float]) -> float:
return math.sqrt(dot(a, a))
def cosine_similarity(a: list[float], b: list[float]) -> float:
na, nb = norm(a), norm(b)
if na == 0 or nb == 0:
return 0.0 # zero vector: similarity undefined, safe default
return dot(a, b) / (na * nb)
print(cosine_similarity([1, 2, 3], [2, 4, 6])) # 1.0 (same direction)
print(cosine_similarity([1, 0], [0, 1])) # 0.0 (orthogonal)
Complexity: O(d) for dimension d.
Production Tip: If you normalize vectors once at indexing time (unit length), cosine similarity at query time collapses into a simple dot product. That's exactly how FAISS performs cosine search with IndexFlatIP.
Interview Question: "Why cosine instead of Euclidean distance?" → In text embeddings, meaning is encoded in the vector's direction. A longer document may produce a vector with a larger norm without changing its meaning. On normalized vectors, both give the same ranking: ‖a − b‖² = 2 − 2·cos(a, b).
2. Top-K Selection with a Heap
You have a million document vectors and want the 5 most similar. Sorting all of them costs O(n log n). A min-heap capped at size K brings that down to O(n log k), while keeping only K items in memory.
import heapq
def top_k(query: list[float], docs: list[tuple[str, list[float]]], k: int = 3):
"""docs: (doc_id, vector) pairs. Returns the k most similar documents."""
heap: list[tuple[float, str]] = [] # min-heap: WEAKEST candidate at the root
for doc_id, vec in docs:
score = cosine_similarity(query, vec)
if len(heap) < k:
heapq.heappush(heap, (score, doc_id))
elif score > heap[0][0]:
heapq.heapreplace(heap, (score, doc_id)) # drop weakest, insert new
return sorted(heap, reverse=True)
docs = [("python", [0.9, 0.1]), ("java", [0.5, 0.5]), ("cooking", [0.0, 1.0])]
print(top_k([1.0, 0.0], docs, k=2))
# [(0.99..., 'python'), (0.70..., 'java')]
Why a min-heap? The root always holds "the worst candidate I currently have." If a new score beats it, we swap in one O(log k) operation. The pattern also works on streaming data because you never need the full dataset in memory.
Interview Question: "This is still slow on 10 billion vectors. What do you do?" → Move from exact search to approximate nearest neighbor (ANN) search: IVF (see Algorithm 10), HNSW graphs, or Product Quantization.
3. Stable Softmax, Temperature, and Top-p Sampling
At every step, an LLM produces a raw score (logit) for each token in its vocabulary. Softmax turns those scores into probabilities, and the next token is sampled. The temperature and top_p parameters control exactly this step.
import math
import random
def softmax(logits: list[float], temperature: float = 1.0) -> list[float]:
if temperature <= 0:
raise ValueError("temperature must be positive (use argmax for greedy)")
scaled = [x / temperature for x in logits]
m = max(scaled) # numerical stability trick
exps = [math.exp(x - m) for x in scaled]
total = sum(exps)
return [e / total for e in exps]
def top_p_sample(logits, p=0.9, temperature=1.0, rng=random):
probs = softmax(logits, temperature)
ranked = sorted(enumerate(probs), key=lambda t: t[1], reverse=True)
nucleus, cumulative = [], 0.0
for idx, prob in ranked: # take tokens until mass reaches p
nucleus.append((idx, prob))
cumulative += prob
if cumulative >= p:
break
total = sum(prob for _, prob in nucleus) # renormalize the nucleus
r = rng.random() * total
acc = 0.0
for idx, prob in nucleus:
acc += prob
if r < acc:
return idx
return nucleus[-1][0]
logits = [2.0, 1.0, 0.1, -3.0]
print(softmax(logits, temperature=0.5)) # "sharper" distribution
print(softmax(logits, temperature=2.0)) # "flatter" distribution
The Critical Detail: x - max. math.exp(1000) raises an OverflowError. Subtracting the maximum from every logit doesn't change the result mathematically (numerator and denominator are both multiplied by e^-m), but it pins the largest exponent at 0 and prevents overflow. Interviewers look for this exact line.
Interview Question: "What happens as temperature approaches 0?" → The distribution concentrates on the highest logit and sampling collapses into greedy decoding (argmax). That's why systems requiring deterministic output use temperature=0.
4. BPE (Byte Pair Encoding) Tokenization
GPT, Llama, and similar models don't process words; they process subword tokens. Most of those tokens are learned with BPE: repeatedly merge the most frequent adjacent pair of symbols into a new symbol.
from collections import Counter
def get_pair_counts(ids: list[int]) -> Counter:
return Counter(zip(ids, ids[1:]))
def merge(ids: list[int], pair: tuple[int, int], new_id: int) -> list[int]:
out, i = [], 0
while i < len(ids):
if i < len(ids) - 1 and (ids[i], ids[i + 1]) == pair:
out.append(new_id)
i += 2
else:
out.append(ids[i])
i += 1
return out
def train_bpe(text: str, num_merges: int):
ids = list(text.encode("utf-8")) # start: 256 possible bytes
merges: dict[tuple[int, int], int] = {}
for step in range(num_merges):
counts = get_pair_counts(ids)
if not counts:
break
pair = max(counts, key=counts.get) # most frequent pair
new_id = 256 + step
ids = merge(ids, pair, new_id)
merges[pair] = new_id
return merges, ids
text = "thinking thought thinker"
merges, ids = train_bpe(text, num_merges=10)
print(len(text.encode("utf-8")), "->", len(ids)) # bytes -> tokens
Why It Matters for Non-English Text: Characters like ş, ü, or é take 2 bytes in UTF-8. A tokenizer trained mostly on English can't merge suffixes of other languages efficiently, so the same meaning costs more tokens. That means higher API costs and a narrower effective context window for languages like Turkish.
Interview Question: "Why BPE instead of word-level tokenization?" → Word-level vocabularies map unseen words (OOV) to <UNK>. Byte-level BPE can represent any text: rare words split into pieces, frequent words become single tokens.
5. Sliding Window Chunking with Overlap
In RAG, you can't embed a whole PDF as-is. The model has a token limit, and one giant vector "dilutes" meaning. Documents are split into chunks. But hard boundaries cut sentences in half and lose context. The fix: overlap.
def chunk_tokens(tokens: list, size: int = 512, overlap: int = 64) -> list[list]:
if not 0 <= overlap < size:
raise ValueError("overlap must be between 0 and size")
step = size - overlap
chunks = []
for start in range(0, len(tokens), step):
chunks.append(tokens[start:start + size])
if start + size >= len(tokens): # last chunk reached the end
break
return chunks
tokens = list(range(10))
print(chunk_tokens(tokens, size=4, overlap=1))
# [[0, 1, 2, 3], [3, 4, 5, 6], [6, 7, 8, 9]]
Complexity: O(n). This is the production version of the pattern in PyMülakat's Two Pointers & Sliding Window module.
Interview Question: "What happens if overlap >= size?" → step becomes zero or negative, and range either raises or returns nothing. The validation on the first line prevents silent failures. Probing edge cases like this earns points in interviews.
6. BM25: The Gold Standard of Keyword Search
Embedding search captures meaning but is weak at exact matches: it can miss terms like HTTP 429, ERR_CERT_COMMON_NAME_INVALID, or a product SKU. That's where BM25, the default ranking function in Elasticsearch and OpenSearch, comes in.
import heapq
import math
from collections import Counter
class BM25:
def __init__(self, corpus: list[str], k1: float = 1.5, b: float = 0.75):
self.k1, self.b = k1, b
self.docs = [doc.lower().split() for doc in corpus]
self.N = len(self.docs)
self.avgdl = sum(len(d) for d in self.docs) / self.N
self.tfs = [Counter(d) for d in self.docs]
df = Counter(term for d in self.docs for term in set(d))
self.idf = {
t: math.log(1 + (self.N - n + 0.5) / (n + 0.5)) for t, n in df.items()
}
def score(self, query: str, i: int) -> float:
tf, dl = self.tfs[i], len(self.docs[i])
s = 0.0
for term in query.lower().split():
if term not in tf:
continue
f = tf[term]
denom = f + self.k1 * (1 - self.b + self.b * dl / self.avgdl)
s += self.idf[term] * f * (self.k1 + 1) / denom
return s
def search(self, query: str, k: int = 5):
scores = [(self.score(query, i), i) for i in range(self.N)]
return heapq.nlargest(k, scores)
bm25 = BM25([
"writing a rate limiter in python",
"fastapi 429 too many requests error",
"python generators and yield",
])
print(bm25.search("429 error", k=1)) # document at index 1
Intuition for the Two Parameters:
k1(term saturation): The 10th occurrence of a word isn't worth as much as the 1st.k1controls these diminishing returns.b(length normalization): Long documents naturally contain more words;bpenalizes them so short, focused documents get a fair chance.
Interview Question: "How is it different from TF-IDF?" → In TF-IDF, term frequency grows linearly. In BM25 it saturates and is normalized by document length.
7. Reciprocal Rank Fusion (RRF): The Glue of Hybrid Search
You have two ranked lists: one from vector search, one from BM25. You can't add the scores directly, since cosine lives in [-1, 1] and BM25 in [0, ∞). RRF ignores scores entirely and looks only at rank.
from collections import defaultdict
def reciprocal_rank_fusion(rankings: list[list[str]], k: int = 60):
scores: dict[str, float] = defaultdict(float)
for ranking in rankings:
for rank, doc_id in enumerate(ranking, start=1):
scores[doc_id] += 1.0 / (k + rank)
return sorted(scores.items(), key=lambda t: t[1], reverse=True)
vector_results = ["doc_a", "doc_b", "doc_c"]
bm25_results = ["doc_c", "doc_a", "doc_d"]
print(reciprocal_rank_fusion([vector_results, bm25_results]))
# doc_a and doc_c rank high in both lists -> they rise to the top
Why k = 60? This constant, found empirically in the original paper (Cormack et al., 2009), keeps the gap between rank 1 and rank 2 from dominating. Documents that are good in both lists beat documents that are first in only one.
Interview Question: "Why not min-max normalize the scores and add them?" → You can, but it's fragile to outliers and the distribution shifts per query. RRF is parameter-light and needs no calibration.
8. Beam Search: Smarter Decoding than Greedy
Greedy decoding picks the most likely token at each step, but the locally best choice doesn't guarantee the globally best sentence. Beam search keeps the top B candidates alive at every step.
import heapq
import math
def beam_search(step_fn, start: str, beam_width: int = 3,
max_len: int = 10, eos: str = "<eos>"):
"""step_fn(seq) -> {token: probability}, acting as the 'model'."""
beams = [(0.0, [start])] # (log-probability, sequence)
finished = []
for _ in range(max_len):
candidates = []
for logp, seq in beams:
for token, p in step_fn(seq).items():
if p > 0:
candidates.append((logp + math.log(p), seq + [token]))
if not candidates:
break
beams = []
for logp, seq in heapq.nlargest(beam_width, candidates, key=lambda c: c[0]):
(finished if seq[-1] == eos else beams).append((logp, seq))
if not beams:
break
finished.extend(beams)
# length normalization: remove the unfair advantage of short sequences
return max(finished, key=lambda c: c[0] / len(c[1]))
Why log-probabilities? Multiply 0.1 by itself 50 times and you get 1e-50; float precision collapses (underflow). Logarithms turn products into sums and keep the math numerically stable.
Interview Question: "Why doesn't ChatGPT use beam search?" → In open-ended chat, beam search tends to produce repetitive, bland text. Beam search is preferred for tasks close to a single right answer (translation, summarization); top-p/temperature sampling (Algorithm 3) is preferred for creative generation.
9. Gradient Descent
A billion-parameter transformer and a two-parameter logistic regression are trained with the same core idea: compute the gradient of the loss and take a small step in the opposite direction. Writing it from scratch once makes you truly understand what loss.backward() does.
import math
def sigmoid(z: float) -> float:
if z >= 0:
return 1 / (1 + math.exp(-z))
e = math.exp(z) # overflow-safe form for negative z
return e / (1 + e)
def train_logreg(X: list[list[float]], y: list[int], lr: float = 0.1, epochs: int = 200):
w = [0.0] * len(X[0])
b = 0.0
n = len(X)
for _ in range(epochs):
gw = [0.0] * len(w)
gb = 0.0
for xi, yi in zip(X, y):
pred = sigmoid(sum(wj * xj for wj, xj in zip(w, xi)) + b)
err = pred - yi # derivative of BCE loss w.r.t. z
for j, xj in enumerate(xi):
gw[j] += err * xj
gb += err
w = [wj - lr * g / n for wj, g in zip(w, gw)]
b -= lr * gb / n
return w, b
X = [[0.5], [1.5], [3.0], [4.0]]
y = [0, 0, 1, 1]
w, b = train_logreg(X, y, lr=0.5, epochs=500)
print(sigmoid(w[0] * 3.5 + b) > 0.5) # True
The Elegant Detail: When sigmoid and binary cross-entropy (BCE) are combined, the gradient simplifies to prediction − target. That's why err = pred - yi is so simple.
Interview Question: "What happens if the learning rate is too large?" → The loss oscillates around the minimum or diverges (NaN). Too small and training crawls. Production systems use adaptive optimizers like Adam plus learning rate schedulers.
10. K-Means and IVF Indexing
The Top-K search in Algorithm 2 scans every vector. On millions of vectors that's unacceptable. IVF (Inverted File Index) first groups vectors into clusters with K-Means; at query time, it only searches the few clusters closest to the query.
import random
def squared_dist(a: list[float], b: list[float]) -> float:
return sum((x - y) ** 2 for x, y in zip(a, b))
def kmeans(points: list[list[float]], k: int, iters: int = 20, seed: int = 42):
rng = random.Random(seed)
centroids = rng.sample(points, k)
for _ in range(iters):
clusters = [[] for _ in range(k)]
for p in points: # 1) assignment step
idx = min(range(k), key=lambda c: squared_dist(p, centroids[c]))
clusters[idx].append(p)
new_centroids = []
for c, members in enumerate(clusters): # 2) update step
if members:
new_centroids.append([sum(dim) / len(members) for dim in zip(*members)])
else:
new_centroids.append(centroids[c]) # empty cluster: keep old centroid
if new_centroids == centroids:
break # converged
centroids = new_centroids
return centroids
def ivf_search(query, centroids, buckets, nprobe=2, k=3):
"""buckets[i]: list of (doc_id, vector) assigned to cluster i."""
nearest = sorted(range(len(centroids)),
key=lambda c: squared_dist(query, centroids[c]))[:nprobe]
candidates = [doc for c in nearest for doc in buckets[c]]
return top_k(query, candidates, k) # reuse Algorithm 2
The Trade-off: Increasing nprobe raises accuracy (recall) but lowers speed. With nprobe = number of clusters, you're back to exact search. It's the classic "accuracy vs. latency" discussion in interviews.
Interview Question: "What are K-Means' weaknesses?" → K must be known in advance, it's sensitive to initial centroids (fix: k-means++), and it fails on non-spherical clusters.
How These 10 Algorithms Combine in a RAG System
The pieces you learned individually connect in this order in a real production system:
- Preparation (Offline): Documents are tokenized with BPE (4) → split into overlapping chunks (5) → embedded → indexed with K-Means/IVF (10). A BM25 index is built in parallel (6).
- Query (Online): The question is embedded → IVF finds candidate clusters → cosine similarity (1) and heap-based Top-K (2) are applied → merged with BM25 results via RRF (7).
- Generation: Retrieved chunks are added to the prompt → the LLM produces the answer with softmax + top-p (3) or beam search (8).
- Improvement: The embedding model or reranker is fine-tuned on domain data with gradient descent (9).
If you can draw this flow on a whiteboard in an interview, you're among the candidates who've earned the "AI Engineer" title.
Conclusion: Mechanisms, Not Libraries
AI tooling changes every six months. LangChain's API changes, a new vector database gets popular, a new model ships. But cosine similarity, heaps, softmax, BPE, and gradient descent have stayed the same for decades and will stay the same for the next one.
To reinforce the data structures behind these algorithms:
- Hash maps and frequency counting (BPE, BM25): Arrays & Hashing module
- Sliding window (chunking): Two Pointers & Sliding Window module
- Heaps and priority queues (Top-K, beam search): Question catalog
Reading theory isn't enough: solve these patterns in PyMülakat's live coding environment and discuss your time and space complexity with the AI interviewer.
Ready to Test Theory in a Real Exam Environment?
10 specialization modules and 200 original Python interview problems await you on PyMülakat. Write and run your code in the browser and test yourself against hidden boundary cases.
More Python Guides & Articles
Python for Loop: Lists, range, and Letter Grades
A Python for loop walks every item in a list. range, indexes, and turning scores into letter grades. The Letter Grades problem uses the same scale.
Python if, elif, else: Condition Order and Letter Grades
Python if, elif, and else run the first true branch. Test 80 before 90 and a score of 95 becomes BA. The Letter Grades problem checks this order.
Python Data Structures Guide: Stacks, Trees, and Graphs with Interactive Interview Problems
Master stacks (monotonic stack, heaps), binary trees (BST, DFS, BFS), and graphs (topological sort, Dijkstra) in Python with clean code templates and 30+ interactive interview challenges.
Python while Loop: Counter, Condition, and a Score List
A Python while loop repeats while its condition stays true. Counters, infinite loops, and walking a score list by index. The same scale is the Letter Grades problem.
Best Python Courses for Intermediate Learners: Udemy, Coursera & Book Recommendations (2026)
Curated 10-minute guide to the best Python courses for intermediate learners in 2026. Compare top Udemy deep-dives, Coursera specializations, must-read Python books, and an 8-week study roadmap.
Python Intermediate Level Project Ideas: 8 Portfolio-Ready Engineering Projects (2026)
Stop building basic calculators and to-do apps. Explore 8 intermediate level Python project ideas with working code architectures, async pipelines, custom data structures, and interview-ready system designs.
Most Asked Python Interview Questions and Answers (2026)
The most frequently asked technical Python interview questions, tricky output puzzles, and working code examples. Read this complete guide from junior to senior level before your interview.