## Problem Given an undirected graph where each node has a label, find the largest connected subgraph where all nodes share the same label. "Largest" means the most nodes. ```python def max_same_label_subgraph( n: int, edges: list[tuple[int,int]], labels: list[str] ) -> tuple[str, list[int]]: # returns: (label, list of node IDs in the largest same-label component) pass ``` **Example:** ``` n = 6 edges = [(0,1),(1,2),(2,3),(3,4),(4,5)] labels = ["A","A","A","B","B","A"] # Component {0,1,2} all label A -> size 3 # Component {5} label A -> size 1 # Component {3,4} label B -> size 2 result -> ("A", [0, 1, 2]) ``` ## Follow-ups 1. How does your BFS/DFS handle disconnected graphs (multiple components)? 2. What is the time and space complexity of your solution? 3. How would you extend this to find the largest subgraph where nodes satisfy a predicate (e.g., label in {A, B})? 4. If edges are weighted, how would you find the subgraph with the maximum total edge weight?

InterviewDB Question

Maximum Subgraph: Find the Largest Connected Subgraph Satisfying a Node Constraint

phone

Question Details

Problem Given an undirected graph where each node has a label, find the largest connected subgraph where all nodes share the same label. "Largest" means the most nodes. Example: Follow-ups How does your BFS/DFS handle disconnected graphs (multiple components)? What is the time and space complexity of your solution? How would you extend this to find the largest subgraph where nodes satisfy a predicate (e.g., label in {A, B})? If edges are weighted, how would you find the subgraph with the maximum…

Full Details

🔒

Unlock all Waymo questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a waymo interview during the phone round.

It covers the following topics: Coding, Phone, Graph .

Topics

Coding Phone Graph

Maximum Subgraph: Find the Largest Connected Subgraph Satisfying a Node Constraint

Question Details

Full Details

About This Question

Topics

More Waymo Interview Questions