You are asked to design a simple order management system for a trading platform.
Each order is associated with an orderId, an orderType ("buy" or "sell"), and a price.
An order is considered active unless it is canceled.
Implement the OrderManagementSystem class:
OrderManagementSystem(): Initializes the order management system.void addOrder(int orderId, string orderType, int price): Adds a new active order with the given attributes. It is guaranteed that orderId is unique.void modifyOrder(int orderId, int newPrice): Modifies the price of an existing order. It is guaranteed that the order exists and is active.void cancelOrder(int orderId): Cancels an existing order. It is guaranteed that the order exists and is active.vector<int> getOrdersAtPrice(string orderType, int price): Returns the orderIds of all active orders that match the given orderType and price. If no such orders exist, return an empty list.Note: The order of returned orderIds does not matter.
Example 1:
Input:
["OrderManagementSystem", "addOrder", "addOrder", "addOrder", "getOrdersAtPrice", "modifyOrder", "modifyOrder", "getOrdersAtPrice", "cancelOrder", "cancelOrder", "getOrdersAtPrice"]
[[], [1, "buy", 1], [2, "buy", 1], [3, "sell", 2], ["buy", 1], [1, 3], [2, 1], ["buy", 1], [3], [2], ["buy", 1]]
Output:
[null, null, null, null, [2, 1], null, null, [2], null, null, []]
Explanation
OrderManagementSystem orderManagementSystem = new OrderManagementSystem();[2, 1].[2].[].
Constraints:
1 <= orderId <= 2000orderId is unique across all orders.orderType is either "buy" or "sell".1 <= price <= 109addOrder, modifyOrder, cancelOrder, and getOrdersAtPrice does not exceed 2000.modifyOrder and cancelOrder, the specified orderId is guaranteed to exist and be active.Problem Overview: Design an order management system that supports common operations such as creating orders, retrieving order information, updating status, and possibly canceling or listing orders. The system must handle frequent lookups and updates efficiently, which makes constant‑time access to orders by their ID essential.
Approach 1: Linear List Storage (Brute Force) (Time: O(n), Space: O(n))
The most straightforward design stores all orders in a simple list or array. Each operation scans the list to find the order with a matching identifier. Creating an order is O(1) by appending to the list, but retrieval, updates, or cancellation require iterating through the entire collection. This leads to O(n) time per lookup. The approach works for small datasets but quickly becomes inefficient when the number of orders grows.
Approach 2: Hash Table Index by Order ID (Time: O(1), Space: O(n))
A more practical design uses a hash table keyed by orderId. Each order is stored as a value object containing details such as status, items, or timestamps. When an operation arrives, the system performs a constant‑time hash lookup to retrieve the corresponding order. Updates simply modify the stored object, while deletions remove the key from the table. This structure makes create, read, update, and delete operations all O(1) on average, which is exactly what high‑throughput backend systems need.
Approach 3: Hash Table with Secondary Indexes (Time: O(1) average, Space: O(n))
If the system must support queries such as retrieving all orders for a user or filtering by status, a single map by order ID is not enough. The design can be extended with multiple hash tables: one mapping orderId → order, and additional indexes like userId → list of orderIds or status → set of orders. Each write operation updates all relevant indexes. Reads remain fast because the system jumps directly to the required set using a hash lookup. This pattern appears frequently in system design problems where multiple access paths are required.
Recommended for interviews: Interviewers expect the hash table design. The brute force list demonstrates baseline reasoning but fails to meet scalability expectations. A primary hash map keyed by order ID gives O(1) average complexity for core operations and reflects how real backend services implement order storage. Adding secondary indexes shows strong design thinking when the problem includes additional query requirements.
We use a hash table orders to store the type and price information of each order, where the key is the order ID and the value is a tuple (orderType, price). Additionally, we use another hash table t to store the list of order IDs corresponding to each (orderType, price), where the key is a tuple (orderType, price) and the value is the list of order IDs.
When calling \texttt{addOrder}, we add the order information to orders and append the order ID to the corresponding list in t.
When calling \texttt{modifyOrder}, we first retrieve the order type and old price from orders, then update the order's price information. Next, we remove the order ID from the corresponding list in t and add it to the list corresponding to the new price.
When calling \texttt{cancelOrder}, we retrieve the order type and price information from orders, then remove the order ID from the corresponding list in t and delete the order from orders.
When calling \texttt{getOrdersAtPrice}, we directly return the list of order IDs corresponding to the query in t.
In the above operations, the time complexity for adding and retrieving the order ID list is O(1), while the time complexity for removing an order ID from the list is O(n), where n is the length of the corresponding list. Since the total number of orders in the problem does not exceed 2000, this method is efficient enough in practice. The space complexity is O(m), where m is the total number of orders.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear List Storage | O(n) lookup | O(n) | Small datasets or initial brute‑force prototype |
| Hash Table by Order ID | O(1) average | O(n) | General case with frequent order lookups and updates |
| Hash Table with Secondary Indexes | O(1) average | O(n) | When queries require filtering by user, status, or other attributes |
Practice Design Order Management System with our built-in code editor and test cases.
Practice on FleetCode