Count Trips From Vehicle Logs
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a text log of vehicle events on a road system. Each log record contains:
- `license_plate`: a string identifying a vehicle
- `event_type`: one of `ENTRY`, `ROAD`, or `EXIT`
A vehicle completes one valid trip when the same license plate appears in the order:
`ENTRY -> ROAD -> EXIT`
There may be many vehicles in the log, and the same vehicle may complete multiple trips. Events for different vehicles may be interleaved.
Implement a function `get_trip(logs)` that returns the total number of completed trips across all license plates.
Example:
```text
logs = [
("A123", "ENTRY"),
("B999", "ENTRY"),
("A123", "ROAD"),
("A123", "EXIT"),
("B999", "ROAD"),
("B999", "EXIT"),
("A123", "ENTRY"),
("A123", "EXIT")
]
```
The result should be `2`, because `A123` and `B999` each completed one `ENTRY -> ROAD -> EXIT` trip. The final `A123 ENTRY -> EXIT` does not count because it is missing a `ROAD` event.
Clarify and handle reasonable edge cases, such as duplicate `ENTRY` events, `EXIT` before `ENTRY`, and multiple trips for the same license plate.
Quick Answer: This question evaluates the ability to process sequential event logs and reason about per-entity state transitions, exercising skills in data structures, event-stream processing, and correctness under interleaved records.
You are given a chronological list of vehicle log records. Each record is a tuple `(license_plate, event_type)`, where `event_type` is one of `ENTRY`, `ROAD`, or `EXIT`.
A vehicle completes one valid trip when the same license plate is seen in this order:
`ENTRY -> ROAD -> EXIT`
Events for different vehicles may be interleaved, and the same vehicle may complete multiple trips.
For this problem, implement `solution(logs)` that returns the total number of completed trips across all license plates.
Use these rules to handle edge cases consistently:
- `ENTRY` starts a new candidate trip for that license plate, replacing any incomplete trip already in progress.
- `ROAD` only matters if that vehicle has already had an `ENTRY` for its current candidate trip.
- `EXIT` counts as a completed trip only if the current candidate already has both `ENTRY` and `ROAD`.
- After any `EXIT`, the current candidate trip for that vehicle is cleared.
- Invalid or out-of-order events simply do not create a completed trip.
Example:
If the logs contain:
`('A123', 'ENTRY'), ('A123', 'ROAD'), ('A123', 'EXIT')`
then that contributes 1 trip.
But `('A123', 'ENTRY'), ('A123', 'EXIT')` contributes 0 because `ROAD` is missing.
Constraints
- 0 <= len(logs) <= 200000
- Each log record is a tuple `(license_plate, event_type)`
- `license_plate` is a non-empty string
- `event_type` is one of: `ENTRY`, `ROAD`, `EXIT`
Examples
Input: ([('A123', 'ENTRY'), ('B999', 'ENTRY'), ('A123', 'ROAD'), ('A123', 'EXIT'), ('B999', 'ROAD'), ('B999', 'EXIT'), ('A123', 'ENTRY'), ('A123', 'EXIT')],)
Expected Output: 2
Explanation: A123 completes one valid trip and B999 completes one valid trip. The final A123 sequence is ENTRY -> EXIT, so it does not count.
Input: ([],)
Expected Output: 0
Explanation: No logs means no completed trips.
Hints
- Treat each license plate independently, even though their events are interleaved in one shared log.
- A small state machine per vehicle is enough: no active trip, seen ENTRY, or seen ENTRY and ROAD.