Loading page…
Practice problem · medium
A maps app stores map tiles on the server and on each phone. A tile is identified by two numbers: its zoom level and its tile number at that zoom level.
Before a trip, the app compares the server's list with the phone's list and downloads what the phone lacks. A teammate built the lookup key by writing the two numbers one after the other. A phone then skipped a tile it did not have.
You find the missing tiles correctly.
Write missing_tiles(zoom_a, tile_a, zoom_b, tile_b).
zoom_a[i] and tile_a[i] are the i-th tile of the server's list. zoom_b[j] and tile_b[j] are the j-th tile of the phone's list.i, in increasing order, of the server's tiles that are not in the phone's list. A tile that is repeated in the server's list is reported at every position where it is missing.Input: zoom_a = [1, 12, 3, 1], tile_a = [23, 3, 4, 23], zoom_b = [12, 3], tile_b = [3, 5]
Output: [0, 2, 3]The trace checks each server tile against the phone's tiles (12, 3) and (3, 5).
| Step | Position | Server tile | On the phone? |
|---|---|---|---|
| 1 | 0 | (1, 23) | no: missing |
| 2 | 1 | (12, 3) | yes |
| 3 | 2 | (3, 4) | no: missing |
| 4 | 3 | (1, 23) | no: missing |
Input: zoom_a = [0, 5], tile_a = [0, 5], zoom_b = [], tile_b = []
Output: [0, 1]An empty phone is missing every tile.
Input: zoom_a = [], tile_a = [], zoom_b = [7], tile_b = [7]
Output: []The server has no tiles, so nothing is missing.
0 ≤ zoom_a.length = tile_a.length ≤ 20,000, and the same for the phone's list0 ≤ zoom ≤ 99 and 0 ≤ tile number ≤ 1,000,000Searching the phone's list for every server tile costs up to one comparison for each phone tile. With 20,000 tiles on each side that is about 4 × 10^8 comparisons. A set finds a tile in one step on average.
The numbers are small, so a pair can be packed into one 64-bit number. They are also short, so two pairs are easy to confuse when their digits are glued.
missing_tiles · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.