How should I practice K Closest Stars from a Data Stream?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is K Closest Stars from a Data Stream associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

K Closest Stars from a Data Stream

Google● MediumINTERNONSITE INTERVIEW

Learn

Problem statement

You receive a finite stream of stars in arrival order. Each row stars[i] = [starId, distance] contains a unique integer identifier and that star's nonnegative distance.

Return up to k rows with the smallest distances. Order the returned rows by increasing distance; when distances are equal, order them by increasing starId.

If k == 0, return an empty matrix. If k is greater than the number of stars, return every row in the required order.

Process the input in one pass while retaining only O(min(k, stars.length)) candidate rows before producing the ordered result.

Function

kClosestStars(stars: int[][], k: int) → int[][]

Examples

Example 1

stars = [[101,50],[102,20],[103,20],[104,80]]k = 2return = [[102,20],[103,20]]

Stars 102 and 103 have the two smallest distances. Their equal distances are ordered by increasing starId.

Example 2

stars = [[7,9],[3,1]]k = 5return = [[3,1],[7,9]]

Because k exceeds the stream length, both stars are returned in increasing distance order.

Constraints

0 <= stars.length <= 200000.
Every row of stars has exactly two integers: [starId, distance].
All starId values are distinct signed 32-bit integers.
0 <= distance <= 10^9.
0 <= k <= 250000.