Bird
Raised Fist0

Implement NDCG for Ranking Evaluation

CODINGintermediateInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement NDCG for Ranking Evaluation
Compute Normalized Discounted Cumulative Gain for ranking tasks
codingintermediateFreq: very_highEvaluation Coding
Prerequisites:Ranking Metrics - NDCG, MAP, MRR
📝
Problem Statement

Implement the Normalized Discounted Cumulative Gain (NDCG) metric for evaluating ranking models. Given a list of relevance scores and a list of predicted scores, compute the NDCG value.

I/O Specification
Input:  Two lists of floats: relevance_scores and predicted_scores
Output: A single float representing the NDCG value
Example
{
  "input": {
    "relevance_scores": [
      3,
      2,
      3,
      0,
      1,
      2
    ],
    "predicted_scores": [
      0.9,
      0.8,
      0.7,
      0.6,
      0.5,
      0.4
    ]
  },
  "expected_output": 0.961
}
🎯
Interview Angles
  • Testing understanding of ranking metrics and their importance in ML evaluation.
  • Evaluating ability to implement metrics from scratch without relying on libraries.
  • Assessing knowledge of vectorized operations and their efficiency benefits.
  • Understanding of handling edge cases in metric computation.
🔵
Naive Approach

Sort the predicted scores and compute the DCG by iterating over the sorted list, then compute the ideal DCG by sorting the relevance scores. Finally, divide DCG by ideal DCG to get NDCG.

Time complexity is O(n log n) due to sorting operations. Space complexity is O(n) for storing sorted indices and relevance scores.
Why Insufficient
O(n log n) due to sorting operations - inefficient for very large datasets.
🐍
Naive Code
Python
import numpy as np

def dcg(scores):
    return np.sum((2**scores - 1) / np.log2(np.arange(2, scores.size + 2)))

def ndcg_naive(relevance_scores, predicted_scores):
    sorted_indices = np.argsort(predicted_scores)[::-1]
    sorted_relevance = np.array(relevance_scores)[sorted_indices]
    dcg_value = dcg(sorted_relevance)
    ideal_relevance = np.sort(relevance_scores)[::-1]
    ideal_dcg_value = dcg(ideal_relevance)
    return dcg_value / ideal_dcg_value if ideal_dcg_value > 0 else 0.0

# Driver example
relevance_scores = [3, 2, 3, 0, 1, 2]
predicted_scores = [0.9, 0.8, 0.7, 0.6, 0.5, 0.4]
print(ndcg_naive(relevance_scores, predicted_scores))  # Expected output: 0.961
💡
Key Insight
Use NumPy's advanced indexing and vectorized operations to compute DCG and ideal DCG efficiently without explicit loops.
🐍
Optimized Code
Python
import numpy as np

def dcg(scores):
    return np.sum((2**scores - 1) / np.log2(np.arange(2, scores.size + 2)))

def ndcg_optimized(relevance_scores, predicted_scores):
    sorted_indices = np.argsort(predicted_scores)[::-1]
    sorted_relevance = np.array(relevance_scores)[sorted_indices]
    dcg_value = dcg(sorted_relevance)
    ideal_relevance = np.sort(relevance_scores)[::-1]
    ideal_dcg_value = dcg(ideal_relevance)
    return dcg_value / ideal_dcg_value if ideal_dcg_value > 0 else 0.0

# Driver example
relevance_scores = [3, 2, 3, 0, 1, 2]
predicted_scores = [0.9, 0.8, 0.7, 0.6, 0.5, 0.4]
print(ndcg_optimized(relevance_scores, predicted_scores))  # Expected output: 0.961
🔍
Line-by-Line
sorted_indices = np.argsort(predicted_scores)[::-1]
Sort predicted scores in descending order to rank them.
sorted_relevance = np.array(relevance_scores)[sorted_indices]
Reorder relevance scores according to the sorted predicted scores.
dcg_value = dcg(sorted_relevance)
Compute DCG for the sorted relevance scores.
ideal_relevance = np.sort(relevance_scores)[::-1]
Sort relevance scores in descending order to get the ideal DCG.
ideal_dcg_value = dcg(ideal_relevance)
Compute the ideal DCG for the sorted relevance scores.
return dcg_value / ideal_dcg_value if ideal_dcg_value > 0 else 0.0
Return NDCG as the ratio of DCG to ideal DCG, handling division by zero.
⚡
Complexity
Time complexity is O(n log n) due to sorting operations. Space complexity is O(n) for storing sorted indices and relevance scores.
Output
0.961
🔲
Edge Cases
Empty input lists
Returns 0.0 as there are no scores to evaluate.
return dcg_value / ideal_dcg_value if ideal_dcg_value > 0 else 0.0
All zero relevance scores
Returns 0.0 as the ideal DCG is zero.
return dcg_value / ideal_dcg_value if ideal_dcg_value > 0 else 0.0
⚠️
Common Mistakes
Incorrectly sorting predicted scores in ascending order.
Symptom: Produces incorrect NDCG values.
Not handling division by zero when ideal DCG is zero.
Symptom: Causes runtime errors or incorrect outputs.
Using loops instead of vectorized operations for DCG computation.
Symptom: Results in inefficient code with higher time complexity.
Misunderstanding the log base used in DCG calculation.
Symptom: Leads to incorrect DCG and NDCG values.

Practice

(1/5)
1. 
import numpy as np

data = np.array([1, 2, 3, 4, 5])
mean = np.mean(data)
std = np.std(data)

standardized_data = (data - mean) / std
print(standardized_data)
What does the code output?
easy
A. An array with values [0, 1, 2, 3, 4]
B. An array with values [0, 0.5, 1, 1.5, 2]
C. An array with values [-1.41, -0.71, 0, 0.71, 1.41]
D. An array with values [-2, -1, 0, 1, 2]

Solution

  1. Step 1: Understand Standardization

    Standardization transforms data to have a mean of 0 and a standard deviation of 1.

  2. Step 2: Calculate the Output

    The standardized values are calculated as (data - mean) / std, resulting in [-1.41, -0.71, 0, 0.71, 1.41].

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Standardization centers data around 0. [OK]
Hint: Standardization centers data around 0. [OK]
Common Mistakes:
2. 
import numpy as np

def numerical_gradient(f, x):
    h = 1e-4
    grad = np.zeros_like(x)
    for i in range(x.size):
        x[i] += h
        fxh1 = f(x)
        x[i] -= 2 * h
        fxh2 = f(x)
        grad[i] = (fxh1 - fxh2) / (2 * h)
        x[i] += h
    return grad

# Test function
f = lambda x: x[0]**2 + x[1]**2
x = np.array([3.0, 4.0])
print(numerical_gradient(f, x))
easy
A. [6.0, 8.0]
B. [6.0001, 8.0001]
C. [5.9999, 7.9999]
D. [0.0, 0.0]

Solution

  1. Step 1: Understand the numerical gradient calculation

    The function calculates the gradient using central difference approximation.

  2. Step 2: Calculate the gradient for each element

    For x = [3.0, 4.0], the gradient is [6.0, 8.0] because the derivative of x^2 is 2x.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Central difference gives exact gradient for quadratic. [OK]
Hint: Central difference gives exact gradient for quadratic. [OK]
Common Mistakes:
3. What is the time complexity of generating a sinusoidal positional encoding matrix of size position x d_model?
easy
A. O(d_model^2)
B. O(position^2)
C. O(position * d_model)
D. O(1)

Solution

  1. Step 1: Analyze the operations

    The code iterates over each position and each dimension, performing constant-time operations.

  2. Step 2: Eliminate wrong options

    O(position^2) is incorrect because the complexity is not quadratic in position. O(d_model^2) is incorrect because the complexity is not quadratic in d_model. O(1) is incorrect because the complexity is not constant.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Iterate over position and dimension. [OK]
Hint: Iterate over position and dimension. [OK]
Common Mistakes:
4. In a multi-class classification problem, how should precision and recall be calculated from a confusion matrix?
medium
A. Calculate precision and recall for each class separately and average them.
B. Use the overall TP, FP, FN, and TN from the matrix.
C. Only calculate precision and recall for the majority class.
D. Calculate precision and recall for each class and use the minimum value.

Solution

  1. Step 1: Understand multi-class metrics

    Precision and recall should be calculated for each class separately.

  2. Step 2: Determine the correct aggregation method

    Average the precision and recall across all classes to get a balanced view.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Average class-wise metrics for multi-class. [OK]
Hint: Average class-wise metrics for multi-class. [OK]
Common Mistakes:
5. How can you optimize the numerical gradient computation for a large neural network?
hard
A. Use a smaller step size to reduce computation time.
B. Parallelize the gradient computation across multiple cores.
C. Increase the batch size during training.
D. Use a higher learning rate to speed up convergence.

Solution

  1. Step 1: Identify optimization strategies for numerical gradient computation

    Parallelizing the computation can significantly reduce time for large networks.

  2. Step 2: Eliminate ineffective strategies

    Options A, C, and D do not directly optimize the gradient computation process.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Parallelize for large networks. [OK]
Hint: Parallelize for large networks. [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard