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.

Input: ([(301, 1, 2, 1, 2, 50), (302, 2, 3, 1, 3, 40)], 1, 3, 1, 1)

Expected Output: -1

Explanation: Flight 301 is a valid first flight, but flight 302 departs before flight 301 arrives, so the connection is invalid. No direct valid route to destination exists.

Input: ([], 5, 5, 0, 10)

Expected Output: (0, [])

Explanation: If the origin and destination are the same, the empty itinerary has cost 0, even when there are no flights.

Input: ([(401, 1, 2, 1, 2, 50), (402, 2, 1, 3, 4, 10), (403, 2, 4, 3, 5, 70), (404, 1, 4, 5, 6, 40), (405, 1, 4, 2, 3, 200)], 1, 4, 1, 1)

Expected Output: (100, [401, 402, 404])

Explanation: The itinerary revisits airport 1 later in time: 401 -> 402 -> 404 costs 50 + 10 + 40 = 100. Flight 405 cannot be the first leg because its departure time is outside the allowed first-departure window.

Solution

def solution(flights, origin, destination, start_date, end_date):
    from heapq import heappush, heappop

    if origin == destination:
        return (0, [])

    if not flights:
        return -1

    # Sort flights by departure time. Each item is:
    # (departure_time, flight_id, source, destination, arrival_time, price)
    sorted_flights = sorted(
        [(flight[3], flight[0], flight[1], flight[2], flight[4], flight[5]) for flight in flights],
        key=lambda x: x[0]
    )

    n = len(sorted_flights)
    INF = float('inf')

    # parent[i] stores the previous flight index in the chosen cheapest path
    parent = [None] * n

    # Pending arrivals: (arrival_time, city, total_cost_to_reach_here, flight_index)
    arrival_heap = []

    # Best active state for each city among itineraries that have already arrived
    best_cost_by_city = {}
    best_last_by_city = {}

    answer_cost = INF
    answer_end = None

    for i, (dep, flight_id, src, dst, arr, price) in enumerate(sorted_flights):
        # Activate all arrivals that can connect to this departure
        while arrival_heap and arrival_heap[0][0] <= dep:
            arrival_time, city, cost_so_far, last_idx = heappop(arrival_heap)
            if cost_so_far < best_cost_by_city.get(city, INF):
                best_cost_by_city[city] = cost_so_far
                best_last_by_city[city] = last_idx

        best_here = INF
        prev_flight = None

        # Option 1: this flight is the first flight of the itinerary
        if src == origin and start_date <= dep <= end_date:
            best_here = price

        # Option 2: connect from the cheapest itinerary that has already arrived at src
        if src in best_cost_by_city:
            candidate = best_cost_by_city[src] + price
            if candidate < best_here:
                best_here = candidate
                prev_flight = best_last_by_city[src]

        if best_here < INF:
            parent[i] = prev_flight
            heappush(arrival_heap, (arr, dst, best_here, i))

            if dst == destination and best_here < answer_cost:
                answer_cost = best_here
                answer_end = i

    if answer_end is None:
        return -1

    path = []
    cur = answer_end
    while cur is not None:
        path.append(sorted_flights[cur][1])
        cur = parent[cur]
    path.reverse()

    return (answer_cost, path)

Time complexity: O(n log n). Space complexity: O(n).

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.