Energy Crisis
Updated
Problem statement
You are given a connected undirected graph with energy e[i] assigned to each vertex. Every edge must connect vertices whose energies differ by exactly 1.
Each row [u, v, flag] has one of two meanings:
- If
flag = 1, the direction is fixed and must satisfye[v] = e[u] + 1. - If
flag = 0, eithere[v] = e[u] + 1ore[u] = e[v] + 1is allowed.
If no assignment satisfies every edge, return -1. Otherwise return the maximum possible disparity max(e) - min(e).
Function
maximizeStellarGradient(n: int, edges: int[][]) → intExamples
Example 1
n = 6edges = [[5, 6, 1], [3, 4, 0], [1, 4, 0], [4, 6, 0], [5, 1, 0], [4, 2, 1]]return = 3The maximum stellar gradient possible for the planet system is 3.
Example 2
n = 5edges = [[4, 3, 1], [3, 5, 1], [2, 4, 0], [1, 2, 1], [5, 1, 1]]return = -1No such configuration is possible, hence the output is -1.
Constraints
- The number of planets,
1 ≤ n ≤ 200 - The number of cosmic pathways,
1 ≤ m ≤ 2000
More Rubrik interview questions
- Delete and Freeze GameOA · Seen Nov 2026
- Delete K Subsets for Maximum ScoreOA · Seen Nov 2026
- Distribute Elements Into Two Arrays IIOA · Seen Nov 2026
- Minimum Replacements to Sort the ArrayOA · Seen Nov 2026
- All Balanced Strings from Minimum Parenthesis InsertionsONSITE INTERVIEW · Seen Nov 2026
- Insert into a Left-Complete Binary TreeONSITE INTERVIEW · Seen Oct 2026
- Thread-Safe Request Counts by AttributeONSITE INTERVIEW · Seen Oct 2026
- Minimum Swaps To Binary PalindromeOA · Seen Apr 2026
- Get Minimum OperationsOA · Seen Nov 2024
- Horizontal Pod AutoscalerOA · Seen Nov 2024
Similar questions at other companies
- Sum Dynamic Weighted Tree DistancesJuspay · OA
- Minimum Fuel Cost Between CitiesMicrosoft · OAMicrosoft interview questions
- Drone Delivery with Battery Swap StationsCisco · OACisco interview questions
- Optimal TransferSuperhuman · OASuperhuman interview questions
- Minimum Travel Time With Periodic Fast RoadsAdobe · OAAdobe interview questions
- Find the PathLinkedIn · OALinkedIn interview questions
- Compute Number of LocationsMoney Forward · OA
- Best Telescope SiteAtlassian · OAAtlassian interview questions
- Cheapest Flight with Its PathAirbnb · OA · ONSITE INTERVIEWAirbnb interview questions
- Traveling the GraphsOptiver · OAOptiver interview questions