Metro Fare With a Daily Cap
Updated
Problem statement
A metro line has K stations in a row, numbered 0 to K - 1, where K is the length of limit. Neighbouring stations are linked, and trains run both ways.
One day a passenger takes several rides. Ride i boards at station start[i] and gets off at station dest[i], passing every station in between. A ride costs 1 to board plus 2 for every hop between neighbouring stations, so a ride over h hops costs 1 + 2h.
The day's charge is the sum of all ride costs, but it can never be more than a daily cap. The cap is limit[Y], where Y is the largest station number the passenger visited that day (as a start, a destination or a station passed on the way).
Return the amount the passenger is charged for the day.
Function
dailyCharge(start: int[], dest: int[], limit: int[]) → intExamples
Example 1
start = [0,3,1]dest = [2,1,4]limit = [5,5,5,5,30]return = 17- Ride 1 goes from station 0 to station 2: 2 hops, so it costs
1 + 2 * 2 = 5. - Ride 2 goes from station 3 back to station 1: also 2 hops, so 5.
- Ride 3 goes from station 1 to station 4: 3 hops, so
1 + 2 * 3 = 7. - The rides add up to 17. The largest station visited is 4, and
limit[4] = 30is more than 17, so the charge is 17.
Example 2
start = [1,0]dest = [0,3]limit = [2,8,4,6]return = 6- Station 1 to station 0 costs 3, and station 0 to station 3 costs
1 + 2 * 3 = 7, so the rides add up to 10. - The largest station visited is 3, so the cap is
limit[3] = 6. The passenger is charged 6.
Example 3
start = [5,1]dest = [3,2]limit = [2,2,2,2,2,7,1]return = 7- Station 5 to station 3 costs 5, and station 1 to station 2 costs 3, so the rides add up to 8.
- Station 5 is where a ride started, and it is the largest station visited, so the cap is
limit[5] = 7. The charge is 7. The cap does not come from the last station on the line (limit[6]) or from the largest destination (station 3).
Constraints
1 <= start.length <= 30dest.length == start.length2 <= limit.length <= 500 <= start[i], dest[i] <= limit.length - 11 <= limit[j] <= 3000start[i] != dest[i]
More Microsoft Online Assessment questions
- Minimum Cost to Process Priority TasksOA · Seen Nov 2026
- Most Visited Sprint MarkerOA · Seen Nov 2026
- Maximum Escape Game ScoreOA · Seen Nov 2026
- Count Subarrays with a Perfect-Square ProductOA · Seen Nov 2026
- Maximum Interactive Team SizeOA · Seen Nov 2026
- Maximize Pipeline Throughput Under a Scaling BudgetOA · Seen Nov 2026
- Minimum Cost K-Capable ModelsOA · Seen Nov 2026
- Find Available Meeting RoomsOA · Seen Oct 2026
- Maximum Sum of a K-StarOA · Seen Oct 2026
- Capacity to Ship Packages Within DaysOA · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Basic Item DiscountsPalantir · OAPalantir interview questions
- Diagonal Bounce TraversalAutodesk · OAAutodesk interview questions
- Costliest ChocolateRippling · OARippling interview questions
- Online No-Intercept Linear RegressionTwo Sigma · OATwo Sigma interview questions
- Plus Mult ArrayIBM · OAIBM interview questions
- Progressive Tax CalculatorInteractive Brokers · OA
- 2020 Account Balance with Monthly Card FeesDRW · OADRW interview questions
- Array Challenge (QR Intern)Akuna Capital · OAAkuna Capital interview questions
- Latency Bucket CounterDatadog · OA · PHONE SCREENDatadog interview questions
- First Fibonacci Number at Least the Array SumBitGo · OABitGo interview questions