The Heat of the Map

A hard Data Modeling interview practice problem on DataDriven. Design the schema on the canvas: tables, keys and relationships, then get feedback on it.

Domain
Data Modeling
Difficulty
hard
Seniority
senior
Asked in
Grab

Problem

Grab's dispatch team runs a live map showing, for every geohash cell in a city, a surge multiplier driven by how far open requests outrun available drivers and a congestion score comparing observed speed to the road's free-flow speed, refreshed each minute. The schema backs both the always-on map, which needs only the current value in each cell, and analysts who replay how surge built up across a city over the past week. The cells nest, so a coarse cell's surge has to reconcile against the finer cells inside it and up to the one city each cell sits in, and you cannot get there by averaging one cell's ratio with another's.

Worked solution and explanation

What this really is

Under the surge-map costume, this problem combines two things: a non-additive measure and a split between current state and history. Surge and congestion are ratios, and ratios do not roll up. Most candidates draw a cell table and a time column. What separates them is whether they keep the numerator and the denominator behind each factor. Store only surge_factor and the first district view averages forty child multipliers. It reports a surge that no driver count supports, and nobody can reproduce it.

Build it in order

Step 1: Declare the grain first

One row in fact_cell_metrics is one geohash cell in one minute, so the composite key is (geohash, minute_bucket). That makes it a periodic snapshot rather than an event log. Replay then scans a clean time series instead of rebuilding state from raw demand events.

Step 2: Model the nesting in dim_geohash

Geohash prefixes nest by construction. A self-referencing parent_geohash plus precision gives you the rollup path without a bridge table. A city_id foreign key resolves any cell to its one city straight from the dimension.

Step 3: Give the map its own table

current_cell_state holds one row per cell, keyed by geohash alone and overwritten each minute. The map reads it by key and never touches history. It carries the same ingredients as the fact, so zooming out on the live map reconciles the same way replay does.

Step 4: Use a surrogate key for city

city_id is an INT surrogate on dim_city. Cities get renamed and change timezone; the key does not. Both fact tables repeat city_id on purpose. A week of city replay then prunes to one city without first joining a billion rows through dim_geohash.

The reference model

fact_cell_metrics is the per-minute history. current_cell_state is its latest-minute projection. Both hang off the same dim_geohash and dim_city, so a cell means the same thing on the map and in replay.

Grain shown by the keys: `fact_cell_metrics` is cell by minute and `current_cell_state` is one row per cell. `parent_geohash` carries the nesting.
  • dim_city: city_id INT PK, name TEXT, country TEXT, timezone TEXT
  • dim_geohash: geohash TEXT PK, city_id INT FK, parent_geohash TEXT FK, precision INT, center_lat DECIMAL, center_lng DECIMAL
  • fact_cell_metrics: geohash TEXT PK, minute_bucket TIMESTAMP PK, city_id INT FK, open_requests INT, available_drivers INT, observed_speed_kmh DECIMAL, free_flow_speed_kmh DECIMAL, surge_factor DECIMAL, congestion_factor DECIMAL
  • current_cell_state: geohash TEXT PK, city_id INT FK, minute_bucket TIMESTAMP, open_requests INT, available_drivers INT, observed_speed_kmh DECIMAL, free_flow_speed_kmh DECIMAL, surge_factor DECIMAL, congestion_factor DECIMAL
  • dim_geohash.city_id references dim_city.city_id
  • dim_geohash.parent_geohash references dim_geohash.geohash
  • fact_cell_metrics.geohash references dim_geohash.geohash
  • fact_cell_metrics.city_id references dim_city.city_id
  • current_cell_state.geohash references dim_geohash.geohash
  • current_cell_state.city_id references dim_city.city_id
Ingredients plus factors
Rows are slightly wider. Any coarse cell or city recomputes exactly from its children, and a disputed multiplier can be audited against its inputs.
Factors only
Rows are narrow and fine at one zoom level. Every rollup to a parent cell or a city averages ratios and is wrong, with nothing to reconcile against.

Common follow-up questions