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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Optiver.

What role is this question designed for?

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

Optimize flight and cargo bookings for profit

Quick Overview

This question evaluates resource allocation, combinatorial optimization, and online/streaming algorithm design within the Coding & Algorithms domain, requiring reasoning about assigning weight‑constrained cargo to flights under timing and cost constraints; it is commonly asked to assess algorithmic thinking about trade-offs between revenue and booking cost, constraint satisfaction, and handling dynamic inputs. The problem tests both conceptual understanding of optimization and online decision‑making and practical application skills for implementing incremental processing and robust handling of failed bookings.

Optimize flight and cargo bookings for profit

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## OptiCargo: make the booking algorithm profitable You are given two streams/lists: - **Flights** you may attempt to book. Each flight has: - `flight_id` - `depart_time` and `arrive_time` - `max_weight` (capacity) - `cost` (paid only if you successfully book the flight) - **Cargo jobs** you may book. Each cargo has: - `cargo_id` - `weight` - `latest_arrival_time` (deadline) - `revenue` (earned if delivered by the deadline) A cargo job can be assigned to **at most one** booked flight. A flight can carry multiple cargo jobs as long as total assigned weight ≤ `max_weight`. A cargo job is deliverable on a flight if `arrive_time ≤ latest_arrival_time`. ### Task A (batch / fix existing code) The existing implementation is unprofitable because it books **all** flights regardless of whether there is profitable cargo to carry. Design/implement changes so that the algorithm chooses which flights to book and which cargo to assign to maximize **total profit**: \[ \text{profit} = \sum(\text{revenue of delivered cargo}) - \sum(\text{cost of booked flights}) \] You may output either: - the maximum profit value, or - the set of booked flights and cargo-to-flight assignments. ### Task B (incremental / streaming class) Implement a class that processes events as they arrive: - `onFlight(flight)` adds a new available flight. - `onCargo(cargo)` adds a new available cargo job. - Optionally, `decide()` (or similar) updates the plan. At any time, the class should be able to report the current planned profit and/or current bookings/assignments. ### Realism constraint (booking may fail) When you “apply” to book a flight, the booking can fail (e.g., another party booked it first). Your design should handle failed bookings gracefully (e.g., retry, re-plan, or treat it as removed from availability).

Quick Answer: This question evaluates resource allocation, combinatorial optimization, and online/streaming algorithm design within the Coding & Algorithms domain, requiring reasoning about assigning weight‑constrained cargo to flights under timing and cost constraints; it is commonly asked to assess algorithmic thinking about trade-offs between revenue and booking cost, constraint satisfaction, and handling dynamic inputs. The problem tests both conceptual understanding of optimization and online decision‑making and practical application skills for implementing incremental processing and robust handling of failed bookings.

Part 1: Maximize Opticargo profit for a fixed set of flights and cargo

You are given all candidate flights and cargo orders upfront. Each flight is a dedicated shipment slot: if you book it, it can carry at most one cargo order. In this simplified model, delivery is instantaneous, so a cargo can use a flight if and only if the flight's departure_time is less than or equal to the cargo's latest_arrival and the flight's max_weight is at least the cargo's weight. If cargo j is assigned to flight i, the profit contributed by that pair is revenue_j - cost_i. You may skip any flight or cargo, and you should never take a loss-making booking if skipping is better. Return the maximum total profit.

Loading coding console...

Examples

Input: ([(1, 10, 100), (3, 5, 30)], [(4, 3, 90), (5, 1, 120), (6, 5, 140)])

Expected Output: 100

Explanation: Assign cargo (4, 3, 90) to flight (3, 5, 30) for profit 60, and cargo (6, 5, 140) to flight (1, 10, 100) for profit 40. Total profit is 100.

Input: ([(2, 3, 50)], [(4, 5, 100), (3, 1, 100)])

Expected Output: 0

Explanation: One cargo is too heavy and the other misses the time constraint, so no profitable shipment is possible.

Input: ([(1, 5, 70), (2, 5, 10)], [(5, 2, 60), (5, 2, 50)])

Expected Output: 50

Explanation: The first flight loses money on every feasible cargo, so only the second flight should be used.

Input: ([(2, 10, 20), (1, 5, 5)], [(5, 2, 40), (10, 2, 50)])

Expected Output: 65

Explanation: Best is to use both flights: profit 35 from matching the smaller flight with the 5-weight cargo, and profit 30 from matching the larger flight with the 10-weight cargo.

Input: ([], [(1, 1, 10)])

Expected Output: 0

Explanation: No flights means no shipments.

Solution

def solution(flights, cargos):
    n_f = len(flights)
    n_c = len(cargos)
    n = max(n_f, n_c)
    if n == 0:
        return 0

    profit = [[0] * n for _ in range(n)]
    max_cell = 0

    for i, (depart, max_weight, cost) in enumerate(flights):
        for j, (weight, latest_arrival, revenue) in enumerate(cargos):
            if depart <= latest_arrival and max_weight >= weight:
                value = revenue - cost
                if value > 0:
                    profit[i][j] = value
                    if value > max_cell:
                        max_cell = value

    cost_matrix = [[max_cell - profit[i][j] for j in range(n)] for i in range(n)]

    u = [0] * (n + 1)
    v = [0] * (n + 1)
    p = [0] * (n + 1)
    way = [0] * (n + 1)

    for i in range(1, n + 1):
        p[0] = i
        j0 = 0
        minv = [float('inf')] * (n + 1)
        used = [False] * (n + 1)

        while True:
            used[j0] = True
            i0 = p[j0]
            delta = float('inf')
            j1 = 0

            for j in range(1, n + 1):
                if not used[j]:
                    cur = cost_matrix[i0 - 1][j - 1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur
                        way[j] = j0
                    if minv[j] < delta:
                        delta = minv[j]
                        j1 = j

            for j in range(n + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta

            j0 = j1
            if p[j0] == 0:
                break

        while True:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
            if j0 == 0:
                break

    assignment = [-1] * n
    for j in range(1, n + 1):
        if p[j] != 0:
            assignment[p[j] - 1] = j - 1

    answer = 0
    for i in range(n_f):
        j = assignment[i]
        if 0 <= j < n_c:
            answer += profit[i][j]
    return answer

Time complexity: O(F * C + N^3), where F = len(flights), C = len(cargos), and N = max(F, C). Space complexity: O(N^2).

Part 2: Streaming Opticargo planner with updates and profit queries

Now flights and cargo orders arrive over time. Implement a streaming planner that supports updates and answers the current maximum profit after each query. Use the same shipment model as Part 1: each active flight can carry at most one active cargo, a cargo can use a flight only if departure_time <= latest_arrival and max_weight >= weight, and the profit of matching a cargo to a flight is revenue - cost. For this platform, implement a function that processes operations and returns the answer for every QUERY operation. Re-adding an existing id replaces the previous active record with that id. Removing a non-existent id should do nothing.

Constraints

0 <= len(operations) <= 200
At any QUERY, the number of active flights and active cargos is at most 60 each
1 <= departure_time, latest_arrival, max_weight, weight, cost, revenue <= 10^9
flight_id and cargo_id are strings
Re-adding an existing id replaces the previous active item

Examples

Input: [('ADD_FLIGHT', 'F1', 1, 10, 100), ('ADD_CARGO', 'C1', 4, 3, 90), ('QUERY',), ('ADD_CARGO', 'C2', 6, 5, 140), ('QUERY',), ('ADD_FLIGHT', 'F2', 3, 5, 30), ('QUERY',)]

Expected Output: [0, 40, 100]

Explanation: With only F1 and C1, shipping loses money so the best profit is 0. After adding C2, F1 can profitably ship it for 40. After adding F2, the best matching becomes 100.

Input: [('ADD_FLIGHT', 'F1', 1, 5, 5), ('ADD_FLIGHT', 'F2', 2, 10, 20), ('ADD_CARGO', 'C1', 5, 2, 40), ('ADD_CARGO', 'C2', 10, 2, 50), ('QUERY',), ('REMOVE_CARGO', 'C2'), ('QUERY',), ('REMOVE_FLIGHT', 'F1'), ('QUERY',)]

Expected Output: [65, 35, 20]

Explanation: The best matching first uses both flights. After removing C2, only C1 remains and F1 is the better choice. After removing F1, only F2 can ship C1.

Input: [('QUERY',)]

Expected Output: [0]

Explanation: Querying an empty system should return 0.

Input: [('ADD_FLIGHT', 'F1', 5, 5, 10), ('ADD_CARGO', 'C1', 5, 4, 100), ('QUERY',), ('ADD_FLIGHT', 'F1', 3, 5, 10), ('QUERY',), ('REMOVE_CARGO', 'NOPE'), ('REMOVE_FLIGHT', 'F1'), ('QUERY',)]

Expected Output: [0, 90, 0]

Explanation: The first version of F1 is too late for C1, then re-adding F1 replaces it with a feasible version. Removing a non-existent cargo is ignored.

Solution

def solution(operations):
    def max_profit(flights, cargos):
        n_f = len(flights)
        n_c = len(cargos)
        n = max(n_f, n_c)
        if n == 0:
            return 0

        profit = [[0] * n for _ in range(n)]
        max_cell = 0

        for i, (depart, max_weight, cost) in enumerate(flights):
            for j, (weight, latest_arrival, revenue) in enumerate(cargos):
                if depart <= latest_arrival and max_weight >= weight:
                    value = revenue - cost
                    if value > 0:
                        profit[i][j] = value
                        if value > max_cell:
                            max_cell = value

        cost_matrix = [[max_cell - profit[i][j] for j in range(n)] for i in range(n)]

        u = [0] * (n + 1)
        v = [0] * (n + 1)
        p = [0] * (n + 1)
        way = [0] * (n + 1)

        for i in range(1, n + 1):
            p[0] = i
            j0 = 0
            minv = [float('inf')] * (n + 1)
            used = [False] * (n + 1)

            while True:
                used[j0] = True
                i0 = p[j0]
                delta = float('inf')
                j1 = 0

                for j in range(1, n + 1):
                    if not used[j]:
                        cur = cost_matrix[i0 - 1][j - 1] - u[i0] - v[j]
                        if cur < minv[j]:
                            minv[j] = cur
                            way[j] = j0
                        if minv[j] < delta:
                            delta = minv[j]
                            j1 = j

                for j in range(n + 1):
                    if used[j]:
                        u[p[j]] += delta
                        v[j] -= delta
                    else:
                        minv[j] -= delta

                j0 = j1
                if p[j0] == 0:
                    break

            while True:
                j1 = way[j0]
                p[j0] = p[j1]
                j0 = j1
                if j0 == 0:
                    break

        assignment = [-1] * n
        for j in range(1, n + 1):
            if p[j] != 0:
                assignment[p[j] - 1] = j - 1

        answer = 0
        for i in range(n_f):
            j = assignment[i]
            if 0 <= j < n_c:
                answer += profit[i][j]
        return answer

    active_flights = {}
    active_cargos = {}
    answers = []

    for op in operations:
        kind = op[0]
        if kind == 'ADD_FLIGHT':
            _, flight_id, depart, max_weight, cost = op
            active_flights[flight_id] = (depart, max_weight, cost)
        elif kind == 'ADD_CARGO':
            _, cargo_id, weight, latest_arrival, revenue = op
            active_cargos[cargo_id] = (weight, latest_arrival, revenue)
        elif kind == 'REMOVE_FLIGHT':
            _, flight_id = op
            active_flights.pop(flight_id, None)
        elif kind == 'REMOVE_CARGO':
            _, cargo_id = op
            active_cargos.pop(cargo_id, None)
        elif kind == 'QUERY':
            answers.append(max_profit(list(active_flights.values()), list(active_cargos.values())))
        else:
            raise ValueError('Unknown operation: ' + str(kind))

    return answers

Time complexity: O(Q * (A^3 + F * C)) in the worst case, where Q is the number of QUERY operations, A is max(active flights, active cargos) at that query, and F and C are the active counts. Space complexity: O(A^2).

Hints

Keep the currently active flights and cargos in dictionaries keyed by id.
Because the active set is small, you can recompute the best offline matching from scratch on every QUERY.