Find K Nearest Points
Company: Snapchat
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an array of 2D points `points`, where `points[i] = [x_i, y_i]`, and an integer `k`, return any `k` points whose Euclidean distance to the origin `(0, 0)` is smallest. If multiple answers are valid, return them in any order.
Follow-up: design a solution with time complexity `O(n log k)` and `O(k)` extra space beyond the output.
Quick Answer: This question evaluates proficiency with Euclidean distance metrics, selection algorithms, and efficient data structures for partial sorting, while requiring reasoning about algorithmic time and space complexity (the follow-up specifies O(n log k) time and O(k) extra space).