Google: Places per Top-Level Maps Category — SQL Problem
Maps stores each place's category as a path such as Food > Restaurant > South Indian, levels joined by > (space, greater-than, space).
- Difficulty: Medium
- Topics: Strings, Aggregation
- Dialect: MySQL
- Problem: #684
Problem statement
Maps stores each place's category as a path such as Food > Restaurant > South Indian, levels joined by > (space, greater-than, space). A taxonomy analyst wants a summary by the first level.
Ignoring places whose category_path is NULL, return top_category (the text before the first > , or the whole path if it has one level), places (how many places fall under it) and deepest_level (the largest number of levels among those places' paths). Order by places descending, then top_category ascending.
A practice scenario set at Google: the tables and data are invented, and this is not a question from, or endorsed by, Google.
Tables
Table: MapsPlace
| Column | Type |
|---|---|
| place_id | int |
| place_name | varchar |
| category_path | varchar |
Primary key: place_id.
Category names never contain >; a path has no leading or trailing spaces. NULL means the place is not categorised yet.
Examples
Example 1
MapsPlace
| place_id | place_name | category_path |
|---|---|---|
| 1 | Vidyarthi Bhavan | Food > Restaurant > South Indian |
| 2 | Toit | Food > Bar > Brewpub |
| 3 | Indian Coffee House | Food > Cafe |
| 4 | Lalbagh | Outdoors > Garden |
| 5 | Cubbon Park | Outdoors > Park |
| 6 | Phoenix Mall | Shopping |
| 7 | Unnamed pin | NULL |
| 8 | Chinnaswamy Stadium | Sports > Stadium > Cricket > Pavilion |
Output
| top_category | places | deepest_level |
|---|---|---|
| Food | 3 | 3 |
| Outdoors | 2 | 2 |
| Shopping | 1 | 1 |
| Sports | 1 | 4 |
How to solve Google: Places per Top-Level Maps Category
Two string facts are needed per place. The top level is the text before the first separator: SUBSTRING_INDEX(category_path, ' > ', 1) returns exactly that, and returns the whole path when it has no separator, so one-level paths like Shopping need no special case.
The depth is one more than the number of separators. A classic way to count occurrences of a substring is to remove them with REPLACE and see how many characters disappeared: each > is three characters, so the difference in length DIV 3 is the separator count. (The alternative counts the single > character instead, which is the same number because category names never contain one.)
With those two expressions the rest is a grouped aggregate: group by the top level, count places, take the MAX depth. NULL paths are filtered out first so they do not form a NULL group. The order is fixed by the count and then the category name. One pass over the table.
Reference solution (MySQL)
SELECT SUBSTRING_INDEX(category_path, ' > ', 1) AS top_category,
COUNT(*) AS places,
MAX((CHAR_LENGTH(category_path) - CHAR_LENGTH(REPLACE(category_path, ' > ', ''))) DIV 3 + 1) AS deepest_level
FROM MapsPlace
WHERE category_path IS NOT NULL
GROUP BY top_category
ORDER BY places DESC, top_categoryAnother way
SELECT top_category, COUNT(*) AS places, MAX(levels) AS deepest_level FROM (SELECT CASE WHEN LOCATE(' > ', category_path) = 0 THEN category_path ELSE LEFT(category_path, LOCATE(' > ', category_path) - 1) END AS top_category, LENGTH(category_path) - LENGTH(REPLACE(category_path, '>', '')) + 1 AS levels FROM MapsPlace WHERE category_path IS NOT NULL) p GROUP BY top_category ORDER BY places DESC, top_category← Google: Local Guides Whose Ratings Turned Harsher · Google: Gmail Spam Filter Precision and Recall per Model →