動的計画法の面接の問題を解決するには、次の手順に従ってください

ソフトウェア製品の構築に豊富な経験があるにもかかわらず、多くのエンジニアは、アルゴリズムに焦点を当てたコーディングインタビューを行うことを考えると不安を感じます。私は、Refdash、Google、および私が参加したスタートアップで何百人ものエンジニアにインタビューしました。エンジニアを不安にさせる最も一般的な質問のいくつかは、動的計画法(DP)に関するものです。

多くのテクノロジー企業は、インタビューでDPの質問をするのが好きです。エンジニアリングの役割で誰かの能力を評価するのに効果的かどうかを議論することはできますが、DPは、エンジニアが好きな仕事を見つけるためにつまずく分野であり続けます。

動的計画法—予測可能で準備可能

DPの質問がエンジニアリング能力をテストする最良の方法ではないかもしれないと私が個人的に信じる理由の1つは、それらが予測可能であり、パターンマッチングが容易であるということです。それらは、エンジニアリング能力とは対照的に、準備のためにはるかに多くをフィルタリングすることを可能にします。

これらの質問は通常、外見上はかなり複雑に見え、それらを解決する人はアルゴリズムが非常に得意であるという印象を与える可能性があります。同様に、DPのいくつかの心をねじる概念を乗り越えることができないかもしれない人々は、アルゴリズムの知識がかなり弱いように見えるかもしれません。

現実は異なり、彼らのパフォーマンスの最大の要因は準備です。だから、みんながそれに備えていることを確認しましょう。これを最後にきっぱりと。

動的計画問題を解決するための7つのステップ

この投稿の残りの部分では、問題が「DP問題」であるかどうかを判断し、そのような問題の解決策を理解するために従うことができるレシピについて説明します。具体的には、次の手順を実行します。

  1. DP問題を認識する方法
  2. 問題の変数を特定する
  3. 漸化式を明確に表現する
  4. ベースケースを特定する
  5. 繰り返し実装するか再帰的に実装するかを決定します
  6. メモ化を追加する
  7. 時間計算量を決定する

サンプルDP問題

これから作成する抽象化の例を示すために、サンプルの問題を紹介します。各セクションでは、問題について説明しますが、問題とは別にセクションを読むこともできます。

問題文:

この問題では、途中でスパイクを避けながら、停止しようとしているクレイジーなジャンプボールに乗っています。

ルールは次のとおりです。

1)スパイクの束が入った平らな滑走路が与えられます。滑走路は、特定の(離散的な)スポットにスパイクがないかどうかを示すブール配列で表されます。明確な場合はTrue、明確でない場合はFalseです。

配列表現の例:

2)開始速度Sが与えられます。Sは任意の時点で負でない整数であり、次のジャンプでどれだけ前進するかを示します。

3)スポットに着陸するたびに、次のジャンプの前に最大1ユニットずつ速度を調整できます。

4)滑走路沿いのどこでも安全に停止したい(アレイの最後にある必要はありません)。速度が0になると停止します。ただし、いずれかの時点でスパイクに着地すると、バウンドするクレイジーなボールが破裂し、ゲームオーバーになります。

関数の出力は、滑走路のどこにでも安全に停止できるかどうかを示すブール値である必要があります。

ステップ1:動的計画問題を認識する方法

まず、DPは本質的に単なる最適化手法であることを明確にしましょう。DPは、問題をより単純なサブ問題のコレクションに分解し、それらのサブ問題のそれぞれを1回だけ解決し、それらの解決策を保存することによって問題を解決する方法です。次回同じサブ問題が発生したときは、その解を再計算する代わりに、以前に計算された解を検索するだけです。これにより、ストレージスペースの(うまくいけば)適度な支出を犠牲にして計算時間を節約できます。

DPを使用して問題を解決できることを認識することは、問題を解決するための最初の、そして多くの場合最も難しいステップです。あなたが自問したいのは、あなたの問題の解決策が同様の小さな問題の解決策の関数として表現できるかどうかです。

この例の問題の場合、滑走路上のポイント、速度、および前方の滑走路が与えられると、次にジャンプする可能性のあるスポットを特定できます。さらに、現在の速度で現在の地点から停止できるかどうかは、次に進むことを選択した地点から停止できるかどうかにのみ依存しているようです。

これは素晴らしいことです。前進することで、前方の滑走路を短くし、問題を小さくすることができるからです。停止できるかどうかが明らかになるまで、このプロセスをずっと繰り返すことができるはずです。

動的計画法の問題を認識することは、多くの場合、それを解決する上で最も難しいステップです。問題の解決策は、同様の小さな問題の解決策の関数として表現できますか?

ステップ2:問題の変数を特定する

これで、サブ問題間に再帰的な構造があることがわかりました。次に、関数パラメーターの観点から問題を表現し、それらのパラメーターのどれが変更されているかを確認する必要があります。

通常、インタビューでは、1つまたは2つのパラメータを変更しますが、技術的にはこれは任意の数にすることができます。1つのパラメーターが変化する問題の典型的な例は、「n番目のフィボナッチ数を決定する」です。2つのパラメータが変化する問題のこのような例は、「文字列間の編集距離の計算」です。これらの問題に精通していない場合でも、心配する必要はありません。

変更されるパラメーターの数を判別する方法は、いくつかのサブ問題の例をリストし、パラメーターを比較することです。変化するパラメーターの数を数えることは、解決しなければならないサブ問題の数を決定するのに役立ちます。また、ステップ1からの漸化式の理解を強化する上で、それ自体が重要です。

この例では、サブ問題ごとに変更される可能性のある2つのパラメーターは次のとおりです。

  1. 配列位置(P)
  2. 速度(S)

前方の滑走路も変化していると言えますが、変化しない滑走路全体と位置(P)がすでにその情報を持っていることを考えると、それは冗長です。

これで、これら2つの変更パラメーターとその他の静的パラメーターを使用して、サブ問題の完全な説明が得られました。

変化するパラメーターを特定し、サブ問題の数を判別します。

ステップ3:漸化式を明確に表現する

これは、コーディングに取り掛かるために多くの人が急いで通過する重要なステップです。漸化式をできるだけ明確に表現すると、問題の理解が強化され、他のすべてが大幅に簡単になります。

漸化式が存在することを理解し、パラメーターの観点から問題を指定すると、これは自然なステップになるはずです。問題は互いにどのように関連していますか?言い換えると、サブ問題を計算したと仮定しましょう。主な問題をどのように計算しますか?

サンプル問題での考え方は次のとおりです。

次の位置にジャンプする前に最大1まで速度を調整できるため、可能な速度は3つだけであり、次の可能性がある場所は3つです。

より正式には、速度がS、位置Pの場合、(S、P)から次のようになります。

  1. (S、P + S) ; #速度を変更しない場合
  2. (S — 1、P + S — 1) ; #速度を-1変更した場合
  3. (S + 1、P + S + 1) ; #速度を+1変更した場合

上記のサブ問題のいずれかで停止する方法を見つけることができれば、(S、P)から停止することもできます。これは、(S、P)から上記の3つのオプションのいずれかに移行できるためです。

これは通常、問題の細かいレベルの理解です(わかりやすい英語の説明)が、関係を数学的に表現したい場合もあります。canStopを計算しようとしている関数を呼び出しましょう。次に:

canStop(S、P)= canStop(S、P + S)|| canStop(S — 1、P + S — 1)|| canStop(S + 1、P + S + 1)

ウーフー、私たちは再発関係にあるようです!

漸化式:サブ問題を計算したとすると、主な問題をどのように計算しますか?

ステップ4:ベースケースを特定する

基本ケースは、他のサブ問題に依存しないサブ問題です。このようなサブ問題を見つけるには、通常、いくつかの例を試して、問題がどのように単純化されて小さなサブ問題になるかを確認し、どの時点でそれ以上単純化できないかを特定します。

問題をさらに単純化できない理由は、パラメータの1つが、問題の制約を考慮して不可能な値になるためです。

この例の問題では、SとPの2つの変更パラメーターがあります。SとPの可能な値が正しくない可能性があることを考えてみましょう。

  1. Pは指定された滑走路の境界内にある必要があります
  2. Pは、滑走路[P]が偽になるようなものにすることはできません。これは、スパイクの上に立っていることを意味するためです。
  3. Sを負にすることはできず、S == 0は完了したことを示します

パラメータに関して行うアサーションをプログラム可能なベースケースに変換するのは、少し難しい場合があります。これは、コードを簡潔に見せて不要な条件をチェックしたくない場合は、アサーションをリストするだけでなく、これらの条件のどれが可能であるかについても考慮する必要があるためです。

この例では:

  1. P <0 || P> =滑走路の長さは正しいことのようです。代替的には、M考慮するかもしれないakingのP ==端滑走路ベースケース。ただし、問題が滑走路の端を超えるサブ問題に分割される可能性があるため、実際に不平等をチェックする必要があります。
  2. これはかなり明白なようです。runway [P]がfalseどうかを簡単に確認できます
  3. #1と同様に、S <0およびS == 0を簡単に確認できます。ただし、ここでは、Sが最大で1減少するため、Sを<0にすることは不可能であると推論できます。事前にS == 0の場合。THER EFORE S == 0 Sパラメータの十分な基本ケースです。

ステップ5:反復的に実装するか再帰的に実装するかを決定します

これまでの手順について説明した方法から、問題を再帰的に実装する必要があると思われるかもしれません。ただし、これまでに説明したことはすべて、問題を再帰的に実装するか反復的に実装するかを完全に認識していません。どちらのアプローチでも、漸化式と基本ケースを決定する必要があります。

反復的に実行するか再帰的に実行するかを決定するには、トレードオフについて慎重に検討する必要があります

スタックオーバーフローの問題は、通常、取引のブレーカーであり、(バックエンド)本番システムで再帰を使用したくない理由です。ただし、インタビューの目的上、トレードオフについて言及している限り、通常はどちらの実装でも問題ないはずです。両方を実装することに慣れているはずです。

私たちの特定の問題では、両方のバージョンを実装しました。そのためのPythonコードは次のとおりです。

再帰的な解決策:(元のコードスニペットはここにあります)

反復的な解決策:(元のコードスニペットはここにあります)

ステップ6:メモ化を追加する

メモ化は、DPと密接に関連する手法です。これは、高価な関数呼び出しの結果を保存し、同じ入力が再度発生したときにキャッシュされた結果を返すために使用されます。

再帰にメモ化を追加するのはなぜですか?同じサブ問題が発生しますが、メモ化せずに繰り返し計算されます。これらの繰り返しは、指数関数的な時間計算量につながることがよくあります。

再帰的なソリューションでは、メモ化を追加するのは簡単だと感じるはずです。理由を見てみましょう。メモ化は関数の結果の単なるキャッシュであることを忘れないでください。いくつかのマイナーな最適化を絞り出すためにこの定義から逸脱したい場合がありますが、メモ化を関数結果キャッシュとして扱うことが、それを実装するための最も直感的な方法です。

これは、次のことを行う必要があることを意味します。

  1. すべてのreturnステートメントの前に関数の結果をメモリに保存します
  2. 他の計算を開始する前に、関数の結果についてメモリを検索してください

これは、メモ化が追加された上記のコードです(追加された行が強調表示されています):(元のコードスニペットはここにあります)

メモ化とさまざまなアプローチの有効性を説明するために、いくつかの簡単なテストを行いましょう。これまでに見た3つの方法すべてをストレステストします。設定は次のとおりです。

  1. ランダムな場所にスパイクがある長さ1000の滑走路を作成しました(スパイクが任意の場所にある確率を20%にすることを選択しました)
  2. initSpeed = 30
  3. すべての関数を10回実行し、平均実行時間を測定しました

結果は次のとおりです(秒単位)。

純粋な再帰的​​アプローチは、反復的アプローチよりも約500倍、メモ化を伴う再帰的アプローチよりも約1300倍の時間がかかることがわかります。この不一致は滑走路の長さとともに急速に大きくなることに注意してください。自分で実行してみることをお勧めします。

ステップ7:時間計算量を決定する

動的計画問題の計算時間の複雑さをはるかに簡単にすることができるいくつかの簡単なルールがあります。これがあなたがする必要がある2つのステップです:

  1. 状態の数を数えます—これは問題の変化するパラメーターの数に依存します
  2. 各州ごとに行われる作業について考えてください。言い換えると、1つの状態以外のすべてが計算された場合、その最後の状態を計算するためにどのくらいの作業を行う必要がありますか?

この例の問題では、状態の数は| P |です。* | S |、ここで

  • Pはすべての位置のセットです(| P |はPの要素の数を示します)
  • Sはすべての速度のセットです

この問題では、各状態ごとに実行される作業はO(1)です。これは、他のすべての状態を考えると、結果の状態を判別するために3つのサブ問題を調べる必要があるためです。

前のコードで述べたように、| S | は滑走路の長さ(| P |)によって制限されるため、状態の数は| P |²であり、各状態ごとに行われる作業はO(1)であるため、合計時間計算量はO(| P |²)。

しかし、| S |のようです それが本当に| P |だった場合、最初の動きで滑走路全体の長さをジャンプする必要があるため、停止できないことは非常に明白であるため、さらに制限することができます。

それでは、| S |をより厳密に制限する方法を見てみましょう。最大速度をSと呼びましょう。位置0から開始していると仮定します。できるだけ早く停止しようとし、潜在的なスパイクを無視した場合、どれだけ早く停止できますか?

最初の反復では、ゼロでの速度を-1だけ調整することにより、少なくともポイント(S-1)に到達する必要があります。そこから、少なくとも(S-2)ステップ進んでいきます。

長さLの滑走路の場合、以下が成り立つ必要があります。

=>(S-1)+(S-2)+(S-3)+…。+ 1 <L

=> S *(S-1)/ 2 <L

=> S²— S — 2L <0

上記の関数のルーツを見つけた場合、それらは次のようになります。

r1 = 1/2 + sqrt(1/4 + 2L)およびr2 = 1/2 — sqrt(1/4 + 2L)

不平等は次のように書くことができます。

(S — r1)*(S — r2)< ; 0

S> 0およびL> 0に対してS— r2> 0であることを考慮すると、次のものが必要です。

S — 1/2 — sqrt(1/4 + 2L)< ; 0

=> S <1/2 + sqrt(1/4 + 2L)

これが、長さLの滑走路で可能な最高速度です。それよりも速い速度では、スパイクの位置に関係なく、理論的にも停止することはできませんでした。

つまり、合計時間計算量は、次の形式の滑走路Lの長さにのみ依存します。

O(L²)よりも優れているO(L * sqrt(L))

O(L * sqrt(L))は、時間計算量の上限です。

素晴らしい、あなたはそれをやり遂げました!:)

私たちが行った7つのステップは、動的計画問題を体系的に解決するためのフレームワークを提供するはずです。アプローチを完成させるために、さらにいくつかの問題についてこのアプローチを実践することを強くお勧めします。

これがあなたが取ることができるいくつかの次のステップです

  1. 停止点へのパスを見つけようとして、サンプルの問題を拡張します。停止できるかどうかという問題を解決しましたが、最終的に滑走路に沿って停止するための手順も知りたい場合はどうすればよいでしょうか。それを行うために、既存の実装をどのように変更しますか?
  2. メモ化の理解を深め、それが単なる関数の結果キャッシュであることを理解したい場合は、Pythonのデコレータまたは他の言語の同様の概念について読む必要があります。メモ化する関数に対して、一般的にメモ化を実装する方法を考えてください。
  3. 私たちが行った手順に従って、より多くのDPの問題に取り組みます。あなたはいつでもそれらの束をオンラインで見つけることができます(例:LeetCodeまたはGeeksForGeeks)。練習するときは、1つのことを覚えておいてください。アイデアを学び、問題を学ばないでください。アイデアの数は大幅に少なく、征服しやすいスペースであり、より良いサービスを提供します。

これらのアイデアを克服したと感じたら、上級エンジニアからインタビューを受けたRefdashをチェックして、コーディング、アルゴリズム、およびシステム設計に関する詳細なフィードバックを入手してください。

もともとはRefdashブログで公開されました。 Refdashは、エンジニアがGoogle、Facebook、Palantirなどのトップ企業の経験豊富なエンジニアと匿名でインタビューし、詳細なフィードバックを得るのに役立つインタビュープラットフォームです。 Refdashは、エンジニアがスキルと興味に基づいて素晴らしい仕事の機会を見つけるのにも役立ちます。