ML coding · Ranking and evaluation metrics
NDCG at k
rels lists the relevance grades (non-negative integers) of the items a system returned,
in the order it returned them. Compute NDCG@k:
- DCG@k = Σ over the first k positions i = 0, 1, … of (2reli − 1) / log₂(i + 2).
- IDCG@k is DCG@k of the same grades sorted from highest to lowest.
- Return DCG@k / IDCG@k, or 0.0 if IDCG@k is 0. If k exceeds the list length, use the whole list.
Examples
Input rels = [3, 2, 3, 0, 1, 2], k = 6
Output 0.9488
A good ranking with one swap near the top.
Input rels = [0, 0, 0], k = 3
Output 0
No relevant items: 0.0 by definition.
Constraints
- 1 ≤ len(rels) ≤ 10⁵, 0 ≤ rel ≤ 10, 1 ≤ k
- Checked to a relative tolerance of 10⁻¹²
Hints
Hint 1
Position i (from 0) is discounted by log₂(i + 2): the top item by log₂ 2 = 1.
Hint 2
The ideal ranking is the grades sorted in descending order, truncated to k.
Hint 3
Guard the division: a list with no relevant items has IDCG 0.
Where candidates go wrong
- Discounting the top item by log₂(1) = 0.
- Using rel instead of 2^rel − 1 as the gain, a different (also common) convention.
- Building the ideal ranking only from the first k items, which overstates NDCG.
The idea
Truncate to k, compute the gains and the discounts as arrays, and take a dot product. Do the same for the grades sorted in descending order. Divide, guarding against zero.
Time O(n log n) · Space O(n)
Reference solution
import numpy as np
def ndcg_at_k(rels, k):
r = np.asarray(rels, dtype=float)
def dcg(x):
x = x[:k]
return float(((2.0 ** x - 1.0) / np.log2(np.arange(2, x.size + 2))).sum())
ideal = dcg(np.sort(r)[::-1])
return 0.0 if ideal == 0 else dcg(r) / idealFollow-ups an interviewer asks
- Mean NDCG over many queries, and why each query is normalised before averaging.
- Graded gains versus binary relevance: when NDCG reduces to a discounted precision.
- Mean reciprocal rank, for when only the first relevant result matters.
Python runs in your browser with NumPy. The first run downloads the runtime, which takes a few seconds.
Why interviewers ask it
The standard offline metric for search and recommendation. The question tests the discount, the ideal ranking and the case with no relevant items.
The theory behind it is in the lesson NDCG, calibration error and macro-F1 from scratch.
Keep going
NDCG at k
Normalised discounted cumulative gain for a ranked list: exponential gains, a log discount, and the ideal ranking computed from all items..
Open the problem → Medium15 minExpected calibration error
Expected calibration error for binary predictions with equal-width bins, empty bins skipped, and every bin edge defined exactly..
Open the problem → Easy10 minMacro-averaged F1 across classes
Per-class F1 from a confusion of labels and predictions, averaged over every class that appears in either, without scikit-learn..
Open the problem →