FastPrep
Problem · Geometry

Closest Random Points (Also for Core/Database Engineering)

Learn this problem
● MediumSnowflakeINTERNOA
See Snowflake hiring insights

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

    drafts saved locally
    public long closestSquaredDistance(int[] x, int[] y) {
  // write your code here
}
    x[0, 1, 2]
    y[0, 1, 4]
    expected2
    checking account