Minimum Security Threshold for a Directed Path
Updated
Problem statement
A directed graph has nodes 0 through n-1. Each edge is [from,to,security].
You may traverse an edge only when its security value is strictly less than an integer threshold S. Return the minimum integer S that permits a path from source to target. Security values may be negative and the graph may contain cycles. Return 0 when the endpoints are equal and -1 when no path exists.
Function
minimumSecurityThreshold(n: int, edges: int[][], source: int, target: int) → longExamples
Example 1
n = 4edges = [[0,1,4],[1,3,7],[0,2,6],[2,3,5]]source = 0target = 3return = 7The path through node 2 has maximum edge security 6, so S must be 7.
Example 2
n = 3edges = [[0,1,-5],[1,2,-2]]source = 0target = 2return = -1Both negative-security edges are usable once S reaches -1.
Example 3
n = 3edges = [[0,1,1]]source = 0target = 2return = -1The target is unreachable.
Constraints
1 <= n <= 100000.0 <= edges.length <= 200000.-10^9 <= security <= 10^9.
More Google Onsite Interview questions
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
- Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Path With Maximum ProbabilitySalesforce · ONSITE INTERVIEWSalesforce interview questions
- Dijkstra's Shortest PathsMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Single-Source Shortest PathsRippling · ONSITE INTERVIEWRippling interview questions
- Minimum-Weight Path Through a MatrixMeta · ONSITE INTERVIEWMeta interview questions
- Hub Vertices Within a RadiusThe Walt Disney Company · ONSITE INTERVIEWThe Walt Disney Company interview questions
- Minimum Path Cost with Edge DiscountsSkyscanner · ONSITE INTERVIEWSkyscanner interview questions
- Shortest Paths in a Nonnegative Directed GraphNation with NaMo · PHONE SCREEN
- Dijkstra Shortest Paths in a Weighted Undirected GraphGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Shortest Paths to Multiple TargetsWaymo · PHONE SCREENWaymo interview questions