How should I practice Minimum Product Path in a Directed Graph?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Minimum Product Path in a Directed Graph associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Minimum Product Path in a Directed Graph

Google● MediumFULLTIMEONSITE INTERVIEW

Problem statement

A directed graph has n nodes numbered from 0 to n - 1. Each row edges[i] = [from, to, weight] is a one-way edge from node from to node to with a positive integer weight.

The cost of a path is the product of its edge weights, not their sum. A path with no edges has cost 1.

Return the minimum cost of any path from source to target. Return -1 if target cannot be reached from source.

The problem statement continues

Pro

Examples

Example 1

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

There are two paths from node 0 to node 3:

0 -> 1 -> 3 costs 2 * 3 = 6.
0 -> 2 -> 3 costs 5 * 1 = 5.

The minimum product is 5. If weights were added instead, the path through node 1 would win with 2 + 3 = 5 against 5 + 1 = 6, so using products changes the best route.

FastPrep Pro

Reported in 1 Google interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

Full problem statement and constraints
2 more worked examples, explained
Guided hints and editorial
Run your code on real test cases

$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week

See Google hiring insights