Find the words whose embeddings are most similar to a given word.
What to build
A program that lists the k nearest neighbours of a word in an embedding table.
Requirements
- Compare the query word with every other word by cosine similarity.
- Print the k most similar as
WORD S, with S to 3 decimal places, highest first; equal similarities in alphabetical order.
Input
Line 1: n. Then n lines word x1 x2 .... Then a line query k.
Output
k lines.
Constraints
2 ≤ n ≤ 1000; 1 ≤ k < n; no vector is all zeros.
Example
Input:
5
king 5 1 0
queen 5 4 0
man 1 0 0
woman 1 3 0
apple 0 1 5
king 3
Output:
man 0.981
queen 0.888
woman 0.496
Why it works
Cosine similarity ranks the other words by how closely their embeddings point in the query word's direction, which is how semantic neighbours are found.
Examples
Example 1 · Input
5 king 5 1 0 queen 5 4 0 man 1 0 0 woman 1 3 0 apple 0 1 5 king 3
Expected output
man 0.981 queen 0.888 woman 0.496
Example 2 · Input
3 a 1 0 b 0 1 c 1 1 a 1
Expected output
c 0.707
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Compute the cosine similarity between the query word's vector and every other word's vector.
Hint 2
Sort by similarity from highest to lowest, then alphabetically, and keep k.
Solution
Show one correct solution (try it yourself first)
import math
n = int(input())
vectors = {}
for _ in range(n):
word, *nums = input().split()
vectors[word] = list(map(float, nums))
query, k = input().split()
def cosine(a, b):
dot = sum(x * y for x, y in zip(a, b))
return dot / (math.sqrt(sum(x * x for x in a)) * math.sqrt(sum(y * y for y in b)))
scores = [(word, cosine(vectors[query], v)) for word, v in vectors.items() if word != query]
scores.sort(key=lambda ws: (-ws[1], ws[0]))
for word, s in scores[: int(k)]:
print(word, f"{s:.3f}")