Maximum Edge Removals for Two Travelers
Updated
Problem statement
An undirected graph has n vertices labeled 1..n. Each edge is [type,u,v]: type 1 can be used only by Alice, type 2 only by Bob, and type 3 by both.
Return the maximum number of edge entries that can be removed while each traveler can still reach every vertex from every other vertex using their permitted edges. If this is impossible even before removals, return -1.
For this exercise, assume an empty edge list is allowed. A graph with one vertex is connected without edges, so that input returns 0.
Function
maxRemovableEdges(n: int, edges: int[][]) → intExamples
Example 1
n = 4edges = [[3,1,2],[3,2,3],[1,1,4],[2,3,4],[1,1,3]]return = 1Remove the Alice-only edge [1,1,3]. The shared edges connect vertices 1,2,3, and each traveler has a permitted edge to 4. At least four retained edges are required here, so removing one of the five is optimal.
Example 2
n = 3edges = [[3,1,2],[1,2,3]]return = -1Bob can use only [3,1,2], leaving vertex 3 unreachable. Removing edges cannot repair that disconnection, so return -1.
Constraints
- For this exercise, assume 1 <= n <= 200.
- For this exercise, assume 0 <= edges.length <= 2000.
- Each edge has exactly three integers [type,u,v], with type in {1,2,3} and 1 <= u < v <= n.
- All [type,u,v] tuples are distinct. Different types may join the same two vertices.
More Morgan Stanley Onsite Interview questions
- Generate Strings of Length at Least ThreeONSITE INTERVIEW · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Kth Largest Array ElementONSITE INTERVIEW · Seen Jul 2026
- Run-Length Encode Consecutive Letter RunsONSITE INTERVIEW · Seen Jul 2026
- Remove K DigitsONSITE INTERVIEW · Seen Oct 2025
- Count Ideal ArraysONSITE INTERVIEW · Seen Aug 2023
- Distinct Palindrome PartitionsONSITE INTERVIEW · Seen Aug 2023
- LFU Cache OperationsONSITE INTERVIEW · Seen Aug 2023
- All-Pairs Shortest PathsOA · ONSITE INTERVIEW · Seen Feb 2022
- Fibonacci with Input ValidationONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Water Supply With Wells and PipesNutanix · ONSITE INTERVIEWNutanix interview questions
- Minimum Cost for Roads and HospitalsAmazon · ONSITE INTERVIEW
- Minimum Cost to Supply Water with Wells and PipesInfosys · OAInfosys interview questions
- Doctor Appointment Slot AssignmentDRW · OADRW interview questions
- Dynamic Friendship ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
- Find All People With SecretIDFC Bank · ONSITE INTERVIEWIDFC Bank interview questions
- Making a Large IslandMeta · ONSITE INTERVIEWMeta interview questions
- Largest Island After One Land ConversionBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Evaluate DivisionPlaud · ONSITE INTERVIEW
- Count Friend CirclesOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley Apprenticeship and Tech Interviews: 6 Experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)