How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Circle.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Circle during technical interviews.

Implement cheapest itinerary with date filters

Company: Circle

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Implement a function that computes the cheapest itinerary from a given origin to a destination using a list of flights, where each flight has (id, source, destination, departure_time, arrival_time, price). Only consider itineraries whose first departure falls within a provided date range. Return the minimum total price and the ordered list of flight IDs forming the itinerary; return -1 if no valid itinerary exists. Explain your algorithm, time/space complexity, and how you enforce time ordering between connections and avoid cycles.

Quick Answer: This question evaluates proficiency in graph algorithms and constrained pathfinding, including handling date filters for initial departures, time-ordered connections, cycle avoidance, and quantitative complexity analysis.

You are given a list of flights, where each flight is represented as a 6-tuple `(id, source, destination, departure_time, arrival_time, price)`. All values are integers: airports are identified by integer IDs, and times are integer timestamps. Write a function that finds the cheapest itinerary from `origin` to `destination`. The first flight in the itinerary must depart within the inclusive range `[start_date, end_date]`. Every later connection must satisfy `next_departure_time >= previous_arrival_time`. Return a tuple `(minimum_total_price, ordered_list_of_flight_ids)`. If no valid itinerary exists, return `-1`. If `origin == destination`, return `(0, [])`. In your explanation, describe your algorithm, its time and space complexity, how you enforce time ordering between connections, and why cycles do not break correctness.

Constraints

`0 <= len(flights) <= 200000`
Each flight is `(id, source, destination, departure_time, arrival_time, price)` with unique `id`
`0 <= departure_time < arrival_time <= 10^9` and `1 <= price <= 10^6`
`start_date <= end_date`

Examples

Input: ([(101, 1, 2, 10, 12, 100), (102, 2, 3, 13, 15, 80), (103, 1, 3, 11, 14, 300), (104, 2, 3, 12, 16, 60)], 1, 3, 9, 11)

Expected Output: (160, [101, 104])

Explanation: Flight 101 can start within the date window, and flight 104 departs exactly when flight 101 arrives, which is allowed. Total cost is 100 + 60 = 160, cheaper than the direct flight 103.

Input: ([(201, 1, 2, 5, 7, 50), (202, 1, 3, 8, 10, 200), (203, 2, 3, 8, 9, 40)], 1, 3, 6, 8)

Expected Output: (200, [202])

Explanation: Flight 201 is cheaper but cannot be the first leg because it departs before `start_date`. Therefore the only valid itinerary is the direct flight 202.

Hints

Sort flights by departure time and process them from earliest to latest.
For each airport, keep track of the cheapest itinerary that has already arrived there by the current departure time.

Quick Overview

This question evaluates proficiency in graph algorithms and constrained pathfinding, including handling date filters for initial departures, time-ordered connections, cycle avoidance, and quantitative complexity analysis.