9

金融ソフトウェア会社によるプログラマー職の面接質問

Q1) i 番目の要素が i 日目の特定の株式の価格である配列があるとします。

株式の 1 株の購入と 1 株の売却のみが許可されている場合、売買に最適な時期を見つけるアルゴリズムを設計します。

私の解決策: 私の解決策は、arraysize-1 日間の i 日と i+1 日の間の株価の差の配列を作成し、Kadane アルゴリズムを使用して最大の連続部分配列の合計を返すことでした。最大の連続配列の開始点で売り、最大の連続配列の最後で売ります。

私の解決策が正しいかどうか疑問に思っています。より良い解決策はありますか???

答えると、フォローアップの質問をされましたが、まったく同じように答えました

Q2) 次の 10 日間の会社 x の将来の終値がわかっている場合、毎日 (毎日 1 つの決定のみを行うことができます)、購入、販売、または保持する必要があるかどうかを決定するアルゴリズムを設計します利益を最大化する目的

例: 1 日目の終値:2.24
2 日目の終値:2.11
...
10 日目の終値:3.00

私の解決策：上記と同じ

毎日決定を下すことができることを考えると、利益を最大化するためのより良いアルゴリズムがあるかどうかを知りたいです

4

5 に答える 5

3

Q1 株式の 1 株の購入と 1 株の売却のみが許可されている場合、売買に最適な時期を見つけるアルゴリズムを設計してください。

配列の 1 回のパスiで、最低価格のインデックスjと最高価格のインデックスを決定します。で買ってiで売るj（株を借りて買う前に売ることは、金融では一般的に認められているので、 なら大丈夫ですj < i）。すべての価格が同じ場合は、何もしません。

Q2 x 社の次の 10 日間の将来の終値がわかっている場合、毎日 (毎日 1 つの決定のみを行うことができます) 買い、売り、または保持する必要があるかどうかを決定するアルゴリズムを設計します利益の最大化の目的

3^10 = 5904910 日しかないので、異なる可能性しかありません。したがって、ブルートフォースを使用することは完全に可能です。つまり、あらゆる可能性を試して、最大の利益をもたらすものを選択するだけです。(より効率的なアルゴリズムが見つかったとしても、これはより効率的なアルゴリズムをテストするための有用な方法であり続けます。)

ブルート フォース アプローチによって生成されたソリューションの一部は無効な場合があります。たとえば、一度に複数の共有を所有する (または借りる) ことができない場合があります。さらに、10 日の終わりに 0 株を保有する必要がありますか、それとも 10 日の終わりにポジションが自動的に清算されますか? また、Q1 で立てた前提、つまり株価の下落を利用して、買う前に売ることも可能だという前提を明確にしたいと思います。最後に、株を買う前に株を売るために借りる場合の支払いを含め、考慮すべき取引手数料があるかもしれません。

これらの仮定が明確になれば、設計をより効率的なアルゴリズムにすることが可能になるでしょう。たとえば、最も単純なケースで、1 株しか所有できず、売却する前に購入する必要がある場合、シリーズの最初の最小値で「購入」し、最後の最大値で「販売」し、購入して間の任意の最小値と最大値で販売されます。

考えれば考えるほど、これらの面接の質問は、問題の解決策についてであるのと同じくらい、候補者が問題を明確にする方法とその有無を確認するためのものだと思います。

于 2013-06-07T13:01:55.923 に答える
0

最初の問題の解決策は正解です。Kadane's Algorithm runtime complexity is O(n)は、最大部分配列問題の最適解です。このアルゴリズムを使用する利点は、実装が簡単なことです。

私によると、2番目の問題に対するあなたの解決策は間違っています。できることは、見つけた最大合計部分配列の左右のインデックスを格納することです。最大合計部分配列とその左右のインデックスが見つかったら。この関数は、左側の部分、つまり 0 から left -1 および右側の部分、つまり right + 1 から Array.size - 1 で再度呼び出すことができます。したがって、これは基本的に再帰プロセスであり、この再帰の構造をさらに設計することができます。この問題を解決する基本ケース。そして、このプロセスに従うことで、利益を最大化できます。

于 2014-12-19T20:18:48.300 に答える
0

質問 1 に対するあなたの答えは正解でした。

質問 2 に対するあなたの回答は正しくありませんでした。この問題を解決するには、各ステップで最適なオプションを選択して、最後から逆方向に作業します。たとえば、シーケンス { 1, 3, 5, 4, 6 } が与えられた場合、4 < 6 なので、最後の手は売りです。5 > 4 なので、その前の動きは買いです。3 < 5 なので、5 への移動は売りです。同様に続けて、3 の動きはホールド、1 の動きは買いです。

于 2013-06-03T03:24:32.603 に答える