Entrevista de Quant: Mejor momento para comprar y vender acciones cortas con restricciones de posición

Question

Me dieron un problema en una entrevista de trabajo, estoy tratando de resolverlo posteriormente

Se te ha dado una lista de N trades para alguna acción, necesitas determinar cuánto volumen para cada trade ejecutaría una estrategia ideal, siempre y cuando no puedas comprar ni vender más de K (=const) acciones. El algoritmo debería funcionar en O(N) y ser constante en memoria.

Es claro cómo resolver un problema así mediante programación dinámica (con memoria O(K) y complejidad O(N * K) = O(N)), pero el tiempo de ejecución en 1e5 trades es de aproximadamente un par de horas, aunque es necesario que funcione en un par de segundos. ¿Tal vez hay algunas optimizaciones para esa dinámica?

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

Answer 1

Un enfoque prometedor para resolver esta tarea implica usar coordenadas cartesianas para representar dos variables: posición y saldo en USD. El primer intercambio genera un segmento dentro de estas coordenadas, definido como $(\text{side_sign} * x,\; -\; \text{side_sign} * \text{trade['price']} * x),\; x \in [0,\;\text{trade['amount']}]$ donde $x$ varía de 0 a la cantidad de la operación. Cuando introducimos una operación posterior, también representada de manera similar, expandimos el conjunto para incluir todos los posibles resultados para la posición y el saldo en USD después de ejecutar parcialmente las dos operaciones consideradas.

A medida que continuamos agregando más operaciones, generamos un conjunto más grande de resultados potenciales. La idea clave es la siguiente: en lugar de mantener un registro de todos los puntos individuales que podrían surgir de estas múltiples combinaciones, es suficiente enfocarse en la envoltura convexa de este conjunto. Cada nueva operación luego puede utilizarse para actualizar esta envoltura convexa. Finalmente, una vez que se han considerado todas las operaciones, es fácil identificar el punto en la envoltura convexa que intersecta el eje de balance con el saldo en USD más alto mientras que se anula la posición.