Least-Strong Common Defeater
Updated
Problem statement
You are given distinct monster names in monsters and a directed acyclic graph defeats. Each pair [a, b] means monster a can directly defeat monster b. Defeat is transitive: if a can defeat b and b can defeat c, then a can defeat c.
Find a monster that can defeat every monster in targets through a path containing at least one edge. Among all such common defeaters, return a least-strong one: a qualifying monster x is not least-strong when it can defeat a different qualifying monster y, because y is strictly weaker while still defeating every target.
If several incomparable least-strong monsters remain, return the lexicographically smallest name. Return the empty string when no monster can defeat every target.
Function
leastStrongDefeater(monsters: String[], defeats: String[][], targets: String[]) → StringExamples
Example 1
monsters = ["Dragons","Zombies","Goblins","Snakes"]defeats = [["Dragons","Zombies"],["Dragons","Goblins"],["Zombies","Goblins"],["Goblins","Snakes"]]targets = ["Snakes","Goblins"]return = "Zombies"Both Dragons and Zombies can defeat both targets. Because Dragons can defeat Zombies, Zombies is the least-strong qualifying monster.
Example 2
monsters = ["A","B","C","X","Y"]defeats = [["A","X"],["A","Y"],["B","X"],["B","Y"],["C","A"]]targets = ["X","Y"]return = "A"A and B are incomparable least-strong common defeaters; C is stronger than A. The lexicographic tie-break returns A.
Example 3
monsters = ["A","B","C"]defeats = [["A","B"]]targets = ["B","C"]return = ""No monster can reach both B and the disconnected monster C.
Constraints
1 <= monsters.length <= 1000.0 <= defeats.length <= 5000.1 <= targets.length <= monsters.length.- Monster names are unique, contain only ASCII letters, digits, underscores, and hyphens, and have length from
1through30. - Every edge contains two different names from
monsters; duplicate edges may appear. - Every target is present in
monsters; targets are distinct. - The directed graph is acyclic.
More Confluent Phone Screen questions
- Implement tail -nPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sudoku Board ValidationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sudoku Puzzle SolverPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Match a Variadic Function SignaturePHONE SCREEN · Seen Oct 2026
- Sequential Phrase Search Across DocumentsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Time Map with Sum and AveragePHONE SCREEN · Seen Sep 2026
- Time-Based Key-Value Store with Range AggregatesPHONE SCREEN · Seen Sep 2026
- Word Search Across DocumentsPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Windowed Key-Value MapPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2025
- Wildcard Matching with StarsPHONE SCREEN · Seen Mar 2021
Similar questions at other companies
- Course Order and CycleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Task Build Order and File-Change RerunsVanta · PHONE SCREEN
- All Halfway Courses Across Course TracksCrunchyroll · PHONE SCREENCrunchyroll interview questions
- Course Schedule Cycle DetectionGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Course ScheduleNykaa · PHONE SCREENNykaa interview questions
- Effective Role PrivilegesSnowflake · PHONE SCREENSnowflake interview questions
- Course ScheduleBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delivery Origins and Reachable DestinationsAtlassian · PHONE SCREENAtlassian interview questions
- Course Schedule FeasibilityTesla · PHONE SCREENTesla interview questions
- Deepest Common Ancestors in a Multi-Parent DAGSalesforce · ONSITE INTERVIEWSalesforce interview questions