Implement KNN from scratch
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Without using ML libraries, implement k-Nearest Neighbors for classification. Requirements: (a) Support Euclidean and cosine distances; (b) Allow tie-breaking via class priors; (c) Analyze training time, query time, and memory complexity; (d) Extend to weighted voting with distance decay; (e) Discuss how you would scale queries to millions of points (e.g., KD-tree limitations in high dimensions, approximate methods).
Quick Answer: This question evaluates understanding of the k-Nearest Neighbors algorithm, distance metrics (Euclidean and cosine), tie-breaking with class priors, weighted voting, complexity analysis, and scalability strategies, testing competencies in algorithm implementation, model behavior, and computational trade-offs.