How should I practice Per-Segment Speeding?

Start by reading the full statement, solve the visible examples, then compare the pattern against related OnePay phone screen problems in FastPrep.

Is Per-Segment Speeding associated with OnePay?

FastPrep tags this as a OnePay phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

Per-Segment Speeding

Learn this problem

● Medium

OnePayFULLTIMEPHONE SCREEN

Problem statement

You are given a chronological array of highway toll records logs. Each record has four whitespace-separated fields:

timestamp licensePlate boothId eventType

The eventType is ENTRY, MAINROAD, or EXIT. Records for different license plates may be interleaved. Each timestamp is decimal seconds with exactly three fractional digits and is interpreted exactly as integer milliseconds.

For one car, a complete journey begins with ENTRY, contains zero or more MAINROAD events, and ends with EXIT.

The array roadSegments supplies directed road metadata. Each record has four whitespace-separated fields:

fromBooth toBooth distanceMeters speedLimitKph

For every pair of consecutive records in a candidate journey, compute the exact average speed over the directed segment. A segment is speeding only when its average speed is strictly greater than speedLimitKph; equality is not speeding. Equivalently, with elapsed time in milliseconds, the segment is speeding when:

distanceMeters * 3600 > speedLimitKph * elapsedMilliseconds

An ENTRY starts a new candidate journey for that plate and replaces any unfinished candidate. A MAINROAD event extends an active candidate and is ignored otherwise. An EXIT completes and closes an active candidate and is ignored otherwise. Violations from a replaced or unfinished candidate are discarded.

Represent a speeding segment by the zero-based index in logs of its ending record. Return all such indices that belong to completed journeys in increasing input order.

Function

detectSpeedingSegments(logs: String[], roadSegments: String[]) → int[]

Examples

Example 1

logs = ["0.000 CAR1 A ENTRY","10.000 CAR2 X ENTRY","30.000 CAR1 B MAINROAD","50.000 CAR2 Y EXIT","90.000 CAR1 C EXIT"]roadSegments = ["A B 1000 60","B C 1000 60","X Y 500 45"]return = [2]

The A-to-B segment averages 120 km/h, above its 60 km/h limit, so index 2 is returned. The other two segments exactly equal their limits and are not speeding.

Example 2

logs = ["0.000 CAR1 A ENTRY","10.000 CAR1 B MAINROAD","11.000 CAR1 X ENTRY","31.000 CAR1 Y EXIT","40.000 CAR2 P EXIT"]roadSegments = ["A B 1000 60","X Y 500 90"]return = []

The first segment is speeding, but the later ENTRY replaces that unfinished candidate, so its violation is discarded. The completed X-to-Y segment exactly equals its limit, and the final EXIT is stray.

Example 3

logs = ["0.000 CAR1 A ENTRY","1.000 CAR2 X ENTRY","10.000 CAR1 B MAINROAD","11.000 CAR2 Y MAINROAD","12.000 CAR2 Z EXIT","20.000 CAR1 C EXIT"]roadSegments = ["A B 1000 100","B C 1000 360","X Y 1000 100","Y Z 100 360"]return = [2,3]

Both segments ending at indices 2 and 3 are speeding. CAR2 completes before CAR1, but the result is ordered by log index, so the output is [2,3].

Constraints

0 <= logs.length <= 200000
0 <= roadSegments.length <= 200000
Every log contains exactly four non-empty whitespace-separated fields and uses event type ENTRY, MAINROAD, or EXIT.
Every timestamp is nonnegative decimal seconds with exactly three fractional digits, its whole-seconds part is at most 10^9, and logs is in chronological order.
Within an active candidate journey, every record after its ENTRY has a strictly greater timestamp than the preceding record for that plate.
Every road record contains two booth IDs, an integer distanceMeters in [1, 10^9], and an integer speedLimitKph in [1, 10^6].
Each directed booth pair appears at most once in roadSegments, every segment used by an active candidate has supplied metadata, and all comparison cross-products fit in a signed 64-bit integer.