Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
The data team wants to split a warehouse into families of tables. Two tables are in the same family if one feeds the other, or if both are linked through a third table. Each family can then be owned by one team.
Write group_tables(tables, links). tables is a list of table names. links is a list of [a, b] pairs, which means the two tables are linked. Return a list of groups. Each group is a sorted list of table names.
Function to write
group_tables(tables: list[str], links: list[list[str]]) -> list[list[str]]A list of groups; each group is a sorted list of table names, and the groups are sorted by first name.
How to approach it
Give every table a leader. For each link, find the leader of both tables and point one at the other. At the end, tables with the same leader are one group.
Sample cases
+ 3 held back until you submit
two chains and a loner
`raw_orders`, `orders` and `orders_daily` are one group by a chain. `raw_users` and `users` are another. `scratch` is alone.
Input
Argument 1
[
'raw_orders',
'orders',
'orders_daily',
'raw_users',
'users',
'scratch'
]Argument 2
[
[
'raw_orders',
'orders'
],
[
'orders',
'orders_daily'
],
[
'raw_users',
'users'
]
]Returns
[
[
'orders',
'orders_daily',
'raw_orders'
],
[
'raw_users',
'users'
],
[
'scratch'
]
]two groups that join later
The last link joins two groups that were already separate, so all four tables end up together.
Input
Argument 1
[
'a',
'b',
'c',
'd'
]Argument 2
[
[
'a',
'b'
],
[
'c',
'd'
],
[
'b',
'c'
]
]Returns
[
[
'a',
'b',
'c',
'd'
]
]a table only seen in a link
`ghost` is not in the table list, but it is in a link, so it still belongs to the group.
Input
Argument 1
[
'a'
]Argument 2
[
[
'a',
'ghost'
]
]Returns
[
[
'a',
'ghost'
]
]nothing at all
No tables and no links give no groups.
Input
Argument 1
[] (empty list)
Argument 2
[] (empty list)
Returns
[] (empty list)
Constraints
a–b and b–c are linked, then a, b and c are one group.tables.Worked example
Take the tables raw_orders, orders, orders_daily, raw_users, users and scratch, with the links raw_orders–orders, orders–orders_daily and raw_users–users. At the start every table is its own group. The first link joins raw_orders and orders. The second joins the group of orders with orders_daily, so the group is now three tables. The third joins raw_users and users. scratch never appears in a link. The answer has three groups, and the first is ['orders', 'orders_daily', 'raw_orders'].
The trap: if you make one group per link, the chain raw_orders–orders–orders_daily becomes two groups that both contain orders.
What this tests
Union-find (also called disjoint sets), the idea behind 'Number of Provinces' and 'Accounts Merge'. Each table points to a leader. To join two tables, you point one leader at the other. Following the pointers to the leader is called find. Data engineers use it to cluster tables by lineage, or to merge records that share an ID.
group_tables(tables: list[str], links: list[list[str]]) -> list[list[str]]Submit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.