Google: Places per Top-Level Maps Category

Medium
684.

Google: Places per Top-Level Maps Category

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

ColumnType
place_idint
place_namevarchar
category_pathvarchar

Primary key: place_id.

Category names never contain >; a path has no leading or trailing spaces. NULL means the place is not categorised yet.

Example

The rows must come back in the order shown.

MapsPlace

place_idplace_namecategory_path
1Vidyarthi BhavanFood > Restaurant > South Indian
2ToitFood > Bar > Brewpub
3Indian Coffee HouseFood > Cafe
4LalbaghOutdoors > Garden
5Cubbon ParkOutdoors > Park
6Phoenix MallShopping
7Unnamed pinNULL
8Chinnaswamy StadiumSports > Stadium > Cricket > Pavilion

Output

top_categoryplacesdeepest_level
Food33
Outdoors22
Shopping11
Sports14
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

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

ColumnType
place_idint
place_namevarchar
category_pathvarchar

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_idplace_namecategory_path
1Vidyarthi BhavanFood > Restaurant > South Indian
2ToitFood > Bar > Brewpub
3Indian Coffee HouseFood > Cafe
4LalbaghOutdoors > Garden
5Cubbon ParkOutdoors > Park
6Phoenix MallShopping
7Unnamed pinNULL
8Chinnaswamy StadiumSports > Stadium > Cricket > Pavilion

Output

top_categoryplacesdeepest_level
Food33
Outdoors22
Shopping11
Sports14

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_category

Another 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 →