The AI Interview - Master AI/ML Interviews

Given a list of points in n-dimensional space represented as tuples and a query point, implement a function to find the k nearest neighbors to the query point using Euclidean distance.

Requirements

Calculate the Euclidean distance from the query point to each point in the list
Return the k points with the smallest distances as a list of tuples
When distances are equal (ties), maintain the original order from the input list (i.e., the point appearing earlier in the input list should appear first in the result)

Examples

Example 1:

Input: points = [(1, 2), (3, 4), (1, 1), (5, 6), (2, 3)], query_point = (2, 2), k = 3

Output: [(1, 2), (2, 3), (1, 1)]

Explanation: Distances from (2,2): (1,2) has distance 1.0, (3,4) has distance 2.24, (1,1) has distance 1.41, (5,6) has distance 5.0, (2,3) has distance 1.0. The 3 nearest points are (1,2), (2,3), and (1,1). Since (1,2) and (2,3) have equal distances, (1,2) comes first because it appears earlier in the input list.

Starter Code

import numpy as np

def k_nearest_neighbors(points, query_point, k):
    """
    Find k nearest neighbors to a query point
    
    Args:
        points: List of tuples representing points [(x1, y1), (x2, y2), ...]
        query_point: Tuple representing query point (x, y)
        k: Number of nearest neighbors to return
    
    Returns:
        List of k nearest neighbor points as tuples
        When distances are tied, points appearing earlier in the input list come first.
    """
    pass

Implement K-Nearest Neighbors

Requirements

Examples

Starter Code