Implement a Stateful Trading Order Manager

Problem Statement

You are tasked with building the core engine for a trading order manager. The system must handle three types of operations: placing a limit order, cancelling an order, and retrieving all active orders for a specific user.

Requirements

1. Deterministic Sharding: Use the FNV-1a hash algorithm on the user_id to route requests to one of N logical shards.
2. State Machine: Orders can be OPEN, FILLED, or CANCELLED. An order can only transition from OPEN to FILLED or CANCELLED. Once in a terminal state, it cannot transition further.
3. Indexing: Maintain data structures that allow:
   • Placing an order in O(1) average time.
   • Cancelling an order by ID in O(1) average time.
   • Retrieving all OPEN orders for a specific user in O(K) time, where K is the number of open orders for that user.

Interface

class OrderManager:
    def __init__(self, num_shards: int):
        # Initialize storage for the specified number of shards

    def place_order(self, user_id: str, order_id: str, symbol: str, amount: float):
        # Store the order if it does not exist

    def cancel_order(self, user_id: str, order_id: str):
        # Transition order to CANCELLED if it exists and is OPEN

    def get_user_orders(self, user_id: str) -> List[dict]:
        # Return all orders currently in OPEN state for the given user

Constraints

• num_shards will be between 1 and 1024.
• order_id is unique system-wide.
• Total operations will be in the magnitude of 10^6.

Example

om = OrderManager(num_shards=4)
om.place_order("user1", "ordA", "BTC", 1.0)
om.place_order("user1", "ordB", "ETH", 2.0)
om.cancel_order("user1", "ordA")
# get_user_orders("user1") returns only ordB