疎結合クラスターのコードに取り組んでいます。ジョブ中に最適なパフォーマンスを実現するために、子が出入りするたびにクラスターにデータを再マッピングさせます。これは最終的にはオプションになりますが、現時点ではデフォルトでデータ バランシングを実行します。私のバランス調整は基本的に、各子がマシンごとの平均ファイル数に 1 を加えた数を超えないようにすることです。除算がきれいでない場合、プラス 1 は残りの部分です。そして、残りは常に子の数よりも少ないため [0 の場合を除きますが、それを除外できます]、バランス調整後の子は最大で avg + 1 になります。

私のアルゴリズムが O(n!) であることに気付くまでは、すべて問題ないように見えます。子供のリストを下に移動し、残りの平均を調べます。誰が多すぎて誰が少なすぎますか。多すぎるリストの各子供について、リストを調べて、少なすぎる子供に送信します。

これに対するより良い解決策はありますか？あるに違いないと感じます。

編集:これは、O(n!)をどのように導出したかを示す擬似コードです:

編集：O（n ^ 2）。Foreach n、n => n*n => n^2。今朝はコーヒーが足りなかったみたい！;)

将来的には、より柔軟で回復力のある分散方法 [重みとヒューリスティックス] に移行したいと考えていますが、今のところ、データの均一な分散が機能しています。

Reddit でこの質問を見ましたが、肯定的な解決策は提示されていませんでした。ここで質問するのに最適な質問だと思いました。これは、インタビューの質問に関するスレッドにありました。

サイズ m の int 配列を取り、配列が n...n+m-1 の数値、その範囲のすべての数値、およびその範囲の数値のみで構成されている場合に (True/False) を返すメソッドを作成します。配列がソートされる保証はありません。(たとえば、{2,3,4} は true を返します。{1,3,1} は false を返し、{1,2,4} は false を返します。

これに関して私が抱えていた問題は、インタビュアーが最適化 (より高速な O(n)、より少ないメモリなど) を私に求め続け、一定量のメモリー。それを理解したことがありません。

解決策とともに、配列に一意のアイテムが含まれていると想定しているかどうかを示してください。また、ソリューションがシーケンスが 1 から始まると想定しているかどうかも示してください。

編集:私は今、重複を処理する線形の時間と一定の空間アルゴリズムが存在しないという意見です。誰でもこれを確認できますか？

重複の問題は、O(n) 時間、O(1) 空間で配列に重複が含まれているかどうかを確認するテストに要約されます。これができれば、最初に簡単にテストできます。重複がない場合は、投稿されたアルゴリズムを実行します。では、O(n) 時間 O(1) 空間で重複をテストできますか?

すべての Big-O 表記のマスター リストはありますか? データ構造、アルゴリズム、それぞれに対して実行される操作、平均的なケース、最悪のケースなど。