Quick Overview

This question evaluates stateful event-stream processing and per-entity state management, testing the ability to track and reconcile time-ordered sensor events while handling edge cases like unmatched or spurious events.

Count completed car journeys from sensor logs

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are given a time-ordered list of highway sensor logs. Each log entry contains: - `timestamp` (integer; strictly increasing) - `sensor_type` (one of `"ENTRY"`, `"EXIT"`, `"CHECKPOINT"`) - `car_id` (string) A **journey** is defined as: for the same `car_id`, an `ENTRY` event followed later by an `EXIT` event. `CHECKPOINT` events may occur in between but do not affect the definition. A car may make multiple journeys over time (e.g., `ENTRY ... EXIT ... ENTRY ... EXIT`). If a car has an `ENTRY` without a subsequent `EXIT` by the end of the logs, that partial journey does **not** count. If an `EXIT` occurs when the car is not currently in an active journey (i.e., there was no unmatched prior `ENTRY`), ignore it. Write a function that returns the total number of completed journeys across all cars. Example: Logs: 1. (1, "ENTRY", "A") 2. (2, "CHECKPOINT", "A") 3. (3, "EXIT", "A") 4. (4, "EXIT", "B") 5. (5, "ENTRY", "A") 6. (6, "ENTRY", "B") 7. (7, "EXIT", "B") Result: 2 (A completes 1 journey at t=3; B completes 1 journey at t=7).

Quick Answer: This question evaluates stateful event-stream processing and per-entity state management, testing the ability to track and reconcile time-ordered sensor events while handling edge cases like unmatched or spurious events.

You are given a time-ordered list of highway sensor logs. Each log entry is a tuple of the form (timestamp, sensor_type, car_id), where sensor_type is one of "ENTRY", "EXIT", or "CHECKPOINT". A completed journey happens when the same car_id has an "ENTRY" event followed later by an "EXIT" event. "CHECKPOINT" events may appear in between and do not affect the journey state. Rules: - An "ENTRY" starts a journey for that car if it is not already in an active journey. - An "EXIT" completes a journey only if the car currently has an unmatched prior "ENTRY". - If an "EXIT" appears for a car with no active journey, ignore it. - If a car is already in an active journey and another "ENTRY" appears before an "EXIT", ignore the extra "ENTRY". - Any car still in an active journey at the end of the logs does not count as completed. Return the total number of completed journeys across all cars.

Constraints

  • 0 <= len(logs) <= 200000
  • Each log entry is (timestamp, sensor_type, car_id), with strictly increasing integer timestamps
  • sensor_type is one of "ENTRY", "EXIT", or "CHECKPOINT"

Examples

Input: ([(1, "ENTRY", "A"), (2, "CHECKPOINT", "A"), (3, "EXIT", "A"), (4, "EXIT", "B"), (5, "ENTRY", "A"), (6, "ENTRY", "B"), (7, "EXIT", "B")],)

Expected Output: 2

Explanation: A completes one journey at timestamp 3. B has an unmatched EXIT at timestamp 4, then completes one journey from timestamp 6 to 7. A's second ENTRY has no EXIT, so it does not count.

Input: ([],)

Expected Output: 0

Explanation: There are no logs, so no journeys are completed.

Hints

  1. Think about what information you need to remember for each car while scanning the logs from left to right.
  2. Because the logs are already time-ordered, a single pass with a hash set is enough.

Loading coding console...