Bills From Unordered Highway Checkpoint Logs
Google● MediumNEW GRADPHONE SCREENProblem statement
Parallel arrays licenses, checkpoints, and timestamps describe unordered highway checkpoint logs. Entry i records one vehicle passing one checkpoint at one time.
Each vehicle makes one continuous trip. Sort that vehicle's records by timestamp and charge the fee for every consecutive ordered checkpoint pair. feePairs[i] is [from,to] and has fee fees[i]; every consecutive pair needed by the logs is present.
Return one string per vehicle in the format license:totalFee, ordered lexicographically by license. Vehicle/checkpoint names contain only letters and digits.
Function
billHighwayTrips(licenses: String[], checkpoints: String[], timestamps: int[], feePairs: String[][], fees: int[]) → String[]Examples
Example 1
licenses = ["A","B","A","A","B"]checkpoints = ["Y","P","X","Z","Q"]timestamps = [30,5,10,50,20]feePairs = [["X","Y"],["Y","Z"],["P","Q"]]fees = [7,4,3]return = ["A:11","B:3"]Vehicle A travels X→Y→Z for 7+4; vehicle B travels P→Q for 3.
Example 2
licenses = ["CAR9","CAR9"]checkpoints = ["EXIT","ENTRY"]timestamps = [20,10]feePairs = [["ENTRY","EXIT"]]fees = [12]return = ["CAR9:12"]The input is unordered, so timestamp sorting restores ENTRY→EXIT.
Example 3
licenses = []checkpoints = []timestamps = []feePairs = []fees = []return = []No log records produce no bills.
Constraints
0 <= licenses.length == checkpoints.length == timestamps.length <= 200000.0 <= feePairs.length == fees.length <= 200000.- Each vehicle has at least two records with distinct timestamps.
- Every fee is in
[0,10^9], and each total fits in a signed 64-bit integer. - Every needed ordered checkpoint pair appears exactly once in
feePairs.