昨日面接に出席しました。彼は私に解決すべきプログラミングの質問をいくつかくれました。私がそれらを解決したとき、インタビュアーはそれがより良い時間計算量で行うことができると言いました。私は非常に落ち込んでいたので、最高の時間計算量でプログラムを実行することはできません。最後に、面接のプロセスを終えることができません。しかし、私が知りたいのは、問題が発生した場合に最適なタイミングでどのようにできるかということです。その状態に到達するための私のアプローチは何ですか？私は完璧な答えが練習であることを知っています。しかし、それでも私は、プログラムをより短い時間で実行し、最高のメモリを使用するように、プログラムを実行する方法と方法を知りたいと思っています。私はどんな本を読まなければなりませんか？どのような問題を練習する必要がありますか？
PS：これは技術的な問題ではないことを私は知っています。しかし、どうすればそれができるのか教えてください。
アルゴリズム、データ構造、時間と空間の複雑さに関する最高の本の 1 つは、Introduction to Algorithmsです。また、面接の準備のために次の本を読むことをお勧めします。
この種の問題を解決するには、練習に加えて「トリックを見る」必要があります。この特定の例では、 がすべての要素を掛け合わせた積B[i] = P/A[i]であることに気付くかもしれません。したがって、この場合、O(n) のパフォーマンスは、最初に 1 回計算し (n-1 乗算)、次にそれぞれを計算する(別の n 除算) ことから得られます。PA[i]PB[i]
場合によっては、「トリックを見つける」最善の方法は、使用するアルゴリズムで繰り返されるパターンを探すことです。あなたの例では、説明で実際に文字列"A[2] * A[3] ... A[n-1]"を2回入力したことに注意してください。これは、「アルゴリズムでこのことを1回だけ実行できるか」と考える場所です。
たくさんのアルゴリズムを読んで練習してください。
オンラインジャッジからの問題解決は、問題解決スキルの効率と正確性を高めるのにも役立ちます。
一部の審査員のリストを以下に示します。