Question d'entrevue par une société de logiciels financiers pour une position de programmeur
Q1) Dites que vous avez un tableau pour lequel l'élément ith est le prix d'un stock donné sur jour i.
Si vous n'êtes pas autorisé à acheter une part du stock et de vendre une part du stock, concevez un algorithme pour trouver les meilleurs moments pour acheter et vendre.
Ma solution: Ma solution consistait à créer des différences entre les cours des actions entre jour I et Jour I + 1 pour la faletsize-1 jours, puis utilisez Kadane Algorithm pour renvoyer la somme du plus grand sous-cours continu.Je acheter ensuite au début de le plus grand tableau continu et vendre à la fin du plus grand Array continue.
Je me demande si ma solution est correcte et y a-t-il de meilleures solutions là-bas ???
Après avoir répondu à on m'a demandé une question de suivi, que j'ai répondu exactement la même
Q2) Étant donné que vous connaissez le cours de clôture futur de la société X pour les 10 prochains jours, Concevoir un algorithme pour déterminer si vous devriez acheter, vendre ou tenir pour chaque jour unique (vous êtes autorisé à faire seulement 1 décision tous les jours) dans le but de de maximiser le bénéfice
par exemple: jour 1 Prix de fermeture: 2.24
Prix de fermeture du jour 2: 2.11
...
Jour 10 Fermeture Prix: 3.00Ma solution: comme ci-dessus
J'aimerais savoir quoi se passe-t-il s'il y a un meilleur algorithme là-bas pour maximiser les bénéfices donnés que je peux prendre une décision chaque jour
5 Réponses :
Voici quelques réponses alternatives:
Q1) Travailler de gauche à droite dans la matrice fournie. Gardez une trace du prix le plus bas vu jusqu'à présent. Lorsque vous voyez un élément de la matrice Notez la différence entre le prix et le prix le plus bas jusqu'à présent, mettez à jour le prix le plus bas jusqu'à présent, et gardez une trace de la différence la plus élevée observée. Ma réponse est de faire le montant du bénéfice donné à la plus grande différence en vendant à ce moment-là, après avoir acheté au prix du prix le plus bas vu à cette époque.
Q2) Traitez-le comme un problème de programmation dynamique, où l'état à tout moment est de savoir si vous possédez une part ou non. Travailler de gauche à droite à nouveau. À chaque point, trouvez le bénéfice le plus élevé possible, étant donné une part d'une part à la fin de ce moment-là, et étant donné que vous ne possédez pas une part à la fin de ce moment-là. Vous pouvez le résoudre à partir du résultat des calculs de l'étape de l'heure précédente: Dans un cas, comparez les options d'achat d'une action et soustrayez ceci à partir du bénéfice donné que vous n'aviez pas possédé à la fin du point précédent ou que vous conservez une part. que vous avez possédé au point précédent. Dans l'autre cas, comparez les options de vente d'une part à ajouter au profit étant donné que vous possédez à l'heure précédente ou que vous restiez PAT avec le bénéfice étant donné que vous n'avez pas possédé à l'heure précédente. Comme c'est standard avec la programmation dynamique, vous conservez les décisions prises à chaque fois à temps et récupérez la liste correcte des décisions à la fin en travaillant à l'envers.
Supposons que les prix sont le tableau Construire un nouveau tableau I.e Maintenant, allez trouver le MAXIMUM SUM SUB-Array dans ceci.
ou
Recherchez un algorithme différent et résolvez le problème de sous-tableau maximum!
Les problèmes sont équivalents. p = [p_1, p_2, ..., p_n]
A = [P_1, P_2 - P_1, P_3 - P_2, ..., P_N - P_ {N-1}]
a [i] = p_ {i + 1} - p_i , prise p_0 = 0 . .
Votre réponse à la question 1 était correcte.
Votre réponse à la question 2 n'était pas correcte. Pour résoudre ce problème, vous travaillez à l'envers à partir de la fin, en choisissant la meilleure option à chaque étape. Par exemple, étant donné la séquence {1, 3, 5, 4, 6}, depuis 4 <6 Votre dernier mouvement est de vendre. Depuis 5> 4, le passage précédent à celui-ci est acheté. Depuis 3 <5, le déménagement sur 5 est vendre. Continuant de la même manière, le déplacement sur 3 est de tenir et du mouvement sur 1 est d'acheter.
Q1 Si vous n'êtes pas autorisé à acheter une part du stock et de vendre une part du stock, concevez un algorithme pour trouver les meilleurs moments d'achat et de vente.
Dans une seule passe via la matrice, déterminez l'index
i avec le prix le plus bas et l'indexj avec le prix le plus élevé. Vous achetez suri et vendez àj (vente avant d'acheter, en empruntant stock, est généralement autorisé dans la finance, donc c'est correct sij ). Si tous les prix sont les mêmes, vous ne faites rien.Q2 Étant donné que vous connaissez le cours de clôture futur de la Société X pour les 10 prochains jours, concevez un algorithme pour déterminer si vous devriez acheter, vendre ou posséder chaque jour (vous êtes autorisé à faire une décision que tous les jours. ) dans le but de maximiser le profit
Il n'y a que 10 jours et il n'y a donc que
3 ^ 10 = 59049 différentes possibilités. Il est donc parfaitement possible d'utiliser une force brute. C'est-à-dire, essayez toutes les possibilités et sélectionnez simplement celui qui donne le plus grand profit. (Même si un algorithme plus efficace a été trouvé, cela resterait un moyen utile de tester l'algorithme plus efficace.)Certaines solutions produites par l'approche de la force brute peuvent être invalides, par ex. Il pourrait ne pas être possible de posséder (ou de doit) plus d'une action à la fois. De plus, avez-vous besoin de finir par posséder 0 stocks à la fin des 10 jours, ou des positions sont-elles automatiquement liquidées à la fin des 10 jours? De plus, je voudrais préciser l'hypothèse que j'ai faite au premier trimestre, à savoir qu'il est possible de vendre avant d'acheter pour tirer parti des chutes des cours des actions. Enfin, il peut y avoir des frais de négociation à prendre en compte, y compris les paiements à faire si vous empruntez un stock afin de le vendre avant de l'acheter.
Une fois ces hypothèses clarifiées, il pourrait bien être possible de concevoir un algorithme plus efficace. Par exemple, dans le cas le plus simple si vous ne pouvez posséder qu'une seule action et que vous devez acheter avant de vendre, vous auriez un "Acheter" au premier minimum de la série, une "vente" au dernier maximum, et achète et vend à n'importe quel minima et maxima entre entre elles.
Plus j'y pense, plus ces questions d'entrevue sont autant sur la manière de voir comment et si un candidat clarifie un problème car ils sont sur la solution au problème.
Vous avez oublié des frais de négociation. Pour chaque accord, vous devez payer des frais. Donc, si vous vendez des stocks au même prix que vous avez acheté, vous perdez de l'argent. En outre, le plus bas - le plus élevé ne peut pas couvrir les frais.
@Sigterm vous avez raison, je n'incluais pas que: Je l'ajouterai à la réponse. En outre, sous des frais de négociation, si vous vendez avant d'acheter, vous le faites, je pense que vous devez payer pour emprunter le stock.
«Si vous vendez avant d'acheter, vous devez payer» bien sûr. Si vous vendez, vous payez les frais. Si vous achetez, vous payez également les frais. De plus, si vous achetez simplement au plus bas et que vous vendez au plus haut, cela ne maximisera pas les bénéfices, car le prix peut fluctuer, comme un roller coaster (volatil). Dans cette situation, il n'y aura qu'un seul prix le plus élevé et le plus bas, mais (si vous pouvez prédire l'avenir), vous pouvez faire une tonne d'argent pendant que le prix continue de vous déplacer. Donc, au lieu de pics, vous devez détecter des points lorsque la tendance tourne, voir si ce retournement est rentable et agir en conséquence.
@Sigterm a accepté tous ces points. L'OP a eu des contraintes: Q1 indique que vous ne pouvez avoir qu'un seul achat et une vente, alors que le Q2 permet autant d'achats et de vendre comme vous le souhaitez.
Votre solution pour le premier problème est correcte. La complexité de l'algorithme d'algorithme de Kadane est Votre solution pour le deuxième problème est fausse selon moi. Ce que vous pouvez faire est de stocker la
Votre idée est la meilleure solution que je puisse penser, mais me demande de me demander quelle est l'utilisation de la connaissance du meilleur moment pour acheter un stock, quand ce temps est passé ..
@Rezhirazie bien histoire se répète toujours haha
@ user414076 J'y ai pensé d'autres, est-ce correct: achetez si le prix monte demain, puis tenez pendant que le prix augmente, puis vendez si le prix ne montez pas demain. ?
Qu'en est-il de faire plusieurs algorithmes et de comparer les revenus et de choisir le meilleur. Par exemple, essayez l'algorithme que vous avez proposé plus, en prenant le jour le plus bas et le plus haut jour après ce jour-là. Comparer les deux algorithmes et choisir le meilleur, plus tout autre algorithme que vous puissiez penser. Un peu comme essayer tout et aller avec la meilleure approche,
ProB 1 pourrait être résolu en mettant à jour la valeur minimale des prix rencontrés avant la position I et vérifier la différence entre l'élément I et le minimum pour une différence maximale. Bien que cette solution et votre solution est exécutée dans
O (n) .Ainsi, vous avez donc demandé si elles produisaient des logiciels de trading d'initiés? :)
Dupliqué possible de Maximisez le bénéfice pour des devis dotés de stocks
@ user2284926: "L'histoire de la puits se répète toujours haha" en matière de commerce de stock, ce n'est pas le cas. Le logiciel qui utilise l'historique pour déterminer le prix futur brûlera à travers tout votre argent.