How should I practice Locate Vehicles with Square Queries?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Applied Intuition phone screen problems in FastPrep.

Is Locate Vehicles with Square Queries associated with Applied Intuition?

FastPrep tags this as a Applied Intuition phone screen coding practice problem when the problem catalog has that company and stage context.

Locate Vehicles with Square Queries

Applied Intuition● MediumFULLTIMEPHONE SCREEN

Problem statement

Source note: The interviewer gave a ready-made function: "boolean ifVechicleInSquare(double lat_min, double lon_min, double side_size)". It returns whether this square has a vehicle. Then: "find the positions of all vehicles within the world map, and return each vehicle's latitude/longitude, accurate to 6 decimal places." The spelling of the function name is the report's.

The report gives no bounds, no rule for square edges and no search order. A judge cannot hand you a live function, so here the hidden positions come as two arrays, and you use them only to write that helper yourself. Positions are whole millionths of a degree, with at most 100 vehicles and no two in one spot. A square includes its low edges and leaves out its high edges. The search starts from one fixed square and splits it into four, and the result starts with the number of helper calls, so the search itself gets checked. Vehicles come back sorted by latitude, then longitude. Each position is one lat,lon string with exactly six digits after the point and a minus sign below zero.

The judged task matches the report at about 70%.

A map service hides the position of every vehicle behind one helper:

boolean ifVechicleInSquare(double lat_min, double lon_min, double side_size)

It returns whether at least one vehicle is inside the given square. Using only this helper, find every vehicle on the world map and report its latitude and longitude to six decimal places.

How this practice version works

All numbers are whole millionths of a degree, so a latitude of 37.7749 is 37774900. The helper here is ifVechicleInSquare(latMin, lonMin, side) with whole-number arguments.

A judge cannot pass you a live function, so the hidden positions arrive as vehicleLats and vehicleLons. Use these arrays only to write the helper. It returns true when some vehicle i has latMin <= vehicleLats[i] < latMin + side and lonMin <= vehicleLons[i] < lonMin + side. A square includes its low edges and leaves out its high edges.

Run this search:

Call the helper once on the whole world: latMin = -90000000, lonMin = -180000000, side = 536870912 (that is 2^29, the smallest power of two that covers every longitude).
When a call returns false, stop working on that square.
When a call returns true and side is 1, that square is exactly one position, so record a vehicle there.
When a call returns true and side is larger, split the square into four squares of half the side and call the helper on all four, even if the first three return false.

Return a string array. The first element is the total number of helper calls, written in decimal. After it comes one element for each vehicle, sorted by latitude and then by longitude, both as numbers. Each element has the form lat,lon, and each number has a minus sign when it is below zero and exactly six digits after the point, such as -0.000001,179.999999 or 0.000000,0.000000.

Function

locateVehicles(vehicleLats: int[], vehicleLons: int[]) → String[]

Examples

Example 1

vehicleLats = [0]vehicleLons = [0]return = ["117","0.000000,0.000000"]

The search makes one call on the whole world. The vehicle then keeps one square alive at each side from 2^29 down to 2, which is 29 splits of four calls each. The total is 1 + 29 * 4 = 117 calls.

Example 2

vehicleLats = []vehicleLons = []return = ["1"]

The first call returns false, so the search stops after 1 call and there is nothing to report.

Example 3

vehicleLats = [37774900,37774901,-33868800]vehicleLons = [-122419400,-122419400,151209300]return = ["229","-33.868800,151.209300","37.774900,-122.419400","37.774901,-122.419400"]

The search finds 57 different squares with a vehicle and a side larger than 1. Each one is split into four calls, so the total is 1 + 57 * 4 = 229 calls. The two vehicles close together share most of their squares.

Sorted by latitude, the vehicle at -33.868800 comes first. The other two have nearly equal latitudes, and 37.774900 comes before 37.774901.

Constraints

0 <= vehicleLats.length <= 100
vehicleLons.length == vehicleLats.length
-90000000 <= vehicleLats[i] <= 90000000
-180000000 <= vehicleLons[i] <= 180000000
No two vehicles have the same position.