How should I practice Best-Fit Plane Normal from 3D Points?

Start by reading the full statement, solve the visible examples, then compare the pattern against related The Voleon Group phone screen problems in FastPrep.

Is Best-Fit Plane Normal from 3D Points associated with The Voleon Group?

FastPrep tags this as a The Voleon Group phone screen coding practice problem when the problem catalog has that company and stage context.

Best-Fit Plane Normal from 3D Points

The Voleon Group● HardFULLTIMEPHONE SCREEN

Learn

Problem statement

Given three-dimensional sample points, return the unit normal vector of their least-squares best-fit plane through the point centroid.

The normal is the eigenvector corresponding to the smallest eigenvalue of the centered 3 x 3 covariance matrix, which is equivalent to the last right-singular vector of the centered point matrix. Choose the sign so the first component whose absolute value exceeds 1e-12 is positive.

Answers within 1e-6 component-wise absolute error are accepted.

Function

bestFitPlaneNormal(points: double[][]) → double[]

Examples

Example 1

points = [[0,0,0],[1,0,0],[0,1,0],[2,3,0]]return = [0,0,1]

All points lie on z = 0, whose sign-normalized unit normal is (0, 0, 1).

Example 2

points = [[1,0,0],[0,1,0],[0,0,1],[0.5,0.25,0.25]]return = [0.5773502691896258,0.5773502691896258,0.5773502691896258]

The samples lie on x + y + z = 1, so the unit normal has three equal positive components.

Constraints

3 <= points.length <= 10^5
points[i].length == 3
Coordinates are finite and have absolute value at most 10^6.
The samples are not collinear and the covariance matrix has a unique smallest eigenvalue.