[Powered by Google Translate] [セミナー：技術インタビュー] [ケニーゆう、ハーバード大学] [これはCS50です。] [CS50.TV] こんにちは皆、私はケニーだ。私は現在、コンピュータサイエンスを勉強年生です。 私は、前者のCS、TFだし、私は私が下級生だったとき、私はこれを持って望む 私はこのセミナーを与えている理由だ。 だから私はあなたがそれをお楽しみください。 このセミナーでは、技術的インタビューについてです およびすべての私のリソースは、このリンクで見つけることができます 右ここにこのリンク、リソースのカップル。 だから私は、かなりの数の問題は、実際には、問題のリストを作りました。 私たちはヒントを見つけることができ、また一般的な資源のページ 面接のために準備する方法についての、 あなたは実際のインタビューの中で何をすべきかのヒント、 だけでなく、将来の参照のための問題と資源をアプローチする方法。 それはすべてオンラインです。 そして、ちょうどこのセミナーは、免​​責事項を、序文に このようにすべきでない - あなたの面接の準備 このリストに限定されるべきではない。 これはあくまで目安であることが意味され、 とあなたは間違いなく、私は塩の粒で言うすべてを取る必要があります しかし、また、私はあなたの面接の準備のお手伝いをするために使用されるすべてのものを使用しています。 

私は次のいくつかのスライドを介して高速化するつもりだ ので、我々は実際のケーススタディを得ることができます。 ソフトウェアエンジニアリングされた位置のための面接の構造、 一般的にそれは、30から45分です 会社によっては、複数のラウンド。 多くの場合は、ホワイトボード上にコーディングされます。 したがって、このような、しかし多くの場合、小規模スケールでホワイトボード。 あなたが電話インタビューを持っている場合は、おそらく使うことになるでしょう collabeditまたはGoogleドキュメントのどちらかはそう彼らはあなたが見ることができるライブコーディング あなたは電話でインタビューされている最中。 面接自体は、通常2つまたは3つの問題がある お使いのコンピュータサイエンスの知識をテストする。 そして、それはほぼ間違いなくコーディングかかわるでしょう。 お会いしましょう​​という質問の種類は、通常、データ構造やアルゴリズムです。 そしてこの種の問題を行う際に、 彼らは大きなO、時間と空間の複雑さとは何か、のように、あなたを求めるのだろうか？ 多くの場合、彼らはまた、より高いレベルの質問をする ので、システムを設計、 どのようにあなたのコードをレイアウトでしょうか？ 何インタフェース、どのクラス、お使いのシステムでどのモジュールを持っている、 これらがどのように一緒に対話しますか？ だから、データ構造とアルゴリズム、ならびに設計システム。 

私達が私達のケーススタディに飛び込む前に、いくつかの一般的なヒント。 私は、最も重要なルールは、常に大声で考えていると思います。 面接はあなたの思考プロセスを披露するチャンスであることになっている。 面接のポイントは測ることがインタビュアーです どのように考え、どのように問題を通過します。 あなたがすることができる最悪のことは、全体のインタビューを通して沈黙することです。 それはちょうど良いことではない。 あなたが質問を与えられたとき、あなたはまた、質問を理解していることを確認したい。 だから戻って自分の言葉で質問を繰り返す その試みは、徹底的いく​​つかの簡単なテストケースを動作させる あなたが質問を理解していることを確認します。 いくつかのテストケースを介して作業することもあなたにこの問題を解決する方法についての直観を与える。 あなたも、あなたが問題を解決するために役立ついくつかのパターンを発見するかもしれません。 その大きなヒントは、イライラしないことです。 イライラしないでください。 インタビューは、挑戦している、しかし、あなたがすることができる最悪のこと サイレントであることに加えて、目に見えてイライラする。 あなたが面接官にそのような印象を与えたくない。 そのあなた一つのこと - だから、多くの人々は、彼らがインタビューに行く、 彼らは、最初の最善の解決策を見つけようとする試み 本当に、紛れもなく明白な解決策は、通常、そこにときだ。 それが遅くなることがあり、それは非効率的かもしれませんが、あなたはそれを明記してください ちょうどので、より適切に動作するから出発点を持っています。 また、解決策を指摘するとの観点から、遅いです ビッグOの時間計算量や空間の複雑さ、 あなたが理解していることを面接者に実演します コー​​ドを記述し、これらの問題。 したがって、最初の最も簡単なアルゴリズムを考え出すことを恐れてはいけない し、そこからより良い仕事。 これまでに何か質問はありますか？オーケー。 

それで、我々の最初の問題にダイブしてみましょう。 "n個の整数の配列を指定して、配列をシャッフルする関数を書く n個の整数のすべての順列が等しく可能性があるとそのような場所で "を意味する。 とは、利用可能な整数の乱数発生器を持っていると仮定 それは半分の範囲は、0からiの範囲の整数を生成します。 誰もがこの問題を理解していますか？ 私はあなたにn個の整数の配列を与える、と私はあなたがそれをシャッフルしたい。 私のディレクトリでは、私は私が何を意味するかを実証するためのいくつかのプログラムを書いた。 私は、シャッフル20要素の配列をするつもりだ -10から9へ、 と私はあなたがこのようなリストを出力したい。 だから、これは私のソートされた入力配列である、と私はあなたがそれをシャッフルしたい。 我々は再びそれをやる。 みんなが質問を理解していますか？オーケー。 だから、それはあなた次第です。 いくつかのアイデアは何ですか？あなたは、n ^ 2、nログN、Nとしてそれを行うことができますか？ 提案に開きます。 オーケー。エミーによって示唆だから1アイデア、 最初の0〜20の範囲で、乱数、ランダムな整数を計算しています。 それで、我々の配列は20の長さを有していると仮定します。 20個の要素の私達の図では、 これは私たちの入力配列です。 そして今、彼女の提案は、新しい配列を作成することです ので、これは出力配列になります。 そして私は、randによって返されたに基づいて -  私がいたので、もし、17日としましょう 最初の位置に第十七要素をコピーします。 今、私たちは、削除する必要があります - 私たちはここにすべての要素をシフトする必要があります 上のように我々は最後にはギャップと真ん中に穴があることを確認します。 そして今、我々はこのプロセスを繰り返します。 今、私たちは、0と19の間に新しいランダムな整数を選ぶ。 我々はここで新しいiを持って、私たちはこの位置に、この要素をコピーします。 それから私達は項目を上にシフトして、我々は完全に新しい配列を持ってまで、私たちは、このプロセスを繰り返します。 このアルゴリズムの実行時間は何ですか？ まあ、のはこの影響を考えてみましょう。 我々は、すべての要素をシフトしている。 我々はこのiを削除するとき、我々は左にそれの後にすべての要素をシフトしている。 そして、それはO（n）のコストです なぜなら、私たちは最初の要素を削除する場合はどうなりますか？ だから、それぞれの除去のために、我々は削除する -  各削除はO（n）操作が発生 我々は人為をnとしたので、これはO（n ^ 2）シャッフルにつながる。 オーケー。だから良いスタート。良いスタート。 

もう一つの提案は、クヌースのシャッフルと呼ばれるものを使用することです またはフィッシャーYatesのシャッフル。 そしてそれは実際にはリニアタイムシャッフルです。 とアイデアは非常に似ています。 再び、我々は、我々の入力配列を持っている その代わりに私たちの入力/出力の2つの配列を使用しての、 私達は私達のシャッフル部分を追跡するために、配列の最初の部分を使用し、 そして我々は追跡し、我々はunshuffled部分のための私達のアレイの残りの部分を残す。 だからここは私が何を意味するかだ。我々は、とオフを開始 - 私たちは、iを選択し、 0〜20の配列。 我々の現在のポインタは最初のインデックスを指している。 我々は、いくつかの私は、ここを選択 そして今我々は交換します。 これは5であったと、これは4であったのであれば、 結果の配列は、ここでは5ここで、4を持つことになります。 そして今、我々はここでマーカーの点に注意してください。 左側にあるすべてが、シャッフルされ そして右側にすべてがunshuffledされています。 そして今、我々はプロセスを繰り返すことができます。 我々は今、1と20の間のランダムなインデックスを選択します。 それで、我々の新しいiがここにあると仮定します。 今、私たちはここで私たちの現在の新しい位置でこのiを入れ替える。 だから我々はこのように前後にスワッピングん。 私はそれをより具体的にするためのコードを起動しましょう​​。 我々は、私の私達の選択で開始 -  我々は0に等しい私で始まり、我々は、ランダムな場所jを選ぶ 配列のunshuffled部分で、iはn-1まで。 私がここにいるので、もし、ここにして、配列の残りの部分との間のランダムなインデックスを選択 そして我々は交換します。 これはシャッフルあなたのアレイに必要なすべてのコードです。 何か質問？ 

まあ、1が質問を必要とされ、なぜこれは正しいのですか？ なぜ、すべての順列は、等しく可能性が高いですか？ そして私は、その証拠を通ることはありません しかし、コンピュータサイエンスの多くの問題は、誘導を介して証明することができる。 あなたのどのように多くは、誘導に精通している？ オーケー。クール。 だからあなたは、単純な誘導によって、このアルゴリズムの正しさを証明することができます あなたの帰納法の仮定にどこにあるであろうか、それを前提とし 私のshuffleはすべての順列同じ確率を返します まで最初のi個の要素に。 さて、I + 1を考える。 そして、私たちは私たちのインデックスjがスワップを選択した方法によって、 し、その後、詳細を詰める - これはにつながる このアルゴリズムは返す理由の少なくとも完全な証拠 確率が等しい確率ですべての順列。 

すべての権利は​​、次の問題。 だから "、負、ゼロ、ポジティブ整数の配列を、与えられた 最大合計を計算する関数を書く 入力配列のいずれcontinueousサブアレイの。 " ここでの例では、すべての数値が正である場合、ある その後、現在最良の選択は、配列全体を取ることです。 1、2、3、4、10に等しい。 あなたはそこにいくつかのネガを持っている場合、 この場合、我々は最初の2つだけにしたい -1および/または-3を選択することが私たちの和をダウンさせることになるため。 時には我々は、配列の途中で開始する必要があります。 時々、私たちは全く何も選択しないようにしたい、それは何かを取ることではないのが最善です。 そして時にはそれが、秋取る方が良いでしょう それ以降のものは、大きなスーパーであるためです。したがって、任意のアイデア？ （学生、判読不能）>>うん。 私は-1取らないと仮定します。 次に、いずれかの私は1,000〜20,000を選択 または私はわずか3億ドルを選択します。 まあ、最良の選択は、すべての数字を取ることです。 この-1、負にもかかわらず、 全体の合計は、私は-1を取ることはなかったよりも良いです。 だから、私は前述のヒントの一つは、明らかに明白なことを述べることであった 最初とブルートフォースソリューション。 この問題での強引なソリューションとは何ですか？うん？ [ジェーン]まあ、私は強引な解決策を考える すべての可能な組み合わせを（判読不能）を追加することです。 [ゆう]オーケー。だからジェーンのアイデアは、すべての可能なを取ることです -  私は言い換えている - すべての可能な連続的な部分配列を取ることです、 その合計を計算し、すべての可能な連続サブアレイの最大値を取る。 何が一意的に私の入力配列の部分配列を識別？ 同様に、私は何の二つのことが必要なのでしょうか？うん？ （学生、判読不能）>>右。 インデックスと上限のインデックスの下限 一意の連続部分配列を決定します。 [女性学生]我々は、それがユニークな数字の配列の推定されていますか？ [ゆう]いいえ、彼女の質問は、私達は私達の配列を想定しています -  私たちの配列はすべて固有の番号がなく、答えはノーです。 

に我々の強引な解決策、start / endインデックスを使用する場合 一意的に私たちの継続的な部分配列を決定します。 我々はすべての可能な開始エントリに対して反復するのであれば、 と>または=を開始するすべてのエンドエントリ用、および<nの場合は、 あなたは合計を計算した後、我々はこれまで見てきた最大の和を取る。 この明確なのですか？ このソリューションの大きなOとは何ですか？ 時間的に。 はなく、かなりN ^ 2。 我々は0からnまで反復することに注意してください、 その結果は、forループの一つだ。 我々は、別のforループでは、ほとんど最初から最後まで、もう一度反復する。 そして今、その中で、我々は、すべてのエントリを総括しなければならない その結果、ループのための別のです。だから我々は3つのネストされたforループは、n ^ 3を持っています。 オーケー。これは、出発点として行く。 当社のソリューションは、n ^ 3よりも悪くはありません。 誰もが力ずくのソリューションを理解していますか？ 

オーケー。より良い解決策は、動的計画法と呼ばれるアイデアを使用しています。 あなたはCS124を取れば、それは、アルゴリズムとデータ構造です あなたは、この技術に精通しになります。 とアイデアは、最初に小さい問題にソリューションを構築しようとしています。 開始と終了：これはで私が何を意味するか、我々は現在、2つのことを心配する必要があります。 そして、それは迷惑なんだ。我々はこれらのパラメータのいずれかを取り除くことができれば何ですか？ ひとつのアイデアは、することです -  we're当社独自の問題を考えると、 範囲内の任意の部分配列[O、N-1]の最大合計数を見つける。 そして今、我々は、我々の現在のインデックスiに、私たちが知っている新しいサブ問題を、持っている 我々はそこを締結する必要があります知っている。私達の部分配列は、現在のインデックスで終わらなければなりません。 残りの問題があるので、ここで私達は私達のサブアレイを開始する必要がありますか？ これは理にかなっていますか？オーケー。 だから私はこの上をコーディングしてきたが、これが何を意味を見てみましょう。 codirectoryで、サブアレイと呼ばれるプログラムが、そこ そしてそれは、項目の数を取る そしてそれは私のシャッフルリストで最大の部分配列の和を返します。 したがって、この場合は、私たちの最大の部分配列は3です。 そして、それはちょうど2と1を使用して撮影している。 のそれを再度実行してみましょう。また、3です。 しかし、この時間は、我々は3を得た方法に注意してください。 我々は取った - 私達はちょうど3自体を取る それは両側にネガに囲まれているので、 これは、和<3をもたらすでしょう。 10項目で実行してみましょう。 それは7です今回は、大手3と4を取る。 今回は8だし、我々は1、4と3を取ることであることを得る。 だから、あなたにどのように直感を与えるために私たちは、この変換された問題を解決することができ、 のは、この部分配列を見てみましょう。 我々は、この入力配列を与えられた、そして我々は答えは8です知っている。 我々は、1,4、および3を取る。 しかし、我々が実際にその答えを得た方法を見てみましょう。 これらの指標のそれぞれで終了最大の部分配列を見てみましょう。 最初の位置で終了しなければならない最大の部分配列は何ですか？ [学生]ゼロ。 >>ゼロ。ちょうど-5を取ることはありません。 ここではそれは同様に0になるだろう。うん？ （学生、判読不能） [ゆう]ああ、申し訳ありませんが、それは-3である。 これは2であるので、これは-3です。 オーケー。だから-4、その位置を終わらせるために最大限の部分配列は何ですか -4はどこにいるのか？ゼロ。 一つ？ 1、5、8。 今、私は-2である場所で終わらなければなりません。 だから6、5、7、および最後の1は4です。 これらは私のエントリであることを知っている 私はこれらの指標のそれぞれで終わる必要があります変換された問題のために、 その後、私の最終的な答えはただですが、、全体でスイープを取る 値と最大値を取る。 したがって、このケースでは、8です。 これは、最大の部分配列は、このインデックスで終わることを意味します と、その前にどこかで始めました。 誰もがこの変換部分配列を理解していますか？ 

オーケー。まあ、のはこのための再発を把握しましょう​​。 ちょうど最初のいくつかのエントリを考えてみましょう。 だからここに、8 0、0、0、1、5であった。 そしてそこここに-2であった、そしてそれは6にダウンしました。 だから私は、位置iのサブ問題（i）でエントリを呼び出す場合は、 どのように私は前の部分問題への答えを使用することができます この部分問題に答えるために？ 私が見れば、このエントリは、考えてみましょう。 どうすれば見ることで回答6を計算することができます この配列とこの配列内の前部分問題への回答の組み合わせ？はい？ [女性学生]あなたが和の配列を取る 右のそれより前の位置で、8そう その後は、現在のサブ問題を追加します。 [ゆう]だか​​ら彼女の提案は、これら2つの数字を見ることである、 この番号とこの番号。 だから、この8は部分問題の答え（1  -  i）を指す。 そして、私の入力配列Aを呼び出してみましょう 、位置iで終わる最大のサブアレイを見つけるために 私は2つの選択肢があります：私はどちらかのサブアレイを続けることができます それは前のインデックスで終了、または新しいアレイを開始します。 私は、前のインデックスに開始サブアレイを続行した場合、 その後私は実現可能な最大合計は、前の部分問題への答えです 加えて、現在の配列エントリ。 しかし、私はまた、新しいサブアレイを開始するかを選択できます その場合、合計は0です。 1に加えて、現在の配列エントリ - だから答えは0の最大値、サブ問題iである。 この再発は理にかなっていますか？ 当社の再発は、我々がちょうど発見したように、サブ問題iである 、前の部分問題の最大のプラス私の現在の配列エントリと等しい これは、以前のサブアレイを続ける意味 または0であり、私の現在のインデックスにある新しい部分配列を開始します。 そして、かつて我々は、我々の最終的な答えその後、ソリューションのこのテーブルを築いてきました ちょうどサブ問題アレイにわたってリニア掃引を行う 値と最大値を取る。 これは私が言ったことを正確に実装したものです。 だから我々は新たなサブ問題の配列、部分問題を作成します。 最初のエントリは、0または最初のエントリは、それらの2の最大のいずれかです。 と部分問題の残りの部分 我々は我々がちょうど発見正確な再発を使用しています。 今、我々は部分問題の配列の最大値を計算し、それは私たちの最終的な答えだ。 

それでは、どのくらいのスペース、我々はこのアルゴリズムで使用していますか？ あなただけのCS50を撮影した場合は、非常に多くのスペースを論じていない可能性があります。 さて、もう一つ注意すべきは、私は、サイズnと一緒にここにmalloc関数と呼ばれることです。 それはあなたに何を示唆しているのでしょうか？ このアルゴリズムは、線形空間を使用しています。 私たちはより良いを行うことができますか？ あなたが最終的な答えを計算することが不要であることに気づくということはありますか？ 私は推測する良い質問ですが、どのような情報 我々は最後まですべての方法を実行する必要はありませんか？ 今、私たちは、これら二つのラインを見れば、 我々は、以前の下位の問題を気に そして我々は唯一の私たちが今までにこれまで見てきた最大気遣う。 私たちの最終的な答えを計算するために、我々は全体の配列を必要としません。 我々は唯一の最後の番号は、最後の2つの数字が必要です。 最大ための部分問題の配列、そして最後の番号の最後の番号です。 だから、実際には、我々は一緒にこれらのループを融合することができます と線形空間から一定のスペースに移動します。 現在の合計は、これまでのところ、ここでは、下位の問題、私たちの部分問題の配列の役割に代わるものです。 だから現在の合計は、これまでのところ、前の部分問題への答えです。 そして、その合計は、これまでのところ、私たちの最高の場所を取ります。 我々に沿って行くと、我々は最大値を計算する。 そして私たちは、一定の空間に線形空間から行く そして私達はまた私達の部分配列の問題に対する線形ソリューションを持っている。 

質問のこれらの種類のあなたのインタビューの中で取得します。 時間計算量とは何ですか、空間計算量は何ですか？ あなたはより行うことができますか？周りに保つために不要なものはありますか？ 私は、あなたが自分で取るべきだとの分析を強調するためにこれをした あなたはこれらの問題を介して作業しているとして。 常に "私がうまくやることはできますか？"、自問しているの 実際には、我々はこれよりも良い行うことができますか？ トリックの質問の並び替え。あなたがする必要があるため、できません 少なくとも、問題の入力を読み込みます。 あなたがする必要があるという事実は、少なくとも問題への入力を読み取るよう あなたは、線形時間よりも複雑な処理ができないことを意味します そしてあなたは、一定のスペースよりも良い行うことはできません。 だから、これは、実際には、この問題を解決する最善の方法です。 質問はありますか？オーケー。 

株式市場の問題： "正、ゼロ、または負のn個の整数の配列を指定して、 N日間の株価を表す、 あなたが作るこ​​とができる最大の利益を計算する関数を書く あなたはこれらのn日以内に正確に1株を売買することを考える。 " 本質的に、我々は低買いたい、高く売る。 そして、我々は我々が作ることができる最善の利益を把握したい。 私の先端に戻って、何をすぐに明らかに、最も単純な答えですが、それは遅いですか？ はい？ （学生、判読不能）>>はい。 >>だからあなただけしかし行くと株価になります 各時点で、（判読不能）であった。 [ゆう]わかりましたので、彼女の解決策 - コンピューティングの彼女の提案 最低と最高の計算は必ずしも動作しない 最高は最低の前に発生する可能性があるためです。 だから、この問題への強引な解決策は何ですか？ 私が独自に私が作る利益を決定する必要があります2つのことは何ですか？右。 強引なソリューションです - ああ、そう、ジョージの提案は、我々は唯一の二日必要です ユニークな2日間の利益を決定する。 だから我々は、購入/売却など、すべてのペアを計算する 負または正またはゼロかもしれない利益を計算します。 我々は日のすべてのペアを繰り返し処理した後に行うことを最大の利益を計算します。 それが私たちの最終的な答えになります。 そして、その解決策がありますので、O（n ^ 2）であるnの2ペアを選択します -  あなたが最後の日の中から選ぶことができます数日。 わかりましたので、私はここで、ブルートフォースソリューション上に行くつもりはない。 私はnログn解決策があることを伝えるつもりです。 あなたは現在、nログnであるものは何なアルゴリズムを知っていますか？ それはトリックの質問ではありません。 

マージソート。マージソートは、nログnです そして実際に、この問題を解決する一つの方法は、使用することです と呼ばれるアイデアのマージソートの種類は、一般的には、分割統治。 そして、次のようにアイデアがある。 あなたは、左半分にベストバイ/販売ペアを計算したいとします。 あなたはわずか2日間の最初のn個で、作ることができる最善の利益を見つける。 その後は、ベストバイをoompute /右半分にペアを販売したい 2日間のため最後のn。 そして、今の質問は、どのように我々は戻って一緒にこれらのソリューションをマージしないのですか？ はい？ （学生、判読不能） オーケー。>>だから私は絵を描くことができます。 はい？ （ジョージ、判読不能） まさに>>。ジョージのソリューションは、まったく正しいです。 彼の提案があるので、まず、最善売る/買うペアを計算する と左半分で発生するので、左、その左と呼びましょう。 最高の右半分で発生するペアを購入/販売しています。 我々は、これらの2つの数値を比較した場合しかし、我々は事件を逃している ここで我々はここで買うと、右半分のどこかに売っています。 我々は左半分で購入、右半分に販売しています。 両方の半分にまたがるベストバイ/販売ペアを計算するための最良の方法 ここで最小値を計算し、ここで最大値を計算するものです その差を取る。 売る/買うペアはここでしか発生したので、2例、 ここだけ、または両方の半分で、これらの3つの番号で定義されます。 だから我々のアルゴリズムは一緒に戻って我々のソリューションをマージするには、 我々は最高の買い/売りのペアを計算したい 我々は左半分に購入し、右半分に販売する場所。 と行うための最善の方法は、前半で最低価格を計算することである 最高の右半分の価格、その差を取る。 結果として3利益は、これらの3つの数字は、あなたは、最大3つを取る そしてそれはあなたがこれらの最初と終わり日間にわたって行うことができます最高の利益だ。 ここで重要な線は赤で表示しています。 これは、左半分に答えを計算する再帰的な呼び出しです。 これは右半分に答えを計算する再帰的な呼び出しです。 これら二つのforループは、それぞれ左と右半分の最小値と最大値を計算します。 今、私は両方の半分にまたがる利益を計算し、 そして最終的な答えは、これらの3つの最大値です。 オーケー。 

だから、確かに、我々はアルゴリズムを持っていますが、もっと大きな問題は、 この時の複雑さは何ですか？ そして、私はマージソートを述べた理由は、この形の答えを分けるということです 2にしてから再び一緒に当社のソリューションをマージ 正確にマージソートの一形態である。 だから私は期間を通じて手放す。 我々はステップ数であることが関数T（n）を定義した場合 n日のために、 私たちの2つの再帰呼び出し 各々はT（N / 2）、費用としている そして、これらの呼び出しの2があります。 今私は、左半分の最小値を計算する必要が 私はN / 2時間、プラス右半分、最大で行うことができる。 だから、これはちょうどnです。 そして、ある一定の仕事のプラス。 そして、この漸化式 正確にマージソートのために漸化式である。 そして、我々はすべてのマージソート、常にn log n時間であることを知っている。 したがって、我々のアルゴリズムは、nログnの時間です。 この反復は意味をなさないか？ これだけの簡単な要約： T（n）は、最大の利益を計算するステップ数です n日の経過。 我々は再帰呼び出しを分割する方法 、最初のn / 2日に当社のソリューションを呼び出すことです その結果は、1つのコールだが、 それから私達は後半に再び呼び出す。 だから、2つの呼び出しです。 そして、我々は、我々が線​​形時間で行うことができ、左半分に最小値を求める 我々は、線形時間で行うことができます右半分の最大値を、見つける。 ので、n / 2 + n / 2のちょうどnです。 その後、我々は演算を行うようなもので、ある一定の仕事を持っています。 この漸化式は、正確にマージソートのために漸化式である。 したがって、私たちのシャッフルアルゴリズムはまた、あるnはnをログに記録します。 それでは、どのくらいのスペース、我々は使用していますか？ のコードに戻りましょう。 

良い質問は、どのように多くのスタックフレーム私たちはこれまで、任意の時点でなければならないのですか？ 我々は、再帰を使用しているので、 スタックフレームの数は、私たちの領域の使用状況を判断します。 のは、n = 8を考えてみましょう。 我々は、8日にシャッフルを呼び出す 最初の4つのエントリにシャッフルを呼び出すとなる、 これは、最初の2つのエントリでシャッフルを呼び出します。 それで、我々のスタックがある - これは私たちのスタックです。 そして、我々は、1日に再びシャッフルを呼び出す そしてそれが私たちの基本ケースとは何かを、私たちはすぐに戻ります。 私たちが今までにこれほど多くのスタックフレーム以上を持っていますか？ いいえ、私たちが呼び出しを行うたびので、 シャッフルを再帰的に呼び出し、 我々は半分に私たちのサイズを分割します。 我々はこれまでに、任意の時点で持っているスタックフレームの最大数は、そう ログnスタックフレームのオーダーである。 各スタックフレームは、一定の空間を有している スペースのため、合計金額、 私たちが今まで使用スペースの最大量は、O（log n）の空間です ここで、nは日数です。 

さて、常に自問して、 "私たちはより良いことができますか？" 特に、我々はすでに解決した問題にこれを削減することができますか？ ヒント：私たちはこれだけ前に他の二つの問題を議論し、それがシャッフルされることはないだろう。 私たちは最大の部分配列の問題に、この株式市場の問題に変換することができます。 どのように我々はこれを行うことができますか？ あなたの一人ですか？エミー？ （エミー、判読不能） [ゆう]その通りです。 だから、最大の部分配列の問題、 我々は、継続的な部分配列の和を探しています。 と株式の問題のためのエミーの提案、 変更、またはデルタを検討してください。 そして、これの絵がある - これは、株式の価格は、 しかし、我々はそれぞれの連続した​​日間の差を取ったなら -  ので、我々は我々が作ることができる最大の利益は、その最高価格を参照してください 我々はここでここで購入し、販売している場合があります。 部分配列の問題を見てみましょう - しかし、連続を見てみましょう。 だからここで、我々は、することができます - ここからここに行く、 私たちは、肯定的な変化を持って、ここからここに行く我々は負の変化を持っています。 しかし、その後、私たちは巨大な肯定的な変化を持って、ここからここへ行く。 そして、これらは私たちが私たちの最終的な利益を得るために総括すべき内容です。 その後、我々はより多くの負の変化をここに持っている。 私たちの最大の部分配列の問題に私達の在庫の問題を削減するための鍵 日の間の差分を考慮することです。 だから我々は、デルタと呼ばれる新しい配列を作成する 0を指定するための最初のエントリを初期化する その後、各デルタの（i）は、違いがあることをみましょう 私の入力配列（i）、および配列（I  -  1）。 その後、我々は最大の部分配列のための私達のルーチンプロシージャを呼び出す デルタの配列を渡します。 そして最大の部分配列は線形時間であるためです そしてこの減少は、このデルタ配列を作成するこのプロセスは、 また、線形時間である その後、株式の最終的な解決策はO（n）の仕事に加えてO（n）の作品です、まだO（n）の作品です。 だから我々は我々の問題に対する線形時間のソリューションを持っている。 誰もがこの変換を理解していますか？ 

あなたが常に持っているべきであると一般的には、良いアイデア あなたが見ているという新たな問題を軽減しようとしています。 それは古い問題に精通して見える場合は、 古い問題にそれを下げてみてください。 そして、あなたは古い問題で使用したことのすべてのツールを使用できるかどうか 新しい問題を解決する。 だから包むために、技術的なインタビューは挑戦しています。 これらの問題は、おそらくより多くの困難な問題のいくつかである あなたはインタビューの中で表示される可能性がある、 あなたは、私がちょうどカバーしているすべての問題を理解していないそうだとすれば、それは大丈夫です。 これらは、より困難な問題のいくつかである。 練習、練習、練習。 私は配布資料の問題の多くを与えますので、間違いなくそれらをチェックアウトする。 あなたのインタビューで、幸運。すべての私のリソースは、このリンクに掲載されてい と先輩の友人の一人は、技術的なモックインタビューを行うことを提案している もし興味があるそうだとすれば、電子メールはそのメールアドレスでヤオウィル。 あなたには、いくつかの質問がある場合、あなたは私を聞くことができます。 君たちは、技術的なインタビューに関連する特定の質問がありますか あるいは我々がこれまで見てきたすべての問題？ オーケー。さて、あなたのインタビューに幸運。 [CS50.TV]