Seconds Until Graph Vertices Stop Disappearing
Updated
Problem statement
An undirected graph has N vertices, numbered 0 through N - 1. Arrays A and B describe its edges: edge i connects A[i] and B[i].
Each second, remove every remaining vertex that has at most one edge connected to it. Remove these vertices and their edges at the same time. A vertex isolated from the start is removed in the first second. If a removal leaves another vertex with at most one edge, remove that vertex in the next second.
Return the number of seconds in which vertices are removed. Stop when no more vertices can be removed. Return zero if no vertex can be removed at the start.
Function
solution(N: int, A: int[], B: int[]) → intExamples
Example 1
N = 7A = [0,1,2,1,4,4]B = [1,2,0,4,5,6]return = 2The first second removes isolated vertex 3 and the degree-one vertices 5 and 6. The next second removes vertex 4. Vertices 0, 1 and 2 form a stable triangle.
Example 2
N = 4A = [0,1,2]B = [1,2,3]return = 2Both endpoints disappear together, then the two remaining vertices disappear in the next second.
Example 3
N = 3A = [0,1,2]B = [1,2,0]return = 0Every vertex in the triangle has degree two, so no removal occurs.
Constraints
- For this exercise, assume
1 <= N <= 100000and0 <= A.length = B.length <= 200000. - Every endpoint is in
0throughN - 1. - For this exercise, assume the graph has no self-loops or repeated undirected edges.
More Marshall Wace Online Assessment questions
- Count Letters with Ordered Lowercase and Uppercase OccurrencesOA · Seen Oct 2025
- Maximum Trailing Zeros on a Path with at Most One TurnOA · Seen Oct 2025
- Shortest Subarray Covering an Integer RangeOA · Seen Oct 2025
- Maximum Events in a 60-Second WindowOA · Seen Aug 2025
- Successful Logins from Multiple CountriesOA · Seen Aug 2025
- Maximize Remaining Item Types After Clearing Consecutive ShelvesOA · Seen Nov 2024
- Shortest String After Erasing Equal PairsOA · Seen Nov 2024
- Count Distinct Tags in a Fixed-Radius Circle (Practice Reconstruction)OA · Seen Apr 2024
- Generate Unique Company Email AddressesOA · Seen Apr 2024
- Reconstruct a Two-Row Binary MatrixOA · Seen Apr 2024
Similar questions at other companies
- Distances to CyclesBelvedere Trading · OA
- Cogwheel Rotation DirectionsOpenAI · OAOpenAI interview questions
- Shortest Path in an Unweighted GraphCitadel · OACitadel interview questions
- Order DAG Nodes from Leaves to RootsVercel · ONSITE INTERVIEW
- Recipes You Can PrepareIndeed · PHONE SCREENIndeed interview questions
- Crawl Reachable Pages with Bounded RetriesSnowflake · PHONE SCREENSnowflake interview questions
- Breadth-First Order of a GraphAdobe · PHONE SCREENAdobe interview questions
- Minimum Operations to Sort with Rotations Then SwapsBank of New York Mellon · OA
- Delivery Management SystemAkuna Capital · OAAkuna Capital interview questions
- Get Message StatusSalesforce · OASalesforce interview questions