2
$\begingroup$

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)}$)

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

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.

As we continue to add more trades, we generate a larger set of potential outcomes. The key insight is this: rather than maintaining a record of all individual points that could arise from these multiple combinations, it's sufficient to focus on the convex hull of this set. Each new trade can then be used to update this convex hull. Finally, once all trades have been considered, it's easy to identify the point on the convex hull that intersects the balance-axis at the highest USD balance while zeroing out the position.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Hi Mark: Concentrating on your original question and not your answer, could you explain how the formula in the fyi part of your question is obtained. I couldn't even think about your question because I had no clue about the formula. Maybe that was the case for others also ? But it sounds like you definitely know what you're doing about it without any replies !!!!!! Thanks. $\endgroup$
    – mark leeds
    Sep 16 at 5:02
  • $\begingroup$ Hi there, d[i][p] -- this is maximal profit using first i trades and having p stocks. $\endgroup$
    – Mark Silverman
    Sep 19 at 11:57
  • $\begingroup$ let the current trade be a sell-trade of N stocks. so the value of d[i][p] is maximum of d[i-1][p] (i.e. not using i-th trade at all) and all possible values d[i-1][p + x] + price[i] * x, where x from 1 to N (here we use d[i-1][p + x] because we updating element with position p and we sell x stocks, so need to use previous element with position p + x) (sorry for the double comment, I'm just going over the edition limit) $\endgroup$
    – Mark Silverman
    Sep 19 at 12:07
  • $\begingroup$ 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$. $\endgroup$
    – mark leeds
    Sep 20 at 15:29
  • $\begingroup$ also, why is it price[i] * x. Does that mean that if you shorted it yesterday then you would have received that price[i] for that stock ? The prices are known I assume since it's day D and the data is from day (D - 1) ? $\endgroup$
    – mark leeds
    Sep 21 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.