FastPrepMinimum Security Threshold for a Directed Path
Problems/Minimum Security Threshold for a Directed Path

Minimum Security Threshold for a Directed Path

Google logoGoogle● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks to "minimize the maximum edge weight along a path".

It uses an undirected graph and later asks about directed edges. Here, edges are directed, weights may be negative, and the result is the smallest integer strictly above the best bottleneck. Equal endpoints return 0 and unreachable targets return -1. The editorial explains the graph mapping and the unclear -1 value.

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

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) → long

Examples

Example 1

n = 4edges = [[0,1,4],[1,3,7],[0,2,6],[2,3,5]]source = 0target = 3return = 7

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

Both negative-security edges are usable once S reaches -1.

Example 3

n = 3edges = [[0,1,1]]source = 0target = 2return = -1

The 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

Interview reports that mention this question

  • Google SWE III ML Interviews: 11 Experiences (Part 1 of 3)

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public long minimumSecurityThreshold(int n, int[][] edges, int source, int target) {
        // write your code here
    }
}
Checking account…