PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates competence in deterministic resource allocation, stateful simulation, and capacity-management under time constraints, exercising algorithmic reasoning and data-structure handling within the Coding & Algorithms domain.

  • hard
  • Optiver
  • Coding & Algorithms
  • Software Engineer

Cargo Order Allocation Across Departing Planes

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

A freight company assigns incoming shipping orders to a fixed fleet of cargo planes. You must implement the order-processing logic: decide whether each order can be accepted, and if so, allocate its cargo across planes and update the fleet's remaining capacity. You are given `planes`, where `planes[i] = [departure_i, capacity_i]`: plane `i` departs at time `departure_i` and can carry at most `capacity_i` units of cargo. Each plane's departure time and capacity are fixed; its remaining capacity only decreases as cargo is assigned to it and never resets. Orders arrive as a sequence and must be processed strictly in the given order. `orders[j] = [time_j, items_j]`, where `time_j` is the time the order is placed and `items_j` is a non-empty list of positive integers — the sizes of the cargo pieces in the order. Let `total_j` be the sum of `items_j`. **Rules** 1. **Eligibility:** cargo from order `j` may only be loaded onto planes that depart **strictly after** `time_j` (a plane with `departure_i > time_j`). 2. **Splitting:** cargo is divisible — an order's cargo may be split across multiple eligible planes in integer units. Individual piece boundaries do not restrict the split; only the order's total size `total_j` matters for allocation. 3. **Acceptance:** order `j` is accepted if and only if, at the moment it is processed, the sum of the remaining capacities of all eligible planes is at least `total_j`. 4. **All-or-nothing:** if an order is rejected, no plane's remaining capacity changes. A rejected order is never retried. 5. **Allocation policy (deterministic):** when an order is accepted, fill eligible planes in ascending order of departure time, breaking ties by ascending plane index. Assign to each such plane `min(remaining cargo to place, plane's remaining capacity)` units, skipping planes whose remaining capacity is `0`, until the full `total_j` units are placed. Then commit the capacity updates. **Output** Return an array `result` with one element per order, in input order: - If order `j` is **rejected**, `result[j]` is an empty array `[]`. - If order `j` is **accepted**, `result[j]` is an array of `[i, amount]` pairs — plane index and the number of units assigned to that plane — listed in the order the planes were filled, including only planes that received `amount > 0`. **Example** ``` planes = [[5, 10], [10, 8], [3, 6]] orders = [[2, [4, 5]], [4, [12]], [6, [9]], [0, [30]]] ``` - Order 0 (time 2, total 9): eligible planes (departure > 2) are 0, 1, 2. Fill by ascending departure: plane 2 (departs 3) takes 6, plane 0 (departs 5) takes 3. Result: `[[2, 6], [0, 3]]`. Remaining capacities: plane 0 → 7, plane 1 → 8, plane 2 → 0. - Order 1 (time 4, total 12): eligible planes are 0 (7 left) and 1 (8 left); 7 + 8 = 15 ≥ 12, accepted. Plane 0 takes 7, plane 1 takes 5. Result: `[[0, 7], [1, 5]]`. Remaining: plane 0 → 0, plane 1 → 3. - Order 2 (time 6, total 9): only plane 1 is eligible (departs 10) with 3 left; 3 < 9, rejected. Result: `[]`. State unchanged. - Order 3 (time 0, total 30): all planes eligible, remaining sum is 0 + 3 + 0 = 3 < 30, rejected. Result: `[]`. ``` result = [[[2, 6], [0, 3]], [[0, 7], [1, 5]], [], []] ``` **Constraints** - `1 <= planes.length <= 2 * 10^5` - `1 <= orders.length <= 2 * 10^5` - The total number of cargo pieces across all orders is at most `4 * 10^5`. - `0 <= departure_i, time_j <= 10^9` - `1 <= capacity_i <= 10^9`; each cargo piece size is between `1` and `10^9`. - All capacity and cargo sums fit in a signed 64-bit integer. - Orders must be processed in the given sequence; each order's acceptance decision uses the fleet state left by all previous orders. A solution that re-scans and re-sorts the whole fleet for every order will be too slow for the largest inputs; aim for roughly `O((n + m) log n)` overall, where `n` is the number of planes and `m` is the number of orders.

Quick Answer: This question evaluates competence in deterministic resource allocation, stateful simulation, and capacity-management under time constraints, exercising algorithmic reasoning and data-structure handling within the Coding & Algorithms domain.

A freight company assigns incoming shipping orders to a fixed fleet of cargo planes. Implement the order-processing logic: decide whether each order can be accepted and, if so, allocate its cargo across planes and update remaining capacity. You are given `planes`, where `planes[i] = [departure_i, capacity_i]`: plane `i` departs at time `departure_i` and can carry at most `capacity_i` units of cargo. A plane's departure time and capacity are fixed; its remaining capacity only decreases as cargo is assigned and never resets. Orders are processed strictly in the given order. For order `j`, `order_times[j]` is the time it is placed and `order_items[j]` is a non-empty list of positive integers — the sizes of the cargo pieces. Let `total_j` be the sum of `order_items[j]`. Implement `solution(planes, order_times, order_items)` and return `result`, one entry per order. **Rules** 1. **Eligibility:** cargo from order `j` may only be loaded onto planes that depart **strictly after** `order_times[j]` (a plane with `departure_i > order_times[j]`). 2. **Splitting:** cargo is divisible — an order's cargo may be split across multiple eligible planes in integer units. Piece boundaries do not restrict the split; only the total `total_j` matters. 3. **Acceptance:** order `j` is accepted iff, at the moment it is processed, the sum of the remaining capacities of all eligible planes is at least `total_j`. 4. **All-or-nothing:** if an order is rejected, no plane's remaining capacity changes. A rejected order is never retried. 5. **Allocation policy (deterministic):** when an order is accepted, fill eligible planes in ascending order of departure time, breaking ties by ascending plane index. Assign each such plane `min(remaining cargo to place, plane's remaining capacity)` units, skipping planes whose remaining capacity is `0`, until all `total_j` units are placed. Then commit the updates. **Output** - If order `j` is **rejected**, `result[j]` is an empty array `[]`. - If order `j` is **accepted**, `result[j]` is an array of `[i, amount]` pairs — plane index and units assigned — in the order planes were filled, including only planes that received `amount > 0`. **Example** ``` planes = [[5, 10], [10, 8], [3, 6]] order_times = [2, 4, 6, 0] order_items = [[4, 5], [12], [9], [30]] ``` - Order 0 (time 2, total 9): eligible planes 0, 1, 2. Fill by ascending departure: plane 2 (departs 3) takes 6, plane 0 (departs 5) takes 3 -> `[[2, 6], [0, 3]]`. Remaining: 7, 8, 0. - Order 1 (time 4, total 12): eligible 0 (7) and 1 (8); 15 >= 12, accepted. Plane 0 takes 7, plane 1 takes 5 -> `[[0, 7], [1, 5]]`. Remaining: 0, 3, 0. - Order 2 (time 6, total 9): only plane 1 eligible with 3 left; 3 < 9, rejected -> `[]`. - Order 3 (time 0, total 30): remaining sum 0 + 3 + 0 = 3 < 30, rejected -> `[]`. ``` result = [[[2, 6], [0, 3]], [[0, 7], [1, 5]], [], []] ``` **Constraints** - `1 <= planes.length <= 2 * 10^5` - `1 <= order_times.length == order_items.length <= 2 * 10^5` - Total cargo pieces across all orders <= `4 * 10^5`. - `0 <= departure_i, time_j <= 10^9`; `1 <= capacity_i <= 10^9`; each piece size in `[1, 10^9]`. - All capacity and cargo sums fit in a signed 64-bit integer. - A solution that re-sorts the whole fleet per order is too slow; aim for roughly `O((n + m) log n)`.

Constraints

  • 1 <= planes.length <= 2 * 10^5
  • 1 <= order_times.length == order_items.length <= 2 * 10^5
  • Total cargo pieces across all orders <= 4 * 10^5
  • 0 <= departure_i, time_j <= 10^9
  • 1 <= capacity_i <= 10^9 and each cargo piece size is in [1, 10^9]
  • All capacity and cargo sums fit in a signed 64-bit integer
  • Orders are processed strictly in input order; each decision uses the state left by prior orders

Examples

Input: ([[5, 10], [10, 8], [3, 6]], [2, 4, 6, 0], [[4, 5], [12], [9], [30]])

Expected Output: [[[2, 6], [0, 3]], [[0, 7], [1, 5]], [], []]

Explanation: The worked example. Order 0 fills plane 2 (departs 3) then plane 0 (departs 5). Order 1 exhausts plane 0 then partially fills plane 1. Order 2 and order 3 lack enough eligible remaining capacity and are rejected, leaving state unchanged.

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

Expected Output: [[[0, 10]]]

Explanation: Single plane departs at 5 > 3, so it is eligible with 10 units. The order total is exactly 10, so it is accepted and fully loaded onto plane 0.

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

Expected Output: [[]]

Explanation: Boundary case: the plane departs at time 5 and the order is placed at time 5. Eligibility requires departure strictly greater than the order time, so no plane is eligible and the order is rejected.

Input: ([[10, 5], [20, 5]], [0, 0, 15], [[6], [4], [3]])

Expected Output: [[[0, 5], [1, 1]], [[1, 4]], []]

Explanation: Stateful sequence. Order 0 (total 6) fills plane 0 fully (5) then plane 1 (1), leaving remaining [0, 4]. Order 1 (total 4) skips the now-empty plane 0 and takes 4 from plane 1, leaving [0, 0]. Order 2 (time 15) only sees plane 1 (departs 20) which has 0 left, so it is rejected.

Input: ([[5, 3], [5, 3]], [0], [[4]])

Expected Output: [[[0, 3], [1, 1]]]

Explanation: Both planes share departure time 5, so the tie is broken by ascending index: plane 0 is filled first (3 units), then plane 1 takes the remaining 1 unit.

Input: ([[100, 50]], [10], [[10, 20, 25]])

Expected Output: [[]]

Explanation: The single eligible plane has capacity 50, but the order's pieces sum to 10 + 20 + 25 = 55 > 50, so the order is rejected and no capacity changes.

Hints

  1. Eligibility, acceptance, and the fill order all key off departure time, so pre-sort plane indices once by (departure, index). Within an order, eligible planes are exactly the suffix of that sorted order whose departure is strictly greater than the order's time — find its start with a binary search.
  2. Acceptance is purely a capacity-sum test over that eligible suffix, and it is the SAME suffix you then fill. Accept iff the summed remaining capacity of the suffix is at least the order total; only mutate capacities after you have confirmed acceptance (all-or-nothing).
  3. Fill greedily along the suffix in (departure, index) order, giving each plane min(remaining_to_place, plane_capacity) and skipping planes already at 0. To beat the O(n) per-order scan at scale, maintain remaining capacity in a Fenwick/segment tree over departure rank so both the suffix sum and the walk to the next non-empty plane are O(log n).
Last updated: Jul 2, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Maintain Price Levels For A Single-Symbol Order Book - Optiver (medium)
  • Build and Validate a Binary Tree from Parent-Child Pairs - Optiver (medium)
  • Days Between Two Calendar Dates - Optiver (medium)
  • Thread-Safe Stock Inventory: Buy and Sell Without Overselling - Optiver (medium)
  • Implement a Level-Aware Expiring Inventory Store - Optiver (medium)