How should I practice Smallest Common Region?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Airbnb phone screen problems in FastPrep.

Is Smallest Common Region associated with Airbnb?

FastPrep tags this as a Airbnb phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

Smallest Common Region

Learn this problem

● Medium

AirbnbFULLTIMEPHONE SCREEN

Problem statement

You are given a rooted hierarchy of named regions. Each row of regions starts with a parent region, followed by all of its direct child regions.

Given region1 and region2, return the smallest region that contains both. A region contains itself and every region in its descendant subtree.

The rows collectively describe one valid hierarchy. Every non-root region has exactly one parent, and every region name is unique within the hierarchy.

Function

findSmallestRegion(regions: String[][], region1: String, region2: String) → String

Examples

Example 1

regions = [["Earth","North America","South America"],["North America","United States","Canada"],["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]]region1 = "Quebec"region2 = "New York"return = "North America"

Quebec is under Canada, while New York is under United States. Their first shared ancestor is North America.

Example 2

regions = [["World","Asia","Europe"],["Asia","Japan","India"]]region1 = "Asia"region2 = "Japan"return = "Asia"

A region contains itself, so Asia is the smallest region containing both Asia and its descendant Japan.

Constraints

1 <= regions.length <= 1000.
Each row contains one parent and at least one direct child.
There are at most 1000 distinct region names.
The rows describe one valid rooted hierarchy with unique names and no cycles.
region1 and region2 both appear in the hierarchy.