Compute Number of Locations
Updated
Problem statement
You want to buy a car and will drive it around N locations, numbered 1 to N. There are M roads. Road j is given as roads[j] = [u, v, d]: it connects locations u and v in both directions and has length d.
The car's fuel tank holds L units of fuel, and driving 1 unit of distance uses 1 unit of fuel. You live at location 1 and start there with a full tank.
Some locations have a gas station: g[i - 1] = 1 if location i has one, and g[i - 1] = 0 if it does not. Location 1 always has one. When you reach a location with a gas station, you can fill the tank back up to L. You may refuel at any station as many times as you like, and reaching a station with exactly 0 fuel left is fine. You must never run out of fuel before reaching the next location.
A location counts as visitable if you can drive from location 1 to it and then back to location 1 without running out of fuel. You may take any route. Location 1 itself counts. Return the number of visitable locations.
Function
computeNumberOfLocations(N: int, M: int, L: int, g: int[], roads: int[][]) → int Complete the function computeNumberOfLocations in the editor.
computeNumberOfLocations has the following parameters:
int N: the number of locationsint M: the number of roadsint L: the fuel tank capacityint[] g:g[i - 1]is1if locationihas a gas station, else0int[][] roads:Mrows[u, v, d], one per road
The function returns an int: the number of locations you can visit and come back home from without running out of fuel.
Examples
Example 1
N = 6M = 6L = 10g = [1, 0, 0, 1, 0, 0]roads = [[1, 2, 4], [1, 3, 6], [2, 4, 5], [3, 6, 3], [4, 5, 5], [5, 6, 8]]return = 4Locations 1 and 4 have gas stations, and the tank holds 10.
- Location 1 is home, so it counts.
- Location 2 is 4 away from home: 4 there and 4 back uses 8 ≤ 10 fuel. It counts.
- Location 4 is 9 away (1 → 2 → 4). You arrive with 1 fuel left, refill, and drive back the same way. It counts.
- Location 5 is 5 away from the station at 4: 5 there and 5 back uses exactly 10. It counts.
- Location 3 is 6 away from home, and every other station is farther. A round trip needs 12 > 10 fuel, so it does not count.
- Location 6 is 9 from home (1 → 3 → 6) and 13 from station 4 (4 → 5 → 6). Neither round trip fits in 10, so it does not count.
The visitable locations are 1, 2, 4 and 5, so the answer is 4.
Constraints
2 ≤ N ≤ 1051 ≤ M ≤ 105roads.length = Mand eachroads[j]has exactly 3 numbers[u, v, d]g.length = N1 ≤ L ≤ 109g[i]is0or1, andg[0] = 11 ≤ u < v ≤ Nfor every road1 ≤ d ≤ 106for every road- Roads are sorted by their first location:
roads[j][0] ≤ roads[j + 1][0]. - No two roads connect the same pair of locations.
- Every location can be reached from location 1 by roads.
- Route lengths can reach about
1011, so add distances in 64-bit integers.
More Money Forward interview questions
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
- Energy CrisisRubrik · OARubrik interview questions
- Best Telescope SiteAtlassian · OAAtlassian interview questions
- Cheapest Flight with Its PathAirbnb · OA · ONSITE INTERVIEWAirbnb interview questions
- Traveling the GraphsOptiver · OAOptiver interview questions