Two-Level Flight Search System with Weekly Schedules and Arrival Times

Implement a simple in-memory flight search system. The task comes in two levels: Level 2 extends Level 1, and every Level 1 method must keep working after Level 2 is added. Each flight has a unique ID, an origin, a destination, a daily departure time written as `HH:MM` (24-hour clock), and a flight duration in whole minutes. The method names and signatures below are assumptions made for this write-up; the required behavior is what the task specifies. ### Constraints and Clarifications - Adding a flight fails if its origin equals its destination or if its ID is already in use. - Days of the week are written as three-letter uppercase codes: `MON`, `TUE`, `WED`, `THU`, `FRI`, `SAT`, `SUN`. - When results are sorted by departure time, only the clock time is compared; the day of the week is ignored. - A flight may land on a later day than it departs, so arrival calculations must handle crossing midnight. - This write-up treats the Level 2 "flights landing on a given day" query as a route query between an origin and a destination, because the task says it uses the same sort order as the Level 1 route search. ### Clarifying Questions - What should queries return for an unknown flight, airport, or day: an empty result or an error? - If two flights on the same route tie on both duration and departure time, how should they be ordered? - Can a flight's duration exceed 24 hours, so that it lands two or more days after it departs? - When the last operating day of a flight is removed, does the flight disappear entirely, and does its ID become free for reuse? - Should invalid inputs, such as a malformed time or a non-positive duration, also make an add fail? ### Part 1 — Level 1: flights that operate every day Implement a class with these operations: - `add_flight(flight_id, origin, destination, departure_time, duration_minutes)`: add a flight that departs every day at `departure_time`. Return whether it was added; it is rejected if `origin == destination` or if `flight_id` already exists. - `delete_flight(flight_id)`: remove the flight. Return whether a flight was removed. - `count_departures(origin)`: return the number of flights that depart from `origin`. - `search(origin, destination)`: return the IDs of all flights from `origin` to `destination`, sorted by duration ascending, and by departure time ascending when durations are equal. ```hint Index for the queries you have Look at what each query needs and decide which lookups should avoid scanning every flight in the system. ``` #### What This Part Should Cover - Data structures chosen for adding, deleting, counting and searching, with their complexities - Correct validation on add, and a clean result when deleting an unknown ID - A sort key that implements the specified order, with times compared as times rather than loosely as text ### Part 2 — Level 2: days of the week Flights can now operate only on specific days of the week. A flight added with the Level 1 `add_flight` operates every day. Add these operations while keeping every Level 1 method working: - `add_flight_on_days(flight_id, origin, destination, departure_time, duration_minutes, days)`: add a flight that departs only on the listed days, with the same validation as Level 1. - `delete_flight_on_day(flight_id, day)`: cancel the flight's departure on that day only. - `count_departures_on_day(origin, day)`: return the number of flights that depart from `origin` on `day`. - `get_arrival(flight_id, departure_day)`: for the flight's departure on `departure_day`, return the landing day and time in the format `"SAT, 21:30"`. The landing may fall on a later day. - `search_landing_on_day(origin, destination, day)`: return the IDs of flights from `origin` to `destination` that land on `day`, in the same order as the Level 1 search (duration, then departure time, comparing clock times only and ignoring the day). Level 1 methods must stay compatible, and each flight is counted only once: a flight that operates on several days still counts as one departure in `count_departures` and appears once in `search`. ```hint Minutes since the start of the week Look for a single representation of "day plus clock time" that turns adding a duration and finding the landing day into simple arithmetic. ``` ```hint One flight, many days Decide whether a flight's operating days belong to the flight itself or to separate per-day records, and check which choice makes the "counted only once" rule automatic. ``` #### Clarifying Questions for this Part - What should `get_arrival` return if the flight does not operate on `departure_day`? - If a flight could land on `day` from more than one of its operating days, should it still appear only once in `search_landing_on_day`? - Should cancelling a day the flight does not operate on count as a failure? #### What This Part Should Cover - A data model for operating days that leaves Level 1 behavior unchanged - Correct day-crossing arithmetic, including wrapping from `SUN` to `MON` - The "counted only once" rule applied consistently across counts and searches - The complexity of the new operations and any index changes they need ### What a Strong Answer Covers - A clean class design that grows from Level 1 to Level 2 without rewriting Level 1 - Explicit handling of every failure case the task names (same origin and destination, duplicate IDs), plus unknown IDs and days - Time handling that converts `HH:MM` to minutes and formats the arrival string exactly - Tests for crossing midnight and the end of the week, sort ties, and per-day cancellations ### Follow-up Questions - How would you add a query for itineraries with one connection and a minimum layover time? - Airports are now in different time zones, and departure and arrival times are local. What changes in your arithmetic and output? - How would your indexes change if searches were far more frequent than adds and deletes?