One-Nearest-Neighbor Classification
OpenAI● EasyNEW GRADFULLTIMEPHONE SCREENProblem statement
You are given a nonempty set of labeled training samples and a set of query samples. Each sample is an integer feature vector.
For every query, find the single training sample with the smallest squared Euclidean distance:
distance(a, b) = sum((a[i] - b[i])^2)
If several training samples have the same minimum distance, choose the one that appears earliest in trainingFeatures.
Return the chosen training label for every query, in query order.
Function
classifyOneNearestNeighbor(trainingFeatures: int[][], trainingLabels: int[], queries: int[][]) → int[]Examples
Example 1
trainingFeatures = [[0,0],[2,2],[5,5]]trainingLabels = [10,20,30]queries = [[1,1],[4,4]]return = [10,30]For [1,1], the first two training samples are tied at squared distance 2, so the earlier sample supplies label 10. For [4,4], the nearest sample is [5,5], which supplies label 30.
Example 2
trainingFeatures = [[0],[2]]trainingLabels = [7,9]queries = [[1]]return = [7]The query is one unit from both training samples, so the stable tie rule selects the first label, 7.
Example 3
trainingFeatures = [[-2,1],[3,4]]trainingLabels = [5,8]queries = [[3,4],[-1,1]]return = [8,5]The first query exactly matches the second training sample. The second query is closest to [-2,1].
Constraints
1 <= trainingFeatures.length == trainingLabels.length <= 2000.1 <= queries.length <= 2000.1 <= trainingFeatures[i].length == queries[j].length <= 100.-10^4 <= trainingFeatures[i][k], queries[j][k] <= 10^4.- Every squared-distance sum fits in a signed 64-bit integer.