Bird
Raised Fist0

Implement KNN Classifier - Brute Force and KD-Tree

CODINGintermediateInterview freq: high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
⚖️
Brute Force KNN vs KD-Tree KNN

For a dataset with 1 million samples and 100 features, would you use a brute force KNN or a KD-Tree KNN? Justify your choice.

📊
Comparison
DimensionBrute Force KNNKD-Tree KNN
Training SpeedFast (O(1))Moderate (O(n log n))
Query SpeedSlow (O(n))Fast (O(log n))
Memory UsageHighModerate
Implementation ComplexityLowHigh
ScalabilityPoorGood
✅
Verdict
Default to KD-Tree KNN for datasets with n > 10,000 and d < 30 where query speed is critical. Use brute force KNN for smaller datasets or when simplicity and exact results are prioritized.
💡
Key Insight
The choice between brute force and KD-Tree KNN hinges on dataset size, dimensionality, and the importance of query speed versus implementation simplicity.
⚠️
Interview Trap
❌ Wrong: Always use KD-Tree for faster queries.
Ignoring the curse of dimensionality and the overhead of tree construction for high-dimensional or dynamic datasets.
✅ Consider the dataset size and dimensionality. Use KD-Tree for large, low-dimensional, static datasets where query speed is critical.
Brute Force KNN
"Simplicity and accuracy for small datasets"
Weaknesses
  • O(n) query time makes it impractical for large datasets
  • High memory usage due to storing all data points
  • No inherent structure to speed up queries
  • Inefficient for high-dimensional data due to curse of dimensionality
Ideal When
  • n < 10,000
  • d < 20
  • When simplicity and ease of implementation are prioritized
  • When exact nearest neighbors are required
A small-scale recommendation system prototype where simplicity and exact results are prioritized over speed.
KD-Tree KNN
"Efficient query time for low-dimensional data"
Weaknesses
  • Construction time is O(n log n), which can be slow for very large datasets
  • Inefficient for very high-dimensional data due to the curse of dimensionality
  • Complexity in implementation compared to brute force
  • Performance degrades as dimensionality increases
Ideal When
  • n > 10,000
  • d < 30
  • When query speed is critical
  • When the dataset is static and pre-processing time is acceptable
A geographic information system (GIS) where spatial queries are frequent and need to be fast.
🐍
Brute Force KNN - Example
▼ Show
Python
import numpy as np

def brute_force_knn(X_train, y_train, X_test, k):
    distances = np.sqrt(((X_train - X_test[:, np.newaxis])**2).sum(axis=2))
    nearest_indices = np.argsort(distances, axis=1)[:, :k]
    nearest_labels = y_train[nearest_indices]
    return np.array([np.bincount(labels).argmax() for labels in nearest_labels])
🐍
KD-Tree KNN - Example
▼ Show
Python
from scipy.spatial import KDTree

def kd_tree_knn(X_train, y_train, X_test, k):
    tree = KDTree(X_train)
    _, indices = tree.query(X_test, k)
    nearest_labels = y_train[indices]
    return np.array([np.bincount(labels).argmax() for labels in nearest_labels])
✅
Use Brute Force KNN When
  • •n < 10,000
  • •d < 20
  • •When exact results are more important than speed
  • •When implementation simplicity is a priority
✅
Use KD-Tree KNN When
  • •n > 10,000
  • •d < 30
  • •When query speed is critical
  • •When the dataset is static and pre-processing time is acceptable
↳
Nuances
  • For very high-dimensional data, both methods suffer due to the curse of dimensionality, but brute force may still be preferable due to its simplicity.
  • KD-Tree performance degrades significantly as dimensionality increases beyond 30, making brute force a more consistent choice in such cases.
  • In dynamic datasets where data changes frequently, the overhead of rebuilding a KD-Tree can outweigh its query speed benefits.

Practice

(1/5)
1. What does the following Python code snippet output when implementing sinusoidal positional encoding?
import numpy as np

def positional_encoding(position, d_model):
    angle_rads = np.arange(position)[:, np.newaxis] / np.power(10000, (2 * (np.arange(d_model)[np.newaxis, :] // 2)) / np.float32(d_model))
    angle_rads[:, 0::2] = np.sin(angle_rads[:, 0::2])
    angle_rads[:, 1::2] = np.cos(angle_rads[:, 1::2])
    return angle_rads

pe = positional_encoding(4, 4)
print(pe)
easy
A. A 4x4 matrix with alternating sine and cosine values
B. A 4x4 matrix with random values
C. A 4x4 identity matrix
D. A 4x4 matrix with all zeros

Solution

  1. Step 1: Understand the code logic

    The code generates a matrix where each row corresponds to a position and each column to a dimension, filled with sinusoidal values.

  2. Step 2: Eliminate wrong options

    A 4x4 matrix with all zeros is incorrect because the matrix is not filled with zeros. A 4x4 identity matrix is incorrect because the matrix is not an identity matrix. A 4x4 matrix with random values is incorrect because the values are not random but deterministic sinusoidal values.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Sinusoidal encoding alternates sine/cosine. [OK]
Hint: Sinusoidal encoding alternates sine/cosine. [OK]
Common Mistakes:
2. What is the time complexity of calculating precision, recall, and F1-score from a confusion matrix?
easy
A. O(1)
B. O(n)
C. O(n^2)
D. O(log n)

Solution

  1. Step 1: Analyze the operations

    Calculating precision, recall, and F1-score involves basic arithmetic operations on a fixed-size matrix.

  2. Step 2: Determine complexity

    These operations are constant time, O(1), as they do not depend on the size of the input data.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Fixed-size matrix operations are O(1). [OK]
Hint: Fixed-size matrix operations are O(1). [OK]
Common Mistakes:
3. 
import numpy as np

def compute_confusion_matrix(y_true, y_pred):
    cm = np.zeros((2, 2), dtype=int)
    for t, p in zip(y_true, y_pred):
        cm[t][p] += 1
    return cm

# Test case
y_true = [0, 1, 0, 1, 0, 1, 1]
y_pred = [0, 0, 0, 1, 1, 1, 1]

cm = compute_confusion_matrix(y_true, y_pred)
print(cm)
Why might this implementation produce incorrect results?
medium
A. It incorrectly indexes the confusion matrix.
B. It assumes binary classification, which may not hold.
C. It does not handle ties in predictions.
D. It uses a mutable default argument.

Solution

  1. Step 1: Analyze indexing logic

    The code uses cm[t][p] which is incorrect for confusion matrix indexing.

  2. Step 2: Identify correct logic

    Correct indexing should be cm[p][t] for predictions vs actuals.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Confusion matrix should index [pred][true]. [OK]
Hint: Confusion matrix should index [pred][true]. [OK]
Common Mistakes:
4. In a pipeline that includes flipping, cropping, and normalizing images, where should normalization be applied for best results?
medium
A. Before flipping and cropping
B. After flipping but before cropping
C. After cropping but before flipping
D. After both flipping and cropping

Solution

  1. Step 1: Understand the impact of operations

    Normalization should be the last step to ensure consistent scaling.

  2. Step 2: Evaluate each option

    Applying normalization last ensures it accounts for all transformations.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Normalize last for consistent scaling. [OK]
Hint: Normalize last for consistent scaling. [OK]
Common Mistakes:
5. In the following non-max suppression code, the function sometimes returns an empty list even when there are valid boxes. What is the likely cause? 
def non_max_suppression(boxes, scores, iou_threshold):
    indices = np.argsort(scores)[::-1]
    keep = []
    while len(indices) > 0:
        current = indices[0]
        keep.append(current)
        indices = indices[1:]
        indices = [i for i in indices if iou(boxes[current], boxes[i]) < iou_threshold]
    return keep
medium
A. The boxes array is empty.
B. The scores array is not sorted correctly.
C. The IoU function is incorrect.
D. The IoU threshold is set too high.

Solution

  1. Step 1: Analyze the condition for keeping boxes

    If the IoU threshold is too high, no boxes will be kept.

  2. Step 2: Eliminate other causes

    Sorting and empty boxes would cause different errors; incorrect IoU would not consistently return empty.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    High IoU threshold filters all boxes [OK]
Hint: High IoU threshold filters all boxes [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