FastPrepFastPrep
Problem Brief

Closest Random Points (Also for Core/Database Engineering)

INTERNOA
See Snowflake online assessment and hiring insights

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 Description

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

    1Example 1

    Input
    x = [0, 1, 2], y = [0, 1, 4]
    Output
    2
    Explanation
    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

    Limits and guarantees your solution can rely on.

    • 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]
    public long closestSquaredDistance(int[] x, int[] y) {
  // write your code here
}
    Input

    x

    [0, 1, 2]

    y

    [0, 1, 4]

    Output

    2

    Sign in to submit your solution.