How should I practice Minimum Path Cost with Edge Discounts?

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

Is Minimum Path Cost with Edge Discounts associated with Skyscanner?

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

Problem · Graph

Minimum Path Cost with Edge Discounts

Learn this problem

● Hard

SkyscannerFULLTIMEONSITE INTERVIEW

Problem statement

You are given an undirected graph with nodes 0 through n - 1. Each edge [u, v, weight] has a positive integer cost.

Travel from node 0 to node n - 1. You may apply at most discounts discounts, each to a different traversal of an edge; a discounted edge costs floor(weight / 2). Return the minimum possible path cost, or -1 when the destination is unreachable.

Function

minimumPathWithDiscounts(n: int, edges: int[][], discounts: int) → long

Examples

Example 1

n = 5edges = [[0,1,4],[1,4,8],[0,2,2],[2,3,2],[3,4,10]]discounts = 1return = 8

Path 0-1-4 costs 4 + floor(8/2) = 8.

Example 2

n = 3edges = [[0,1,5]]discounts = 2return = -1

Node 2 is unreachable.

Constraints

2 <= n <= 10000.
0 <= edges.length <= 50000.
1 <= weight <= 1000000000.
0 <= discounts <= 20.