Katkat
Back

Compute minutes since last train departure

Capital OneMachine Learning Engineer · Online Assessment
HardMachine Learning EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to manipulate time objects, handle cyclic day-wrap scenarios, and perform efficient searching on sorted lists.

Problem Statement

You are given a list of train departure times for a specific route in "HH:MM" format (24-hour clock). You are also given a current_time in "HH:MM" format. Your task is to write a function that returns the number of minutes since the most recent train departure.

If the most recent train departed earlier today, calculate the difference between current_time and that departure time. If no train has departed yet today, the "most recent" train is the last train that departed yesterday. If multiple trains share the same departure time, consider the latest one as the reference. If there are no departure times provided, return -1.

Function Signature

def minutes_since_last_departure(departure_times: list[str], current_time: str) -> int:

Constraints

  • departure_times contains between 1 and 1000 strings.
  • All times are in "HH:MM" format (00:00 to 23:59).
  • departure_times is not guaranteed to be sorted.

Examples

Example 1:

  • departure_times: ["08:30", "14:00", "18:15"]
  • current_time: "15:00"
  • Result: 60 (15:00 - 14:00 = 60 minutes)

Example 2:

  • departure_times: ["09:00", "22:00"]
  • current_time: "06:00"
  • Result: 480 (The last train yesterday was 22:00; 22:00 to 00:00 is 120m, 00:00 to 06:00 is 360m; 120 + 360 = 480 minutes)

Edge Cases

  • Current time matches a departure time exactly (result should be 0).
  • Only one departure time exists in the list.
  • Departure times span across midnight.

Hints

Hint 1

Convert all time strings into total minutes from the start of the day (00:00 = 0, 23:59 = 1439).

Hint 2

Sort the departure times to easily find the largest departure time less than or equal to the current time.

Hint 3

If no departure time is less than or equal to the current time, the most recent train is the latest time in the sorted list, occurring on the previous day (add 1440 minutes to the total duration).

Follow-up questions

  • How would you optimize this if the list of departure times was extremely large (e.g., millions of records)?
  • What changes would be needed if you had to account for time zones or Daylight Savings Time adjustments?
  • How would you modify the solution to return the time until the *next* train departs instead of the time since the last one?