# Quant Interview - Best time to buy and short stock with position constraint

I was given a problem at a job interview, I'm trying to solve it afterwards

You are given a list of N trades for some stock, you need to determine how much volume for each trade an ideal strategy would execute, provided that you cannot buy or short more than K (=const) shares. The algorithm should work for O(N) and be constant in memory.

It is clear how to solve such a problem by dynamic programming (with memory O(K) and complexity O(N * K) = O(N)), but the running time on 1e5 trades is about a couple of hours, although it is necessary to work for a couple of seconds. Maybe there are some optimisations for such dynamics?

(fyi. $$d[i][p] = max(d[i-1][p],\,\,\,\, d[i-1][p - \text{side_sign} * x] - \text{side_sign} \cdot x \cdot \text{trade['price']}$$ $$x \in [1, \text{ trade['amount']}])$$, $$\text{side_sign = (-1 if trade['side'] == 'short' else 1)}$$)

A promising approach to solving this task involves using Cartesian coordinates to represent two variables: position and USD balance. The first trade generates a segment within these coordinates, defined as $$(\text{side_sign} * x,\; -\; \text{side_sign} * \text{trade['price']} * x),\; x \in [0,\;\text{trade['amount']}]$$ where $$x$$ ranges from 0 to the trade's amount. When we introduce a subsequent trade, also represented similarly, we expand the set to include all potential outcomes for position and USD balance after partially executing the two considered trades.
• Thanks Mark. So, aside from the maximum restriction, you are given a list at on day $D$ of the stocks ( and their respective amounts ) you should have bought and shorted on day $D-1$. Sep 20 at 15:29