問題4：ITトレーニング-主要企業の現在の問題と課題

休憩の後、ITトレーニングのリリースを再開します。



IT企業へのインタビューで遭遇する興味深いタスクのセレクションに注目します。定期的なソリューションにより、今後のインタビューに少し準備を整え、体調を整えることができます。

以下は、さまざまな難易度でのGoogleの求職者向けの質問とタスクです。

ご質問

1. 長方形のケーキ
   

   質問：長方形のケーキがすでに切り取られている場合、どのようにして長方形のケーキを2つの等しいピースにカットしますか？ 切断片は、任意のサイズと向きにすることができます。 ストレートカットは1つだけ許可されます。

   
   
   翻訳

   ケーキから長方形のピースがすでに切り取られている場合、長方形のケーキを2つの等しい部分にどのようにカットしますか。 切断片のサイズは任意で、水平または垂直に向けられます。 どの方向でも1つの直線カットのみが許可されます。
   
   
   
2. 強い卵
   

   卵はどれくらい強いですか？
   
   2つの同一の卵があります。 100階建ての建物の前に立って、卵を壊さずに落とすことができる最大の階数はどれくらいかと思うでしょう。 解決策を見つけるために必要な最小試行回数は？

   
   
   翻訳

   2つの同一の卵が与えられます。 100階建ての建物の前に立って、卵が壊れないように落としたときに最上階が何であるかを考えています。 これはどのくらいの最小試行回数で決定できますか？
   
   
   

タスク

1. アナグラム部分文字列
   

   2つの単語が与えられた場合、2番目の単語のサブストリングが単語1のアナグラムでもある場合、trueを返します。
   LGE、GOOGLE => True
   GEO、GOOGLE => False
   

   
   
   翻訳

   2単語が与えられます。 2番目の単語に部分文字列（最初の単語のアナグラム）があるかどうかを調べます。
   LGE、GOOGLE => True
   GEO、GOOGLE => False
   
   
   
2. 最小バス（乗り換え）
   

   市バスの駅情報、たとえばバス番号 1 abcd駅、バス番号で停止します。 cefg駅に2駅停車します。 次に、あなただけが取る必要がある広告 1、したがって1を返します。agは2です。ステーションcで転送する必要があるため、
   別の駅に行くために必要な最低限のバスを尋ねてください。 任意のデータ構造を設計できます。

   
   
   翻訳

   バス停留所のスケジュールは次のとおりです。ルート1-abcd停留所、ルート2-cefgで続きます。 次に、広告を渡すには1つのバスが必要です。g-2つのバスが必要です（駅cで変更します）。
   特定の駅に到達するために必要なバスの最小数を見つけます。 すべてのデータ構造が許可されます。
   
   
   
3. サブアレイの最大量
   

   最大合計のサブ配列
   
   任意の順序で整数（正と負の両方）の配列が与えられます。 最大合計を持つサブ配列を見つける

   
   
   翻訳

   ランダムに並べられた整数の配列（負の数がある場合もあります） 最大量のサブアレイを見つけます。
   
   
   

回答は来週以内に行われます-決定する時間があります。 頑張って

解決策

1. 質問1

   コメントで解決策を正しく見つけました：
   

   最初の問題では、2つの対角線の交点に元のケーキの「重心」を見つけます。 次に、切断されたピースの「重心」も見つけます。 これらの「重心」を通る線に沿ってカットします

   
   
   
   
2. 質問2

   最初に思い浮かぶのは、単純なバストです。 2階のステップで検索。 より一定の間隔で。 ただし、最適なアプローチは、建物の最上階までの階数を減らすことです。これにより、最大14回の試行に対応できます。
   

   等間隔をとる代わりに、フロアの数を前の増分より1つ少なくすることができます。 たとえば、最初に14階で試してみましょう。破損した場合は、解決策を見つけるためにさらに13回試行する必要があります。 壊れていない場合は、フロア27（14 + 13）を試してください。 壊れた場合、解決策を見つけるためにさらに12回の試行が必要です。 したがって、最初の2回の試行と追加の12回の試行は、合計で14回の試行となります。 壊れていない場合は、39（27 + 12）などを試すことができます。 14を初期フロアとして使用すると、14回を超える試行が必要になる前に最大105フロア（14 + 13 + 12 + ... + 1）に到達できます。 100フロアをカバーするだけでよいため、解決策を見つけるには14回の試行で十分です。
   

   
   より詳細な回答に興味がある人のために- コメントの MagnetonBoraは、Igor Kleinerのレッスンを見ることを提案しています。
   
   
   
3. タスク1

   コメントは正しい方法を提案しました：
   

   スライディングウィンドウ。 複雑さO（n + m）追加メモリO（n）

   
   

   bool findSubstrAnagram(string s1, string s2){ if(s1.size() > s2.size()) return false; if(s1 == s2) return true; vector<char> mark_s1(256, 0); vector<char> mark_s2(256, 0); for(char c : s1){ mark_s1[c]++; } int count = 0; for(char c : s2){ if(mark_s2[c] < mark_s1[c]){ count++; mark_s2[c]++; } else{ count = 0; fill(mark_s2.begin(), mark_s2.end(), 0); } if(count == s1.size()) return true; } return false; } 

   
   
   
   
4. タスク2

   alexeykuzmin0は、 BFS01を使用する適切なソリューションを提案しました。
   

   ソリューションで説明されているFord-Bellmanアルゴリズムの代わりにBFS0-1を使用します。 グラフの頂点はルートであり、エッジはルートの交差点です。 初期停止を含むすべてのルートを最初に0に初期化します。 答えは、最終停車地を含む、すべてのルートまでの最短距離です。
   

   
   
   
   
5. タスク3

   このパズルを解く最良の方法は、O（n）時間で実行されるKadaneのアルゴリズムを使用することです。 アイデアは、アレイをスキャンし続け、すべての位置で終了する最大のサブアレイを計算することです。 配列に正の値と負の値が混在している場合、サブ配列には数値の範囲が含まれます。また、配列に負の値しかない場合は、最小の負の値が含まれます。
   

   
   そして、jsの例：
   

    function getMaxSubSum(arr) { var maxSum = arr[0], partialSum = 0; for (var i = 0; i < arr.length; i++) { partialSum += arr[i]; maxSum = Math.max(maxSum, partialSum); if (partialSum < 0) partialSum = 0; } return maxSum; }