FastPrepClosest Random Points (Also for Core/Database Engineering)

Closest Random Points (Also for Core/Database Engineering)

Snowflake logoSnowflake● MediumINTERNOA

Problem statement

In many real-world applications, the problem of finding a pair of closest points arises. In the real world, data is usually distributed randomly. Given n points on a plane, randomly generated with uniform distribution, find the squared shortest distance between pairs of these points.

Function

closestSquaredDistance(x: int[], y: int[]) → long

Complete the function closestSquaredDistance in the editor below.

closestSquaredDistance has the following parameter(s):

  • int x[n]: each x[i] denotes the x coordinate of the ith point
  • int y[n]: each y[i] denotes the y coordinate of the ith point

Returns long: a long integer that denotes the squared shortest distance between the pairs of points

Examples

Example 1

x = [0, 1, 2]y = [0, 1, 4]return = 2

There are 3 points with x coordinates x = [0, 1, 2] and y coordinates y = [0, 1, 4]. The points have the xy coordinates (0, 0), (1, 1), and (2, 4). The closest points are (0, 0) and (1, 1), and their squared shortest distance is (1-0)^2 + (1-0)^2 = 2.

Constraints

  • 2 ≤ n
  • either n ≤ 1000 or n = 105
  • values of x[i] and y[i] are randomly generated with uniform distribution from the range [0, 109-1]

More Snowflake problems

See Snowflake hiring insights
Saved
public long closestSquaredDistance(int[] x, int[] y) {
  // write your code here
}
x[0, 1, 2]
y[0, 1, 4]
expected2
Checking account…