How should I practice Least-Strong Common Defeater?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Confluent phone screen problems in FastPrep.

Is Least-Strong Common Defeater associated with Confluent?

FastPrep tags this as a Confluent phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Least-Strong Common Defeater

Learn this problem

● Hard

ConfluentFULLTIMEPHONE SCREEN

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

Examples

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 1 through 30.
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.