Design a Live Robotaxi Map & Nearby Search
- Turn a stream of robotaxi positions into a live index that answers nearby search in milliseconds
- Handle late, duplicate and out-of-order updates without moving a vehicle backward
- Defend stale results and hot spots, then privacy and failover when pushed
Understanding the problem
Something like this: Zoox robotaxis report their location as they drive. Design a system that ingests those locations, shows authorized clients a near-real-time map of the fleet, and answers nearby search, meaning which vehicles are close to a point and eligible for a given job.
Versions of this prompt keep coming back. A software engineer technical screen in May 2026 asked for nearby search over continuously moving autonomous vehicles. A backend engineer screen in August 2026 asked for real-time vehicle location tracking with a live map. Back in 2024, a Senior SWE loop asked one candidate to design the Zoox app that shows cars on the road. Two of the three came up in technical screens, so practice reaching the core of the design quickly.
The shape is familiar from ride-hailing, and the twist is that nothing stands still. Size it for, say, fifty thousand vehicles, each moving about 15 meters every second. Any index you build is being rewritten under your feet while people search it. The data itself is small, since the latest position of every vehicle fits in about 15 megabytes. What makes it hard is the churn, readers who want everything fresh, and the moments when updates arrive late or not at all.
Functional requirements
Ask who the clients are before drawing anything. Three kinds make sense. Riders open the app and see vehicles near them, then watch their own vehicle arrive. Operations staff watch every vehicle in a city on a console. Internal services, mainly dispatch, ask for the nearest available vehicles to a pickup point. Each wants the same data at a different level of detail, which is why "authorized" is in the prompt.
In scope
- Ingest a position report from every vehicle, about once a second
- Show a live map to riders, operations staff and internal tools, each with its own permissions
- Nearby search: vehicles within a radius that pass filters such as available and charged enough
- Tell every reader how old each position is
- Keep position history so a vehicle's route can be replayed
Below the line (call it out, then skip)
- Drawing map tiles and the rendering itself
- The routing engine that computes drive times
- Matching riders to vehicles, which is dispatch's job
- How the vehicle works out its own position
Non-functional requirements
Freshness is the headline. A position should reach a viewer's screen within about 3 seconds at the 99th percentile, from the moment the vehicle measured it. A nearby search should answer in under 100 milliseconds, because dispatch calls it on the path of every ride request. Availability beats strict consistency for reads. A map that's two seconds behind is fine. A map that's down is a problem for every rider and every operator at once. One thing must be exactly right, though: a vehicle never jumps back to an older position because an old update arrived late. Ingest must not lose reports silently. The live map only needs the newest one, but the history feeds replay and analysis, so every report should land there at least once. Ask for numbers, and if the interviewer has none, propose some with room to grow.
- Position updates: 50,000 a second. 50,000 vehicles reporting once a second. At about 200 bytes each that is 10 MB a second, under a terabyte of history a day.
- Live state: about 15 MB. The newest report per vehicle, around 300 bytes with the index entries. It fits in memory on any machine, many times over.
- Open maps at peak: 100,000. Riders watching for their vehicle plus a few hundred operations consoles, each expecting an update every second.
- Freshness target: under 3 seconds. From the vehicle measuring a position to a viewer seeing it, at the 99th percentile.
The set-up
Core entities
Position report
What a vehicle sends about once a second: which vehicle, where it is, its heading and speed, its service status, and when it measured all that. It also carries a sequence number that only goes up, which is how we tell a newer report from an older one.
Live vehicle state
The newest accepted report for each vehicle, plus the map cell it currently sits in. There is exactly one per vehicle, and it gets overwritten constantly. This is what search and the map read.
Map cell
A small hexagon on the map that holds the ids of the vehicles inside it. Cells turn "near this point" into "in these few cells," which is a lookup instead of a scan.
Map subscription
One viewer watching a set of cells, along with what that viewer is allowed to see. It lives only as long as the connection.
The split that matters is live state versus history. Live state is tiny, hot and disposable: keep it in memory and rebuild it from the log if a machine dies. History is large, append-only and kept for weeks, so it goes in a store built for time series, keyed by vehicle and hour. The two never share a database, because they want opposite things.
| Table | Fields |
|---|---|
| live vehicle state (in memory) | vehicle_id · sequence · measured_at · position · heading · speed · status · cell |
| cell membership (in memory) | cell · status · vehicle ids |
| position history (Cassandra) | vehicle_id + hour (partition key) · measured_at · sequence · position · status |
API
Four calls cover it. Vehicles push reports over a long-lived stream, because setting up a new connection every second over cellular wastes time and battery. Viewers get a WebSocket for the live map, since the server has to push updates without being asked.
High-level design
The design is one write path and two read paths sharing one in-memory index. Reports flow from the vehicle into a log, and everything else reads that log. In the diagram, blue is a client outside this system, violet is a service we run, amber is the log that moves data, and green is durable storage.
1) A vehicle reports. The Robotaxi sends a report over its open stream to an Ingest gateway, which checks it and appends it to the Position log, keyed by vehicle id. Keying by vehicle keeps each vehicle's reports in order within one partition, and the log keeps them safe if any reader falls behind. The gateway acks the sequence number so the vehicle can drop it from its buffer. That is 50,000 small writes a second, easy for a modest Kafka cluster, and nothing on this path touches geography. What happens when reports arrive late or twice has its own deep dive.
2) The index absorbs it. The Live geo index reads the log, compares each report's sequence number with the one it holds, and drops anything older. If the report is newer, it updates the vehicle in place and moves it between cells only when the vehicle has crossed a cell edge. With cells about 300 meters across and vehicles moving about 15 meters a second, a crossing happens roughly every 20 seconds per vehicle, so about 95 percent of updates never touch the cell sets. Meanwhile the History writer stores every report in Position history.
3) Someone searches nearby. The Dispatch service asks the Nearby API for available vehicles within a kilometer of a pickup. The API works out which cells cover that circle, about 60 of them, and asks an index replica for the available vehicles in those cells. It computes real distances for the few hundred candidates, filters, sorts and returns the closest ones, each with its age. That finishes in well under 10 milliseconds. Why cells beat a database here is the first deep dive.
4) Maps stay live. A Rider app or Ops console opens a WebSocket to the Map gateway with its viewport. The gateway checks the viewer's token with the Auth service, sends a snapshot of the vehicles in view, then subscribes to those cells. Once a second the index emits each cell's changes, and the gateway forwards them, filtered for that viewer. If every viewer polled instead, 100,000 open maps would mean 100,000 searches a second. How subscriptions keep that load flat, even outside a stadium, is the fan-out dive.
Technology choices
- The Ingest gateway speaks gRPC streaming or MQTT over mutual TLS. A long-lived connection costs one handshake per drive instead of one a second, and mutual TLS means each vehicle proves its identity with its own certificate. If a gateway dies, vehicles reconnect to another one with jittered backoff and resend whatever they had not seen acked.
- The Position log is Kafka, which stores messages in ordered, replicated partitions that many readers can consume independently. Keep three copies of each partition, and count a write as done only once every caught-up copy has it. If a broker fails, another replica takes over its partitions and producers retry. A retry can duplicate a report, which the sequence check absorbs. Next to the main topic, keep a compacted topic, which retains only the latest message per vehicle, for fast rebuilds.
- The Live geo index is a small service of our own on H3 cells. H3 is the hexagonal grid Uber open-sourced. It gives every patch of the earth a cell id at many sizes, and finding a cell's neighbors is cheap. Redis with its GEO commands is the lighter option, and the first deep dive weighs the two. The index holds soft state only, so a dead replica gets replaced and rebuilt in seconds.
- Position history goes in Cassandra, built for heavy append-only writes spread across many machines. Partitioning by vehicle and hour keeps partitions bounded and makes a route replay one read per hour. A node failure is absorbed by replication, typically three copies. Older data rolls off to Parquet files in S3 for analysis.
- The Map gateway uses WebSockets, a two-way connection that stays open, because the server pushes every second and viewers change their viewport often. Gateways hold no state that matters: a viewer whose gateway dies reconnects, gets a fresh snapshot and carries on.
- The Auth service issues short-lived JWTs, signed tokens that list the caller's role and scopes. Gateways verify the signature locally, so a slow auth service doesn't slow down every map update.
Brand names matter less than the categories. If the interviewer's team runs something else, explain why positions belong in a replayable log and why live state can sit in memory. That reasoning travels.
Potential deep dives
How does nearby search work when every vehicle keeps moving?
The numbers decide this one. The index takes 50,000 writes a second, and each write changes the very thing searches look up. Dispatch might send 5,000 searches a second, each wanting an answer inside a 100-millisecond budget. Any structure that pays a real cost per write, or scans a whole city per search, falls over.
Approach
Keep one row per vehicle in Postgres. Update its latitude and longitude on every report, and answer nearby search with a bounding-box query, or a radius query through PostGIS, the geographic extension.
Challenges
A plain index on latitude narrows only one dimension, so a box query reads a strip across the whole city and then filters on longitude. PostGIS indexes both dimensions, but every update still rewrites the row and its index entry, and Postgres leaves the old row version behind for cleanup. At 50,000 updates a second the database spends its life on writes. And it makes each one durable, a guarantee nobody needs for a position that gets replaced a second later.
Approach
On every report, add the vehicle to its region's geo set with its new position. Redis stores each member in a sorted set scored by a geohash, a number that keeps nearby points close together. A radius search becomes a few range scans, and one Redis instance handles around 100,000 operations a second, so a region fits comfortably.
Challenges
The geo set knows positions and nothing else. Status and battery live in a separate key, so search fetches candidates and filters afterward. In a busy area where nine vehicles in ten are on trips, asking for 50 nearby yields 5 usable ones, and you query again wider. Out-of-order reports need a small script that compares the stored sequence number before writing. And one single-threaded primary per region takes every write and most reads, which is the first thing to buckle in a hot spot.
Redis is a fine answer for a screen, and it's honest to start there. What pushes past it is the combination of filters, ordering and read load. Search wants only eligible vehicles, every write needs the sequence check, and reads need to scale apart from writes. A purpose-built index does all three for very little code, because the whole state is 15 MB.
Approach
Each index node holds two maps. One maps a vehicle id to its latest state, including its cell. The other maps a cell to the vehicles inside it, split by status, so search never touches vehicles on a trip. A report updates the vehicle in place and moves it between cells only on a crossing. A search takes the point's cell and adds rings of neighbors until the radius is covered, so with 300-meter hexagons four rings, about 60 cells, cover a kilometer. Real distances are computed only for the vehicles in those cells. For read scaling, add replicas that consume the same log partitions and apply the same rule, so they converge on the same state.
Challenges
You now own a service: deploys, shard maps, rebuilds and monitoring. A search near a region's edge has to ask two shards, which is rare when regions are whole cities. Cell size is a tradeoff. Smaller cells mean less filtering and more crossings, and bigger cells mean the reverse.
Distance needs a sentence too. On a sphere, straight-line distance comes from the haversine formula. Raw degrees won't do, because a degree of longitude shrinks with latitude: at 36 degrees north it's about 90 km, against 111 km for a degree of latitude. And straight-line distance is only a proxy. A vehicle 200 meters away across a divided road can be several minutes out. So nearby search returns the closest 20 or so by straight line, and dispatch re-ranks them by drive time with the routing service. That keeps the expensive routing calls to a handful per request.
What happens when updates arrive late, twice or out of order?
Naive designs break here. Reports go wrong in three ordinary ways. First, a vehicle spends 30 seconds in a dead zone, then reconnects and sends 30 buffered reports in a burst. Second, a gateway retries a write to the log after a timeout, and the report lands twice. Third, a vehicle drops its connection and reconnects to a different gateway while the old one is still flushing, so two gateways write its reports at once and they interleave. If the index simply applies whatever arrives last, the vehicle jumps back 400 meters on every operator's screen. Worse, dispatch might send it to a rider based on where it was half a minute ago.
The vehicle numbers every report
A sequence number that only goes up, with a boot counter in front so a reboot doesn't reset it to zero. Sequence numbers beat timestamps for ordering because they don't depend on any clock being right. The measured time still travels with the report, for working out age.
The live index keeps only the newest
A report whose sequence is at or below the stored one is dropped. That single comparison handles late, duplicate and interleaved reports alike, and every replica that applies it ends up in the same state.
History keeps everything
The history writer stores late reports too, keyed by vehicle and measured time. A duplicate overwrites the same row with the same values. Late reports fill gaps in the replayed route, which is exactly what someone reviewing an incident needs.
Newest first after a reconnect
The vehicle sends its current position before backfilling its buffer. The map recovers in one second instead of thirty, and the backfill is late by design, so the live path ignores it.
The rule the index applies to each report fits in a few lines.
if report.sequence <= stored.sequence: drop it (history still keeps it)new_cell = cell_of(report.position)if new_cell != stored.cell: move the vehicle between cell setsstored = report, with new_cellDelivery guarantees are the natural next question. Kafka gives at-least-once delivery here, and that's enough. The live path is idempotent because applying an older or repeated report changes nothing, and the history path is idempotent because rewriting a row is harmless. Nobody needs exactly-once machinery when both readers shrug off repeats.
How do we keep results honest when positions go stale?
A position is a claim about the past. Even a healthy pipeline shows a vehicle where it was a second or two ago, and a vehicle that stops reporting keeps its last position in the index forever unless something says otherwise. So every position carries its age. Every response also carries as_of, the time of the newest report the index has applied. If the index falls five seconds behind the log, every caller can see that the whole answer is old, beyond any single vehicle being slow.
Age then drives behavior, and each client wants something different.
| Age of the newest report | Rider app | Ops console | Nearby search |
|---|---|---|---|
| Under 3 seconds | Shown, animated | Shown | Eligible |
| 3 to 30 seconds | Hidden | Greyed out, with a last-seen time | Left out unless the caller allows an older max age |
| Over 30 seconds | Hidden | Red marker at the last position, plus an alert | Left out |
The ops row is the easy one to get wrong. Dropping a silent vehicle from a rider's map is right. Dropping it from the operations map hides the one vehicle that most needs attention. A separate sweeper in the index checks for vehicles past the threshold every second and emits a "lost contact" change, because a vehicle that has gone silent sends no update to trigger anything. On the client, the map can glide each marker along its last heading and speed between updates, so motion looks smooth at one update a second. Cap that guessing at a second or two and then freeze the marker. A marker that keeps sliding along a road the vehicle may never have taken is a lie.
How does one live map reach thousands of viewers, even in a hot spot?
Picture a concert letting out. Twenty thousand people open the app within a few minutes, all looking at the same few blocks, while dozens of vehicles queue in one pickup zone. The writes there are fine, since a few hundred vehicles in one cell is nothing for an in-memory map. The reads are the danger, because every one of those viewers wants the same cells every second.
Approach
The app calls the nearby endpoint for its viewport once a second and redraws.
Challenges
100,000 open maps become 100,000 searches a second, twenty times dispatch's load. The concert alone sends 20,000 searches a second at one shard for the same answer. Each poll also pays for a new HTTP request, an auth check and a full result even when nothing moved.
Approach
Map viewers subscribe to coarse cells, about 2.5 km across, so a phone screen covers a few of them. Once a second, the index emits one delta per active coarse cell: which vehicles moved, appeared or left. Each map gateway subscribes to a cell once, however many of its viewers watch it, and copies the delta to each socket after filtering for that viewer. The index's work now depends on the number of active cells, a few hundred per city at most. Twenty thousand concert viewers spread over 50 gateway nodes is 400 sockets each, and the index still produces one message per cell per second.
Challenges
Viewers panning the map change subscriptions constantly, so the gateway needs a fast snapshot path for newly visible cells. A gateway node that hosts many viewers of one hot cell becomes a hot node itself, so the load balancer spreads connections by count. A slow phone on a weak signal must not back up the stream for others, so each socket gets a small buffer and drops old deltas for a fresh snapshot when it overflows.
Hot spots can also be a write problem when a region outgrows one index shard. Split the region by its parent cells, so each node owns a set of neighborhoods, and a search near a split asks both owners. Coarse H3 cells nest cleanly, which makes that split a lookup table instead of a reshuffle. The real-time updates lesson covers WebSockets, server-sent events and polling in general.
Who is allowed to see which vehicle?
A vehicle carrying a passenger is a live feed of that passenger's location, and that one fact decides most of the rules. Riders see available vehicles only, never occupied ones. Their own vehicle shows in detail only while their trip is active.
| Client | Sees | Never sees |
|---|---|---|
| Rider app | Available vehicles nearby, positions rounded to about 50 meters, under ids that change each session; their own vehicle exactly during their trip | Occupied vehicles, real vehicle ids, other riders' trips |
| Ops console | Every vehicle in the regions the operator is assigned, with full status and age | Regions outside their assignment |
| Dispatch service | Search results with vehicle ids, status and age | The live map stream, which it has no use for |
Enforce it at the edges. The nearby API and the map gateway read the caller's token, which lists the role and scopes, and check every subscription against it. Then each message is cut down to the fields that role may see. Tokens expire after about 15 minutes, and a WebSocket that outlives its token must refresh or be closed. Otherwise an operator removed from a region keeps watching it for hours. The changing ids for riders are deliberate. They let the app animate a marker smoothly within a session without letting anyone track one vehicle across days. Rate limits on the rider endpoints stop someone from sweeping the city to map the fleet. Access to position history is logged, since a replayed route can reveal where a rider lives.
What happens when an index node or a whole zone fails?
The live index is soft state, which makes failover simpler than it sounds. Run at least two replicas per region in different availability zones, each consuming the same log partitions on its own. If one dies, the nearby API sends searches to the other and the gateways resubscribe. Neither replica needs to tell the other anything. A replacement rebuilds in two moves. First it loads the compacted topic, one latest report per vehicle, 50,000 records that load in a couple of seconds. Then it reads the main log from a little before the newest report it loaded and catches up. The overlap is harmless, since the sequence check drops what it already has. It starts serving once its lag is under a second.
The other failures each have a known answer. A dead ingest gateway sends its vehicles to reconnect elsewhere, and their reconnects need jittered backoff. Otherwise thousands of cars retry in the same second and knock over the next gateway. A Kafka broker failure is the retry-and-duplicate case from earlier, and the sequence check already covers it. Losing a whole cloud region is a Staff-level follow-up. Mirror the log to a second region, let vehicles connect to either, and accept a few seconds of stale map during the switch. When something has to give, degrade in order. Ingest and the log keep accepting reports, since they are the record of where vehicles were. The map can fall behind and the as_of value will say so. Alert on index lag past two seconds and on any region where the share of fresh vehicles drops suddenly, which usually means a cellular problem.
Practice the core in code
The heart of this design is small enough to code in one sitting. One class takes position reports and drops any that are late or repeated. It keeps vehicles grouped by grid cell, and answers a radius search filtered by status and age. The problem uses a flat grid in meters instead of the earth's surface and square cells instead of hexagons. The ideas it tests are the ones from the deep dives: the sequence check, moving a vehicle between cells only on a crossing, and searching only the cells that can matter. One simplification to name out loud: the problem orders reports by timestamp, where the design orders them by the vehicle's sequence number and keeps the measured time for age.
Live fleet index: drop stale reports, find nearby vehicles
Problem
FleetIndex(cell_size) that keeps vehicles grouped by cell, where a point's cell is (floor(x / cell_size), floor(y / cell_size)).update(vehicle_id, timestamp, x, y, status) records a report. If the vehicle is new, or timestamp is greater than its stored timestamp, replace its state and return true. Otherwise ignore the report and return false.nearby(x, y, radius, now, max_age) returns the ids of "available" vehicles within radius of (x, y) whose stored timestamp is at least now - max_age, closest first, ties by id. Search only the cells the radius can reach, and compare squared distances.Each test is a JSON array of operations:
["FleetIndex", [cell_size]] first, then [method, [args]]. The expected array holds each return, with null for the constructor.- FleetIndex(100)
- update("a", 1, 0, 0, "available")→ true
- update("b", 1, 50, 50, "available")→ true
- update("c", 1, 300, 0, "available")→ true
- nearby(0, 0, 100, 1, 10)→ ["a","b"]
Vehicle b is about 71 meters away, inside the radius. Vehicle c is 300 meters away and two cells over, so its cell is never searched.
Keep two maps: vehicle id to its latest report and cell, and cell to the set of vehicle ids inside it. A search scans the block of cells from (x - radius) to (x + radius) on each axis.
Live fleet index: drop stale reports, find nearby vehicles
Click "Run" to execute your code
Follow-ups to be ready for
- "Show me where this vehicle went in the last hour." One read from position history for that vehicle and hour, with late reports already filled in.
- "Alert when a vehicle leaves its service area." A separate consumer on the position log checks each report against the area's boundary cells.
- "Filter by more than status." Add battery level or seat count to the live state and filter after the cell lookup. Split cell sets only by the most selective field.
- "The fleet grows ten times." Ingest and the log scale out by partition. The index splits each region by parent cell, and the state is still only 150 MB.
What is expected at each level
The 2026 versions of this prompt came up in technical screens for software and backend engineers. The 2024 one came up in a Senior loop. An August 2026 Senior/Staff loop had two design rounds, so this one may sit next to a second design prompt.
Mid level (L3 and L4)
Roughly 80/20 breadth to depth. You should reach a working end-to-end design: vehicles report into a log, an in-memory index groups them by cell, nearby search reads the cells around a point, and maps get pushed updates. Do the 50,000-writes-a-second math and land on memory over a database yourself. With a hint, you should add the sequence check for late reports. The bar: a design where a late report can't move a vehicle backward.
Senior (L5)
Roughly 60/40. Bring up late and duplicate reports before the interviewer does, and explain why at-least-once delivery is enough. Put age and as_of on every result, and handle a silent vehicle differently for riders and operators. Defend Redis or a custom index with numbers, and know when straight-line distance stops being good enough. The bar: you find stale data, hot spots and ordering problems yourself, and answer each with a mechanism.
Staff (L6) and above
Roughly 40/60. Treat privacy as a design input from the start, since an occupied vehicle's position is a rider's location. Cover fan-out by cell, shard splits by parent cell, rebuilds from the compacted topic, and region loss with a stated cost. Say what degrades first when things break, and what you'd alert on. The bar: you lead the conversation through failure, privacy and scale. The interviewer just picks which one to dig into.
Key Takeaways
- ✓Positions flow through a log into an in-memory cell index. The live state is megabytes, so the hard parts are churn, freshness and failure.
- ✓Number every report on the vehicle and keep only the newest, so late and duplicate reports never move a vehicle backward.
- ✓Put an age on every position and as_of on every answer. A silent vehicle disappears for riders and turns red for operators.
- ✓Push per-cell changes once a second to subscribed gateways, so viewer count never multiplies load on the index.
Zoox interview guideKnow what Zoox asks before you walk in.
21 coding · 4 system design · 30 behavioral questions
Get their questions first.
InterviewLegend is independent and not affiliated with or endorsed by any company it covers.