Coding - Crypto Order System - Coinbase Interview Question | DarkInterview

Crypto Order System

CodingSoftware EngineerHigh Frequency

Problem Overview

Design a crypto trading system that manages cryptocurrency orders, supporting operations such as placing, pausing, resuming, canceling, completing, and displaying live orders.

Each order includes the following attributes:

ID: Unique order identifier (string)
Currency: The cryptocurrency being traded (e.g., "BTC", "ETH")
Amount: The amount of cryptocurrency in the order
Timestamp: The time the order was placed
Order Type: Either buy or sell
State: One of live, paused, completed, or canceled

You'll build this incrementally across multiple parts, with each part extending the previous functionality. [Source: darkinterview.com]

Part 1: Basic Order Management

Problem Statement

Implement a CryptoTradingSystem class. Every mutation method returns the order ID on success and an empty string on failure (invalid ID or invalid state transition).

class CryptoTradingSystem:
    def __init__(self):
        """Initialize the trading system."""
        pass

    def place_order(self, order_id: str, currency: str, amount: int,
                    timestamp: int, order_type: str) -> str:
        """
        Place a new order with LIVE state.

        Args:
            order_id: Unique identifier for the order
            currency: The cryptocurrency (e.g., "BTC", "ETH")
            amount: Quantity to trade
            timestamp: Time the order was placed
            order_type: "buy" or "sell"

        Returns:
            The order ID if successful, otherwise an empty string
            (e.g., if order_id already exists).
        """
        pass

    def pause_order(self, order_id: str) -> str:
        """
        Pause a LIVE order.

        Returns:
            The order ID if successful, otherwise an empty string.
            Only LIVE orders can be paused.
        """
        pass

    def resume_order(self, order_id: str) -> str:
        """
        Resume a PAUSED order.

        Returns:
            The order ID if successful, otherwise an empty string.
            Only PAUSED orders can be resumed.
        """
        pass

    def cancel_order(self, order_id: str) -> str:
        """
        Cancel an existing order that is either LIVE or PAUSED.

        Returns:
            The order ID if successful, otherwise an empty string.
            Completed and already-canceled orders cannot be canceled.
        """
        pass

    def complete_order(self, order_id: str) -> str:
        """
        Complete a LIVE order.

        Returns:
            The order ID if successful, otherwise an empty string.
            Only LIVE orders can be completed. A PAUSED order must be
            resumed before it can complete.
        """
        pass

    def display_live_orders(self) -> list:
        """
        Return the IDs of all LIVE orders, sorted by ascending timestamp.
        """
        pass

State Machine

  place_order()
       |
       v         pause_order()
     LIVE  ------------------->  PAUSED
      | ^                          |
      | |      resume_order()      |
      | +--------------------------+
      |                            |
      | complete_order()           | cancel_order()
      v                            v
  COMPLETED                    CANCELED

cancel_order() is also valid from LIVE.
COMPLETED and CANCELED are terminal states: the order stays
in the system but no further transitions are allowed.

Key transition rules interviewers probe for:

pause is only valid from LIVE; resume is only valid from PAUSED
cancel is valid from LIVE or PAUSED
complete is only valid from LIVE, so a paused order must be resumed first
Terminal orders (COMPLETED, CANCELED) reject every further operation

Example Usage

system = CryptoTradingSystem()

system.place_order("order1", "BTC", 10, 100, "buy")    # "order1"
system.place_order("order2", "ETH", 100, 90, "sell")   # "order2"
system.place_order("order3", "BTC", 5, 110, "buy")     # "order3"
system.place_order("order1", "ETH", 1, 120, "buy")     # "" (duplicate ID)

system.pause_order("order2")                            # "order2"
print(system.display_live_orders())                     # ["order1", "order3"]
# order2 is paused, so it's not live; sorted by timestamp (100 < 110)

system.complete_order("order2")                         # "" (paused, not live)
system.resume_order("order2")                           # "order2"
system.complete_order("order2")                         # "order2"

system.cancel_order("order3")                           # "order3"
system.cancel_order("order2")                           # "" (already completed)

print(system.display_live_orders())                     # ["order1"]

Part 1 Solution

from enum import Enum

class OrderState(Enum):
    LIVE = "live"
    PAUSED = "paused"
    COMPLETED = "completed"
    CANCELED = "canceled"

class Order:
    def __init__(self, order_id: str, currency: str, amount: int,
                 timestamp: int, order_type: str):
        self.order_id = order_id
        self.currency = currency
        self.amount = amount
        self.timestamp = timestamp
        self.order_type = order_type
        self.state = OrderState.LIVE

class CryptoTradingSystem:
    def __init__(self):
        self.orders = {}  # order_id -> Order

    def place_order(self, order_id: str, currency: str, amount: int,
                    timestamp: int, order_type: str) -> str:
        if order_id in self.orders:
            return ""  # Reject duplicate ID
        self.orders[order_id] = Order(order_id, currency, amount, timestamp, order_type)
        return order_id

    def pause_order() -> :
        order = .orders.get(order_id)
         order    order.state != OrderState.LIVE:
             
        order.state = OrderState.PAUSED
         order_id

     () -> :
        order = .orders.get(order_id)
         order    order.state != OrderState.PAUSED:
             
        order.state = OrderState.LIVE
         order_id

     () -> :
        order = .orders.get(order_id)
         order    order.state   (OrderState.LIVE, OrderState.PAUSED):
             
        order.state = OrderState.CANCELED
         order_id

     () -> :
        order = .orders.get(order_id)
         order    order.state != OrderState.LIVE:
             
        order.state = OrderState.COMPLETED
         order_id

     () -> :
        live = [o  o  .orders.values()  o.state == OrderState.LIVE]
        live.sort(key= o: o.timestamp)
         [o.order_id  o  live]

Design notes: [Source: darkinterview.com]

Canceled and completed orders stay in the system as terminal states rather than being deleted. This keeps them queryable and makes the state machine explicit.
display_live_orders sorts on demand: O(N log N) per call. If display is called far more often than mutations, keep live orders in a sorted container keyed by timestamp instead (e.g., a balanced BST / SortedList), making mutations O(log L) and display O(L) where L = live orders. Mentioning this trade-off is worth points.
Variant note: some interview reports have cancel physically remove the order from memory instead of marking it CANCELED. If you get that variant, the interviewer is usually probing whether you clean up all secondary indexes on deletion.

Complexity Analysis:

Method	Time	Space
`place_order`	O(1)	O(1) per order
`pause_order`	O(1)	O(1)
`resume_order`	O(1)	O(1)
`cancel_order`	O(1)	O(1)
`complete_order`	O(1)	O(1)
`display_live_orders`	O(N log N)	O(N)

Part 2: User-Level Operations

Problem Statement

Interviewer: "Now we want the system to manage orders for multiple users. Add a userId field when placing orders, and support canceling all orders associated with a specific user."

Extend the system to associate each order with a user and support bulk cancellation by user ID. [Source: darkinterview.com]

def place_order(self, order_id: str, currency: str, amount: int,
                timestamp: int, order_type: str, user_id: str) -> str:
    """Place a new LIVE order, now associated with a user."""
    pass

def cancel_all_orders(self, user_id: str) -> int:
    """
    Cancel all orders associated with the given user.

    Returns:
        The number of orders successfully canceled.

    Notes:
        - Only LIVE and PAUSED orders can be canceled; the user's
          COMPLETED and already-CANCELED orders don't count.
    """
    pass

Design Discussion Points

Additional data structure: We need a user_id -> set(order_ids) mapping so cancel_all_orders doesn't scan every order in the system
Partial cancellation: The return value counts only orders that were actually cancelable (LIVE or PAUSED), so the count can be smaller than the user's total order count
Index maintenance: Since orders are never deleted, the user index only grows on place_order; if you're implementing the deletion variant, cancel must also clean up the user index

Part 2 Solution

from enum import Enum
from collections import defaultdict

class OrderState(Enum):
    LIVE = "live"
    PAUSED = "paused"
    COMPLETED = "completed"
    CANCELED = "canceled"

class Order:
    def __init__(self, order_id: str, currency: str, amount: int,
                 timestamp: int, order_type: str, user_id: str):
        self.order_id = order_id
        self.currency = currency
        self.amount = amount
        self.timestamp = timestamp
        self.order_type = order_type
        self.user_id = user_id
        self.state = OrderState.LIVE

class CryptoTradingSystem:
    def __init__(self):
        self.orders = {}                     # order_id -> Order
        self.user_orders = defaultdict(set)  # user_id -> set of order_ids

    def place_order(self, order_id: str, currency: str, amount: int,
                    timestamp: int, order_type: str, user_id: str) -> str:
        if order_id in self.orders:
             
        order = Order(order_id, currency, amount, timestamp, order_type, user_id)
        .orders[order_id] = order
        .user_orders[user_id].add(order_id)
         order_id

     () -> :
        order = .orders.get(order_id)
         order    order.state != OrderState.LIVE:
             
        order.state = OrderState.PAUSED
         order_id

     () -> :
        order = .orders.get(order_id)
         order    order.state != OrderState.PAUSED:
             
        order.state = OrderState.LIVE
         order_id

     () -> :
        order = .orders.get(order_id)
         order    order.state   (OrderState.LIVE, OrderState.PAUSED):
             
        order.state = OrderState.CANCELED
         order_id

     () -> :
        order = .orders.get(order_id)
         order    order.state != OrderState.LIVE:
             
        order.state = OrderState.COMPLETED
         order_id

     () -> :
        count = 
         order_id  .user_orders.get(user_id, ()):
            order = .orders[order_id]
             order.state  (OrderState.LIVE, OrderState.PAUSED):
                order.state = OrderState.CANCELED
                count += 
         count

     () -> :
        live = [o  o  .orders.values()  o.state == OrderState.LIVE]
        live.sort(key= o: o.timestamp)
         [o.order_id  o  live]

Key point: cancel_all_orders reuses the same state-transition rule as cancel_order (only LIVE or PAUSED orders are cancelable) and counts only successful cancellations. Interviewers often check this by seeding the user with a completed order first.

Complexity Analysis:

Method	Time	Space
`place_order`	O(1)	O(1) per order
`cancel_order`	O(1)	O(1)
`cancel_all_orders`	O(K)	O(1)

Where K = number of orders belonging to the user. [Source: darkinterview.com]

Part 3: Sharding by User ID

Problem Statement

Interviewer: "As the number of users grows, handling all orders in a single data stream is no longer feasible. Partition the data into n separate streams. All orders belonging to the same user must remain within the same stream."

Modify the system to distribute orders across n streams using user-based sharding, while maintaining all functionality from the previous parts:

class CryptoTradingSystem:
    def __init__(self, n: int):
        """
        Initialize the trading system with the given number of data streams.

        Notes:
            - Use hash(user_id) % n to determine which stream
              a user's orders belong to
            - All orders from the same user must be in the same stream
        """
        pass

Requirements

Consistent sharding: hash(user_id) % n determines the target stream
All operations must route to the correct stream
display_live_orders now returns live orders from all streams, merged and still sorted by ascending timestamp
Same user, same stream: Guarantees ordering consistency for per-user operations

Design Discussion Points

Why shard by user? Ensures all of a user's orders are co-located, making cancel_all_orders efficient (only touches one stream)
Hash function choice: Python's built-in hash() works for demonstration; in production, use consistent hashing
Stream independence: Each stream can be processed by a different worker/thread in a distributed system
Rebalancing: What happens if you change n? (Consistent hashing discussion)

Part 3 Solution

from enum import Enum
from collections import defaultdict

class OrderState(Enum):
    LIVE = "live"
    PAUSED = "paused"
    COMPLETED = "completed"
    CANCELED = "canceled"

class Order:
    def __init__(self, order_id: str, currency: str, amount: int,
                 timestamp: int, order_type: str, user_id: str):
        self.order_id = order_id
        self.currency = currency
        self.amount = amount
        self.timestamp = timestamp
        self.order_type = order_type
        self.user_id = user_id
        self.state = OrderState.LIVE

class Stream:
    """A single shard that manages a subset of orders."""
    def __init__(self):
        self.orders = {}                     # order_id -> Order
        self.user_orders = defaultdict(set)  # user_id -> set of order_ids

    def place(self, order: Order) -> str:
        if order.order_id in self.orders:
            return ""
        self.orders[order.order_id] = order
        .user_orders[order.user_id].add(order.order_id)
         order.order_id

     () -> :
        order = .orders.get(order_id)
         order    order.state   from_states:
             
        order.state = to_state
         order_id

     () -> :
         ._transition(order_id, (OrderState.LIVE,), OrderState.PAUSED)

     () -> :
         ._transition(order_id, (OrderState.PAUSED,), OrderState.LIVE)

     () -> :
         ._transition(order_id, (OrderState.LIVE, OrderState.PAUSED),
                                OrderState.CANCELED)

     () -> :
         ._transition(order_id, (OrderState.LIVE,), OrderState.COMPLETED)

     () -> :
        count = 
         order_id  .user_orders.get(user_id, ()):
            order = .orders[order_id]
             order.state  (OrderState.LIVE, OrderState.PAUSED):
                order.state = OrderState.CANCELED
                count += 
         count

     () -> :
         [o  o  .orders.values()  o.state == OrderState.LIVE]


 :
     ():
        .n = n
        .streams = [Stream()  _  (n)]
        .order_to_stream = {}  

     () -> :
        
         (user_id) % .n

     () -> :
         order_id  .order_to_stream:
               
        stream_idx = ._stream_for_user(user_id)
        order = Order(order_id, currency, amount, timestamp, order_type, user_id)
        result = .streams[stream_idx].place(order)
         result:
            .order_to_stream[order_id] = stream_idx
         result

     () -> :
        stream_idx = .order_to_stream.get(order_id)
         stream_idx  :
             
         .streams[stream_idx].pause(order_id)

     () -> :
        stream_idx = .order_to_stream.get(order_id)
         stream_idx  :
             
         .streams[stream_idx].resume(order_id)

     () -> :
        stream_idx = .order_to_stream.get(order_id)
         stream_idx  :
             
         .streams[stream_idx].cancel(order_id)

     () -> :
        stream_idx = .order_to_stream.get(order_id)
         stream_idx  :
             
         .streams[stream_idx].complete(order_id)

     () -> :
        stream_idx = ._stream_for_user(user_id)
         .streams[stream_idx].cancel_all_orders(user_id)

     () -> :
        
        live = []
         stream  .streams:
            live.extend(stream.get_live_orders())
        live.sort(key= o: o.timestamp)
         [o.order_id  o  live]

Example Usage

system = CryptoTradingSystem(n=3)

# "alice" and "bob" may land on different streams
system.place_order("order1", "BTC", 10, 100, "buy", "alice")
system.place_order("order2", "ETH", 100, 90, "sell", "alice")
system.place_order("order3", "BTC", 5, 110, "buy", "bob")
system.place_order("order4", "ETH", 50, 95, "sell", "bob")

system.pause_order("order2")

print(system.display_live_orders())
# ["order4", "order1", "order3"] (globally sorted by timestamp: 95, 100, 110)

# Cancel all of alice's orders; only touches one stream
canceled = system.cancel_all_orders("alice")
print(f"Canceled {canceled} orders")  # 2 (order1 live, order2 paused)

print(system.display_live_orders())
# ["order4", "order3"] (only bob's orders remain live)

Why this design works: [Source: darkinterview.com]

Same user, same stream: hash(user_id) % n guarantees co-location
Efficient per-user ops: cancel_all_orders only touches one stream
Parallel processing: Each stream can be handled by a separate worker/thread
Order-level routing: The order_to_stream map lets us route pause/resume/cancel/complete by order ID without knowing the user

Follow-Up Discussion Topics

Discussed in Interviews

Sharding strategy: Why hash(user_id) % n and not hash(order_id) % n?
- User-based sharding keeps all user orders together
- Makes cancel_all_orders a single-stream operation
- Trade-off: potential hot spots if one user has many orders
Consistent hashing: What happens when you add or remove streams?
- Simple modulo requires reshuffling all data
- Consistent hashing minimizes data movement
- Virtual nodes for better load distribution
Efficient display: If display_live_orders is hot, how do you avoid re-sorting? [Source: darkinterview.com]
- Keep each stream's live orders in a sorted container keyed by timestamp
- Merge the n sorted streams with a min-heap: O(L log n) instead of O(L log L)
- Trade-off: mutations become O(log L) instead of O(1)
Out-of-order events: What if events arrive with out-of-order timestamps?
- Buffer events and process in timestamp order
- Time-windowed processing (e.g., process all events in 5-second windows)
- Queue-based solution with a priority queue sorted by timestamp
Thread safety: If each stream is processed by a separate worker, what synchronization is needed?
- Per-stream locks (not a global lock)
- The order_to_stream lookup needs concurrent access protection

Complexity Summary

Implementation	place	pause/resume/cancel/complete	cancel_all_orders	display_live_orders
Single stream	O(1)	O(1)	O(K)	O(N log N)
Sharded (n streams)	O(1)	O(1)	O(K)	O(N log N)

Where N = total orders, K = orders per user, n = number of streams. [Source: darkinterview.com]

Space complexity: O(N) for orders + O(U) for the user index, where U = number of users.