FastPrepStream Cluster Max and Median

Stream Cluster Max and Median

Snap Inc. logoSnap Inc.● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Process an integer data stream whose values are assigned to stored clusters. A cluster's representative is its first value and never changes.

  • ADD value: among representatives within maxDistance of value, choose the closest; break a distance tie by the smaller zero-based cluster identifier. If none qualifies, create a new cluster. Append the assigned cluster identifier.
  • MAX clusterId: append that cluster's maximum value, or INVALID for an unknown identifier.
  • MEDIAN clusterId: append the exact median, using an integer or an x.5 string, or INVALID for an unknown identifier.

Return one string for every operation in order.

Function

processClusterStream(maxDistance: int, operations: String[]) → String[]

Examples

Example 1

maxDistance = 3operations = ["ADD 10","ADD 12","ADD 20","ADD 17","MAX 0","MEDIAN 0","MAX 1","MEDIAN 1"]return = ["0","0","1","1","12","11","20","18.5"]

Ten and twelve form cluster 0. Twenty starts cluster 1, and seventeen joins it at distance three from its representative.

Example 2

maxDistance = 5operations = ["ADD 0","ADD 10","ADD 5","MEDIAN 0","MEDIAN 1","MAX 4"]return = ["0","1","0","2.5","10","INVALID"]

Value five ties both representatives and joins the smaller cluster identifier.

Constraints

  • 0 <= maxDistance <= 10^9.
  • 1 <= operations.length <= 5000.
  • Added values are signed 32-bit integers.
  • Every operation has one of the exact forms above.

More Snap Inc. problems

See Snap Inc. hiring insights
public String[] processClusterStream(int maxDistance, String[] operations) {
    // Write your code here.
}
maxDistance3
operations["ADD 10","ADD 12","ADD 20","ADD 17","MAX 0","MEDIAN 0","MAX 1","MEDIAN 1"]
expected["0", "0", "1", "1", "12", "11", "20", "18.5"]
Checking account…