Design a map or ride-hailing client: tile maths, caching while panning, location updates, battery and what you send to the server.

26.5.3 · L5 · Interview

Predict first

What tile contains London at zoom 10, and how does a small LRU behave while panning?

import Foundation
func tile(lat: Double, lon: Double, z: Int) -> (x: Int, y: Int) {
    let n = Double(1 << z)
    let x = Int((lon + 180) / 360 * n)
    let r = lat * .pi / 180
    let y = Int((1 - log(tan(r) + 1 / cos(r)) / .pi) / 2 * n)
    return (x, y)
}
let london = tile(lat: 51.5074, lon: -0.1278, z: 10)
print("London z10:", london.x, london.y)
print("tiles in the world at z0, z10, z15:", 1, 1 << 20, 1 << 30)
// a 390x844 pt viewport at 256 pt tiles covers ceil(w/256)+1 by ceil(h/256)+1 tiles worst case
func count(_ w: Double, _ h: Double) -> Int { (Int((w / 256).rounded(.up)) + 1) * (Int((h / 256).rounded(.up)) + 1) }
print("worst-case tiles for one phone screen:", count(390, 844))
// pan east in 100 pt steps along a row of tiles with an LRU of 12 tiles
var lru: [Int] = []; var fetched = 0, hits = 0
func need(_ ids: [Int]) {
    for id in ids {
        if let i = lru.firstIndex(of: id) { lru.remove(at: i); lru.append(id); hits += 1 }
        else { fetched += 1; lru.append(id); if lru.count > 12 { lru.removeFirst() } }
    }
}
var x = 0.0
for _ in 0..<20 {
    let first = Int(x / 256), last = Int((x + 390) / 256)
    need(Array(first...last).flatMap { c in (0..<4).map { r in r * 1000 + c } })
    x += 100
}
print("panned 2000 pt: fetched", fetched, "tiles, cache hits", hits)

London z10: 511 340; 15 tiles at most per screen; 36 fetches and 160 cache hits while panning
London z10: 0 0; the cache never hits
Every pan step fetches every visible tile again

Mental model. A map is a wall of postcards. You do not print the whole wall; you keep the cards around your feet and fetch the next row as you walk.

A slippy map is a pyramid of square tiles. At zoom z the world is a 2^z × 2^z grid (1 tile at zoom 0, 1,048,576 at zoom 10, over a billion at zoom 15), and a coordinate maps to a tile with the Web Mercator formula: x = (lon + 180) / 360 × 2^z and y = (1 − asinh(tan lat) / π) / 2 × 2^z. The check puts London (51.5074, −0.1278) at tile (511, 340) at zoom 10. A phone screen of 390 × 844 points needs at most 15 tiles of 256 points, because a viewport straddles tile edges. With MKMapView you do not manage tiles yourself (MapKit caches its own), but custom MKTileOverlay layers, offline maps, heat maps and your own renderer all need this arithmetic: compute the visible tile range, request only the missing ones, cancel requests for tiles that scrolled away, and prioritise the ones nearest the centre.

Caching decides how smooth panning feels. In the model, panning 2,000 points along a row with a 12-tile LRU fetched 36 tiles and hit the cache 160 times, because neighbouring viewports share most tiles; a cache smaller than one viewport would thrash (Q338). Add a disk cache with expiry for tiles and an in-memory cache of decoded images (Q327). The location side is where batteries die (Q376): use the coarsest accuracy that works, a distanceFilter, significant-change or visit monitoring when the app is not on screen, and stop updates when the screen is not needed; for a driver app that must report often, batch points and upload them together (or stream over a socket while foregrounded) and downsample on the server. Send position as (lat, lon, accuracy, timestamp, speed), never trust device time alone, smooth the displayed marker (interpolate between fixes rather than teleporting), snap to roads on the server, and handle denied or reduced-accuracy permission with a usable fallback. Privacy matters: a trail is sensitive data, so minimise retention and tell the user when you track.

Neighbouring viewports share most tiles, so a cache that holds a viewport or two turns panning into a trickle of fetches.

Common traps

Fetching a rectangle of tiles by pixel size and not tile edges. You miss the partial tiles at the borders and see blank squares.
Keeping location updates on at best accuracy “just in case”. That is the fastest way to drain the battery and get a review that says so.

They might follow up with

How would you show 50,000 pins? Cluster by tile or zoom level on a background queue and show clusters, not annotations (Q377).
Offline maps? Pre-download a tile range by region and zoom with a size estimate shown to the user, and treat it as pinned, not cached.

Design a map or ride-hailing client: tile maths, caching while panning, location updates, battery and what you send to the server.

Predict first

Common traps

They might follow up with

Related questions