FastPrepMaximum Edge Removals for Two Travelers
Problems/Maximum Edge Removals for Two Travelers

Maximum Edge Removals for Two Travelers

Morgan Stanley logoMorgan Stanley● HardINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Morgan Stanley onsite interview for interns. The author describes a graph task like the linked two-traveler edge-removal problem. Here we use the model from that problem. The exact interview twist is not reported. We chose the interface, the limits, and how inputs with no edges work.

Our version is about 80% the same as the reported question.

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[][]) → int

Examples

Example 1

n = 4edges = [[3,1,2],[3,2,3],[1,1,4],[2,3,4],[1,1,3]]return = 1

Remove 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 = -1

Bob 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 Intern Interviews: 25 Experiences (Part 1 of 5)

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)
All Morgan Stanley interview questionsSee Morgan Stanley hiring insights
Saved
class Solution {
    public int maxRemovableEdges(int n, int[][] edges) {
        // Write your code here.
    }

}
Checking account…