Fractional Share Orders: Keep Brokerage Inventory Below One Share

A brokerage lets its customers buy and sell fractional shares, but the exchange trades only whole shares. To bridge the gap, the brokerage keeps a small inventory of each stock, fills fractional orders from that inventory, and trades whole shares on the exchange only when it has to. For example, suppose the brokerage holds no shares of a stock. A customer buys 1.5 shares, so the brokerage buys 2 whole shares on the exchange, delivers 1.5 and keeps 0.5. A second customer buys 0.4 shares, which come out of inventory and leave 0.1. A third customer buys 0.5 shares; inventory covers only 0.1 of them, so the brokerage buys 1 more whole share and is left with 0.6. Sales work in the other direction: if one customer sells 0.75 shares and another sells 0.5, inventory reaches 1.25, so the brokerage sells 1 whole share on the exchange and keeps 0.25. After every order, the brokerage flattens its inventory of that stock: the inventory is never negative, and it is always less than one share. Given the orders, in the order they arrive, and the brokerage's starting inventory, return its inventory of every stock after all orders have been handled. ### Function Signature ```python def final_inventory(orders: list[list[str]], inventory: list[list[str]]) -> list[list[str]]: ``` Each order is `[symbol, side, quantity, price]` and each inventory row is `[symbol, amount]`. Every number is an integer string in hundredths: its last two digits are the decimal part, so `"1000"` means 10.00, `"20"` means 0.20 and `"100"` means 1.00. ### Rules - `side` is `"B"` when the customer buys from the brokerage and `"S"` when the customer sells to it. - `price` is the current price of one share in hundredths of a dollar (cents). It is used only to convert dollar-based orders. - A `quantity` made only of digits is a number of shares in hundredths: `"42"` is 0.42 shares. - A `quantity` that starts with the character `$` is a dollar-based order: the digits after that character are a dollar amount in cents, and the order is for `amount * 100 / price` hundredths of a share (see Example 2). - Orders are handled one at a time, in list order, and each order changes only the inventory of its own `symbol`. A symbol that is not in `inventory` starts at 0. - **Buy of `q` hundredths.** If the inventory is at least `q`, the customer's shares come out of the inventory. Otherwise the brokerage first buys on the exchange the smallest number of whole shares that makes the inventory at least `q`, then delivers `q` from it. - **Sell of `q` hundredths.** `q` is added to the inventory. The brokerage then sells on the exchange as many whole shares as it can without making the inventory negative. - These rules leave every symbol's inventory between 0 and 99 hundredths, inclusive, after every order. - Return one `[symbol, amount]` row for every symbol that appears in `inventory` or in at least one order, including symbols whose final inventory is 0, sorted by `symbol` in ascending order. `amount` is the final inventory in hundredths of a share, written as a base-10 integer without leading zeros: `"8"`, not `"08"`, and `"0"` for an empty inventory. Return an empty list when both inputs are empty. ### Constraints - `0 <= len(orders) <= 10^5` - `0 <= len(inventory) <= 10^4` - Every `symbol` is 1 to 5 uppercase English letters, and a symbol appears at most once in `inventory`. Symbols are compared as plain strings, so `"AA"` sorts before `"AAPL"`, and `"AAPL"` before `"B"`. - `side` is `"B"` or `"S"`. - A share-based `quantity` is an integer from 1 to `10^7` (0.01 to 100,000 shares), written without leading zeros. - A dollar-based `quantity` is the `$` character followed by an integer amount from 1 to `10^7` cents, written without leading zeros. For every dollar-based order, `amount * 100` is divisible by `price`, so the order converts to a whole, positive number of hundredths of a share. - `price` is an integer from 1 to `10^7` cents, written without leading zeros. - Every starting `amount` in `inventory` is an integer from 0 to 99, written without leading zeros (`"0"` for zero). - Every value, including `amount * 100` for a dollar-based order and every intermediate inventory, is at most `10^9 + 99`, which fits in a 32-bit signed integer. ### Examples **Example 1** ```text Input: orders = [["AAPL", "B", "42", "100"]], inventory = [["AAPL", "99"]] Output: [["AAPL", "57"]] ``` The customer buys 0.42 shares. The inventory of 0.99 shares covers them, leaving 0.99 - 0.42 = 0.57 shares. **Example 2** ```text Input: orders = [["AAPL", "B", "$42", "100"]], inventory = [["AAPL", "50"]] Output: [["AAPL", "8"]] ``` The order is for \$0.42 at \$1.00 per share, which is `42 * 100 / 100 = 42` hundredths, or 0.42 shares. The inventory of 0.50 shares covers them, leaving 0.08 shares, written as `"8"`. **Example 3** ```text Input: orders = [["AAPL", "B", "150", "100"], ["AAPL", "B", "40", "100"], ["AAPL", "B", "50", "100"], ["TSLA", "S", "75", "200"], ["TSLA", "S", "50", "200"], ["TSLA", "B", "$300", "200"]], inventory = [["MSFT", "20"]] Output: [["AAPL", "60"], ["MSFT", "20"], ["TSLA", "75"]] ``` - AAPL starts at 0. Buying 1.50 shares needs 2 whole shares from the exchange and leaves 0.50. Buying 0.40 leaves 0.10. Buying 0.50 needs 1 more whole share and leaves 0.10 + 1.00 - 0.50 = 0.60. - TSLA starts at 0. Selling 0.75 gives 0.75. Selling 0.50 gives 1.25, so 1 whole share is sold on the exchange, leaving 0.25. The last order is for \$3.00 at \$2.00 per share, which is `300 * 100 / 200 = 150` hundredths, or 1.50 shares. The inventory covers only 0.25, so the brokerage buys 2 whole shares and keeps 0.25 + 2.00 - 1.50 = 0.75. - MSFT has no orders and stays at 0.20.