Average Stock Holding Time
You are given a transaction log for a single stock. The log is a list of (quantity, time) tuples, where a positive quantity means a buy and a negative quantity means a sell. The net position starts at zero and ends at zero.
Design and implement an algorithm to compute the average holding time per share. Assume FIFO accounting: the first shares bought are the first shares sold.
Constraints: -
Examples:
Example 1: ``` log = [(10, 0), (-5, 3), (-5, 7)] ``` FIFO matching: first 5 shares held 3 days, next 5 shares held 7 days. Average holding time = $(5 \times 3 + 5 \times 7) / 10 = 50/10 = 5.0$
Example 2: ``` log = [(3, 0), (2, 1), (-4, 5), (-1, 6)] ``` FIFO: sell 4 at time 5 matches 3 shares from time 0 (held 5 days) and 1 share from time 1 (held 4 days). Sell 1 at time 6 matches 1 share from time 1 (held 5 days). Total share-days = $3 \times 5 + 1 \times 4 + 1 \times 5 = 15 + 4 + 5 = 24$. Total shares = 5. Average =
Hints
- Think of each buy as adding a lot to a queue and each sell as draining from the front of that queue. The holding time for each share is the sell time minus its buy time.
- You do not need to store one entry per share -- store lots as
(remaining_quantity, time)tuples and partially drain them. This keeps the queue size bounded by the number of buy events. - For each matched block of
mshares between a buy at time $t_b$ and a sell at time $t_s$, add $m \times (t_s - t_b)$ to a running total, then divide by total shares sold at the end.
Worked Solution
How to Think About It: This is a queue matching problem. Each buy adds shares to a FIFO queue tagged with their buy time. Each sell pops shares from the front of the queue and computes holding time = sell time minus buy time. Shares from a single buy lot may be split across multiple sells, so partial consumption of queue entries must be handled. Once you see it as FIFO queue draining, the implementation is straightforward.
Brute force (storing every individual share as a queue entry) works but is wasteful if lots are large. The efficient approach stores lots as (remaining_quantity, buy_time) tuples and partially drains them.
Algorithm: 1. Initialize a deque buy_queue (FIFO), total_share_days = 0, total_shares = 0. 2. For each (qty, time) in the log: - If qty > 0 (buy): append (qty, time) to the back of the queue. - If qty < 0 (sell): set sell_qty = -qty. While sell_qty > 0, pop from the front of the queue, match as many shares as possible, accumulate matched * (sell_time - buy_time) into total_share_days, subtract matched from sell_qty. If the front lot is not fully consumed, update it in place. 3. Return total_share_days / total_shares.
Code: ```python from collections import deque
def avg_holding_time(log): buy_queue = deque() # entries: (remaining_qty, buy_time) total_share_days = 0 total_shares = 0
for qty, time in log: if qty > 0: buy_queue.append([qty, time]) else: sell_qty = -qty while sell_qty > 0 and buy_queue: lot_qty, lot_time = buy_queue[0] matched = min(lot_qty, sell_qty) total_share_days += matched * (time - lot_time) total_shares += matched sell_qty -= matched buy_queue[0][0] -= matched if buy_queue[0][0] == 0: buy_queue.popleft()
return total_share_days / total_shares if total_shares > 0 else 0.0 ```
Complexity: - Time: $O(n)$ -- each log entry is processed once. Each share is matched exactly once (one buy event, one sell event), so the total work across all queue pops is $O(n)$. - Space: $O(n)$ for the queue in the worst case (all buys before all sells).
Answer: FIFO queue matching in $O(n)$ time and $O(n)$ space. The key insight is that each share is touched at most twice -- once on the buy and once on the sell -- so the total work is linear in the number of log entries, not in the number of shares.
Intuition
FIFO matching is the standard accounting convention for computing cost basis and holding periods, and it shows up in practice everywhere from P&L attribution to tax lot tracking. The algorithmic pattern -- a queue that is partially drained by successive operations -- appears in many contexts: order book matching, inventory accounting, and streaming data problems where you process items in arrival order.
The subtlety most candidates miss is the partial lot case: a sell of 7 shares might consume 5 shares from one buy lot and 2 from the next. Handling this correctly with in-place updates to the queue front (rather than popping and re-pushing) is what keeps the solution $O(n)$. If you instead pop, split, and re-push, you risk making the solution $O(n \times \text{lot size})$ in the worst case.