Zomato: Cuisine Gaps in Each Locality Worth Recruiting For
Zomato's city sales teams sign up restaurants where diners search for a cuisine that nobody nearby serves.
- Difficulty: Hard
- Topics: Joins, Subqueries, Aggregation, Dates
- Dialect: MySQL
- Problem: #1042
Problem statement
Zomato's city sales teams sign up restaurants where diners search for a cuisine that nobody nearby serves. They want every such gap, with the June search demand behind it.
A gap is a pair of a locality and a cuisine from Cuisine such that no active restaurant in that locality serves the cuisine, while at least one active restaurant elsewhere in the same city does (someone the team can approach). Consider every locality × cuisine combination, including ones nobody searched. Return city, locality_name, cuisine_name, june_searches (searches for that cuisine in that locality dated 2024-06-01 to 2024-06-30; 0 if none) and partners_in_city (active restaurants in the city serving the cuisine). Order by june_searches descending, then locality_name, then cuisine_name.
A practice scenario set at Zomato: the tables and data are invented, and this is not a question from, or endorsed by, Zomato.
Tables
Table: Locality
| Column | Type |
|---|---|
| locality_id | int |
| locality_name | varchar |
| city | varchar |
Primary key: locality_id.
One row per delivery locality; locality names are unique.
Table: Cuisine
| Column | Type |
|---|---|
| cuisine_id | int |
| cuisine_name | varchar |
Primary key: cuisine_id.
The cuisines the app lets diners filter by.
Table: Restaurant
| Column | Type |
|---|---|
| restaurant_id | int |
| locality_id | int |
| is_active | bool |
Primary key: restaurant_id.
One row per restaurant; is_active is 0 for one that is paused or delisted.
Table: RestaurantCuisine
| Column | Type |
|---|---|
| restaurant_id | int |
| cuisine_id | int |
Primary key: restaurant_id, cuisine_id.
The cuisines each restaurant serves; a restaurant may serve several.
Table: CuisineSearch
| Column | Type |
|---|---|
| search_id | int |
| locality_id | int |
| cuisine_id | int |
| searched_on | date |
Primary key: search_id.
One row per search filtered by a cuisine, logged against the diner's locality.
Examples
Example 1
Locality
| locality_id | locality_name | city |
|---|---|---|
| 1 | Koramangala | Bengaluru |
| 2 | Indiranagar | Bengaluru |
| 3 | Bandra West | Mumbai |
| 4 | Powai | Mumbai |
Cuisine
| cuisine_id | cuisine_name |
|---|---|
| 1 | Biryani |
| 2 | Chinese |
| 3 | South Indian |
Restaurant
| restaurant_id | locality_id | is_active |
|---|---|---|
| 10 | 1 | 1 |
| 11 | 1 | 1 |
| 12 | 2 | 1 |
| 13 | 2 | 0 |
| 14 | 3 | 1 |
| 15 | 4 | 1 |
RestaurantCuisine
| restaurant_id | cuisine_id |
|---|---|
| 10 | 1 |
| 10 | 2 |
| 11 | 3 |
| 12 | 1 |
| 13 | 3 |
| 14 | 2 |
| 15 | 2 |
| 15 | 1 |
CuisineSearch
| search_id | locality_id | cuisine_id | searched_on |
|---|---|---|---|
| 1 | 2 | 3 | 2024-06-03 |
| 2 | 2 | 3 | 2024-06-10 |
| 3 | 2 | 3 | 2024-05-31 |
| 4 | 2 | 2 | 2024-06-15 |
| 5 | 1 | 1 | 2024-06-20 |
| 6 | 3 | 1 | 2024-06-21 |
| 7 | 4 | 3 | 2024-06-30 |
Output
| city | locality_name | cuisine_name | june_searches | partners_in_city |
|---|---|---|---|---|
| Bengaluru | Indiranagar | South Indian | 2 | 1 |
| Mumbai | Bandra West | Biryani | 1 | 1 |
| Bengaluru | Indiranagar | Chinese | 1 | 1 |
How to solve Zomato: Cuisine Gaps in Each Locality Worth Recruiting For
A gap is something missing from the data, so it cannot be found by grouping the rows that exist. Generate every candidate instead: Locality CROSS JOIN Cuisine is the full grid of (locality, cuisine) pairs, whether or not anyone serves or searches them. Everything else is filtering and decorating that grid.
The local supply is the set of distinct (locality, cuisine) pairs covered by active restaurants — a paused restaurant does not feed anyone. NOT EXISTS against that set keeps the uncovered pairs. The city-level supply is a separate aggregate: active restaurants per city and cuisine, counted with COUNT(DISTINCT restaurant_id). An inner join to it removes gaps that no restaurant in the city could fill, and its count is the partners_in_city column; since the locality itself has none, all of them are elsewhere in the city.
Demand is pre-aggregated per pair for June and attached with a LEFT JOIN, so a pair nobody searched still appears with COALESCE(…, 0) searches. Aggregating before joining matters: joining raw searches to the grid and counting afterwards would work here, but joining raw searches and raw restaurants would multiply the two counts together.
The alternative builds the same grid with JOIN … ON 1 = 1 and computes the three counts with correlated subqueries, then filters on them. It is easy to read but runs three probes per pair; the CTE version reads each table once.
Reference solution (MySQL)
WITH served AS (
SELECT DISTINCT r.locality_id, rc.cuisine_id
FROM Restaurant r
JOIN RestaurantCuisine rc ON rc.restaurant_id = r.restaurant_id
WHERE r.is_active = 1
),
city_partners AS (
SELECT l.city, rc.cuisine_id, COUNT(DISTINCT r.restaurant_id) AS partners
FROM Restaurant r
JOIN Locality l ON l.locality_id = r.locality_id
JOIN RestaurantCuisine rc ON rc.restaurant_id = r.restaurant_id
WHERE r.is_active = 1
GROUP BY l.city, rc.cuisine_id
),
demand AS (
SELECT locality_id, cuisine_id, COUNT(*) AS searches
FROM CuisineSearch
WHERE searched_on BETWEEN '2024-06-01' AND '2024-06-30'
GROUP BY locality_id, cuisine_id
)
SELECT l.city, l.locality_name, c.cuisine_name,
COALESCE(d.searches, 0) AS june_searches,
cp.partners AS partners_in_city
FROM Locality l
CROSS JOIN Cuisine c
JOIN city_partners cp ON cp.city = l.city AND cp.cuisine_id = c.cuisine_id
LEFT JOIN demand d ON d.locality_id = l.locality_id AND d.cuisine_id = c.cuisine_id
WHERE NOT EXISTS (
SELECT 1 FROM served s WHERE s.locality_id = l.locality_id AND s.cuisine_id = c.cuisine_id
)
ORDER BY june_searches DESC, l.locality_name, c.cuisine_nameAnother way
SELECT city, locality_name, cuisine_name, june_searches, partners_in_city FROM (
SELECT l.city, l.locality_name, c.cuisine_name,
(SELECT COUNT(*) FROM CuisineSearch q
WHERE q.locality_id = l.locality_id AND q.cuisine_id = c.cuisine_id
AND q.searched_on >= '2024-06-01' AND q.searched_on <= '2024-06-30') AS june_searches,
(SELECT COUNT(*) FROM Restaurant r
JOIN Locality rl ON rl.locality_id = r.locality_id
JOIN RestaurantCuisine rc ON rc.restaurant_id = r.restaurant_id
WHERE r.is_active = 1 AND rl.city = l.city AND rc.cuisine_id = c.cuisine_id) AS partners_in_city,
(SELECT COUNT(*) FROM Restaurant r
JOIN RestaurantCuisine rc ON rc.restaurant_id = r.restaurant_id
WHERE r.is_active = 1 AND r.locality_id = l.locality_id AND rc.cuisine_id = c.cuisine_id) AS local_partners
FROM Locality l JOIN Cuisine c ON 1 = 1
) grid
WHERE local_partners = 0 AND partners_in_city > 0
ORDER BY june_searches DESC, locality_name, cuisine_name← Zomato: Live Menu Rebuilt From the Latest Approved Edits · Zomato: Most-Loved Dish of Each Restaurant and Its Complaints →