300. Location Stream: Nearest Locations and Top Hotspots

Location Stream: Nearest Locations and Top Hotspots

Design a service that stores a stream of locations represented by latitude and longitude coordinates.

The service must return the 10 distinct stored locations nearest to a given coordinate and the 5 most frequently recorded locations.

Coordinate Normalization

Before storing or using a latitude or longitude value, round it to at most 6 digits after the decimal point using half-up rounding.

For any coordinate value value, calculate:

roundedValue = sign(value) * floor(abs(value) * 1,000,000 + 0.5) / 1,000,000

sign(value) is 1 when the value is positive.
sign(value) is -1 when the value is negative.
sign(value) is 0 when the value is zero.
Treat -0.0 and 0.0 as the same value.
Use normalized coordinates for storage, frequency counting, distance calculations, equality checks, and result ordering.
Two input coordinates that normalize to the same latitude and longitude represent the same location.

Location Format

Each returned location is represented as a string in the format "latitude,longitude".

Use ordinary decimal notation without scientific notation.
Include at most 6 digits after the decimal point.
Remove all trailing zeroes after the decimal point.
Remove the decimal point if no fractional digits remain.
Represent both -0.0 and 0.0 as "0".

Formatting examples:

28.613900 becomes "28.6139".
77.209000 becomes "77.209".
19.000000 becomes "19".
12.3456784 becomes "12.345678".
-12.3456788 becomes "-12.345679".
-0.0000004 becomes "0".

Distance Calculation

Treat latitude and longitude as coordinates on a two-dimensional plane. Compare locations using their squared Euclidean distance.

For a normalized stored coordinate (storedLatitude, storedLongitude) and a normalized query coordinate (queryLatitude, queryLongitude), calculate:

latitudeDifference = storedLatitude - queryLatitude
longitudeDifference = storedLongitude - queryLongitude

The squared Euclidean distance is:

squaredDistance = latitudeDifference * latitudeDifference + longitudeDifference * longitudeDifference

Use squaredDistance when comparing locations.
Do not calculate the square root.
Do not round the squared distance.
Comparing squared distances produces the same ordering as comparing Euclidean distances.
Earth curvature and longitude wraparound are not considered.
The calculated value is a coordinate-plane distance and does not represent an exact distance in kilometers.

Hotspot Rules

Every occurrence of a normalized coordinate increases its frequency by one.
Locations with greater frequencies appear before locations with lower frequencies.
If two locations have the same frequency, the location with the smaller normalized latitude appears first.
If their latitudes are also equal, the location with the smaller normalized longitude appears first.

Nearest Location Rules

Each distinct normalized coordinate appears at most once in the result.
Locations are returned from the smallest squared Euclidean distance to the greatest.
Locations with equal squared distances are ordered by smaller normalized latitude and then by smaller normalized longitude.
If fewer than 10 distinct locations are stored, return all distinct locations.
Return an empty list when no locations have been recorded.

Method Signatures

Constructor

LocationStream()

Creates an empty location stream.

Add Location

void addLocation(double latitude, double longitude)

latitude is the latitude of the location being recorded.
longitude is the longitude of the location being recorded.
Normalize both coordinates before storing the location.
Repeated normalized coordinates increase the hotspot frequency.

Get Nearest Locations

List<String> getNearestLocations(double latitude, double longitude)

latitude is the latitude of the query location.
longitude is the longitude of the query location.
Normalize both query coordinates before calculating distances.
Return at most 10 distinct stored locations.

Get Top Hotspots

List<String> getTopHotspots()

Return at most 5 distinct locations with the greatest frequencies.
Return an empty list when no locations have been recorded.

Constraints

-90.0 <= latitude <= 90.0
-180.0 <= longitude <= 180.0
1 <= number of method calls <= 100,000
Coordinate values may contain more than 6 digits after the decimal point.
All coordinate values are finite numbers.
All method parameters are valid coordinate values.

Examples

Each example uses a new LocationStream instance.

Example 1

LocationStream()
addLocation(latitude = 28.6139, longitude = 77.2090)
addLocation(latitude = 19.0760, longitude = 72.8777)
addLocation(latitude = 28.6139, longitude = 77.2090)
addLocation(latitude = 26.9124, longitude = 75.7873)
getTopHotspots()
Output: ["28.6139,77.209", "19.076,72.8777", "26.9124,75.7873"]

The coordinate "28.6139,77.209" was recorded twice, so it is the highest-ranked hotspot. The remaining locations have equal frequencies and are ordered by latitude.

Example 2

LocationStream()
addLocation(latitude = 12.9716, longitude = 77.5946)
addLocation(latitude = 13.0827, longitude = 80.2707)
addLocation(latitude = 17.3850, longitude = 78.4867)
getNearestLocations(latitude = 13.0000, longitude = 77.6000)
Output: ["12.9716,77.5946", "13.0827,80.2707", "17.385,78.4867"]

The stored coordinates are returned in increasing order of their squared Euclidean distances from the normalized query coordinate.

Example 3

LocationStream()
addLocation(latitude = 12.3456784, longitude = 45.6000004)
addLocation(latitude = 12.3456782, longitude = 45.6000001)
addLocation(latitude = -12.3456788, longitude = 30.0000002)
getTopHotspots()
Output: ["12.345678,45.6", "-12.345679,30"]

The first two inputs normalize to the same coordinate, so that location has a frequency of two. Trailing zeroes are removed from every returned value.

Example 4

LocationStream()
getTopHotspots()
Output: []

No hotspot exists because the stream is empty.