← Headway Interview Insights

Headway·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Headway software engineer interview, part of a three-question object-oriented design scenario that built on itself. The journey-counting problem was the middle chunk and it had more edge cases than I expected going in.

Questions Asked (1)

Q1

Given a log of road events parsed into typed objects (ENTRY, MAINROAD, EXIT), implement a function that counts the total number of complete journeys across all vehicles, where events from different vehicles may be interleaved.

Algorithms & Data StructuresSystem Design
Author's notes

My first instinct was to just count ENTRY events and call it a day, which is wrong the moment you think about interleaving.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the event semantics and journey definition, then design a state machine per vehicle using a hash map to track each vehicle's current state. Iterate through the log once, updating states and counting completed journeys when a vehicle transitions from MAINROAD to EXIT.

Pro tip: Mention that you would validate the input log for consistency (e.g., no duplicate ENTRY without EXIT) and discuss how to handle edge cases like incomplete journeys or out-of-order events, showing attention to data quality.

1. Clarify requirements and assumptions

Ask the interviewer to confirm the definition of a complete journey (e.g., ENTRY → MAINROAD → EXIT) and whether events are guaranteed to be in chronological order per vehicle. Also clarify if a vehicle can have multiple journeys and if events can be missing.

2. Design the data structure

Use a hash map (dictionary) to track each vehicle's current state, mapping vehicle ID to its last event type or a state enum. This allows O(1) updates per event and handles interleaved vehicles.

3. Define state transitions and counting logic

Specify valid transitions: ENTRY → MAINROAD → EXIT. Increment the journey count when a vehicle in MAINROAD state receives an EXIT event. Reset or remove the vehicle's state after a complete journey or on invalid transitions.

4. Iterate through the log and process events

Loop through each event in order, update the vehicle's state in the map, and apply the counting logic. Handle edge cases like EXIT without prior ENTRY or MAINROAD by ignoring or logging errors.

5. Analyze complexity and test

State that the algorithm runs in O(n) time and O(v) space, where n is the number of events and v is the number of vehicles. Walk through a small example with interleaved events to verify correctness.

Key Points to Mention

  • Use a hash map to track per-vehicle state, enabling O(1) updates and handling interleaved events.
  • Define a clear state machine with valid transitions (ENTRY → MAINROAD → EXIT) and count only complete journeys.
  • Handle edge cases: incomplete journeys, out-of-order events, duplicate entries, and vehicles with multiple journeys.
  • Discuss time and space complexity: O(n) time, O(v) space, where n is number of events and v is number of vehicles.
  • Consider input validation and error handling for malformed logs, showing production-quality thinking.
  • Mention potential extensions: streaming processing, parallelization, or handling large logs with limited memory.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.