11

出典：Googleインタビューの質問

入力内の同一の要素が出力内で最大限に分散されるようにするルーチンを作成しますか?

基本的に、TOTALの広がりが可能な限り最大になるように、同じ要素を配置する必要があります。

例：

Input: {1,1,2,3,2,3}

Possible Output: {1,2,3,1,2,3}  

Total dispersion = Difference between position of 1's + 2's + 3's = 4-1 + 5-2 + 6-3 = 9 .

これに利用できる最適な多項式時間アルゴリズムがあるかどうかは、まったくわかりませ ん。また、この質問以外の詳細は提供されていません。

私が考えたのは、入力内の各要素の周波数を計算し、すべての周波数が使い果たされるまで、一度に個別の要素ごとに出力に配置することです。

私のアプローチがよくわかりません。

あらゆるアプローチ/アイデアの人々。

4

4 に答える 4

4

この単純なアルゴリズムが機能すると思います：

  • 各要素の出現回数を数えます。
  • 新しいリストを作る
  • 複数回出現するすべての要素の 1 つのインスタンスをリストに追加します(各グループ内の順序は関係ありません)。
  • すべての一意の要素の 1 つのインスタンスをリストに追加する
  • 複数回出現するすべての要素の 1 つのインスタンスをリストに追加する
  • 2 回以上出現するすべての要素の 1 つのインスタンスをリストに追加する
  • 3 回以上出現するすべての要素の 1 つのインスタンスをリストに追加する
  • ...

さて、これは直感的に良い広がりを与えません:
for {1, 1, 1, 1, 2, 3, 4}==> {1, 2, 3, 4, 1, 1, 1}
for {1, 1, 1, 2, 2, 2, 3, 4}==>{1, 2, 3, 4, 1, 2, 1, 2}

ただし、提供されているスコアリング機能を考えると、これが最高のスプレッドだと思います。分散スコアは、距離の 2 乗和ではなく距離の合計をカウントするため、補正する大きなギャップが別の場所にある限り、複数の複製を近づけることができます。

平方距離スコアの合計の場合、問題は難しくなります。おそらく、面接の質問は、候補者が採点機能のこの弱点を認識していることにかかっていたのでしょうか?

于 2013-07-27T15:37:09.460 に答える
0

Vorsprung と HugoRune によって提案されたアルゴリズムの python コード:

from collections import Counter, defaultdict

def max_spread(data):
    cnt = Counter()
    for i in data: cnt[i] += 1

    res, num  = [], list(cnt)
    while len(cnt) > 0:
        for i in num:
            if num[i] > 0:
                res.append(i)
                cnt[i] -= 1
            if cnt[i] == 0: del cnt[i]

    return res

def calc_spread(data):
    d = defaultdict()
    for i, v in enumerate(data):
        d.setdefault(v, []).append(i)

    return sum([max(x) - min(x) for _, x in d.items()])
于 2013-07-27T16:19:23.917 に答える
0

HugoRune の答えは、異常なスコアリング関数を利用していますが、実際にはもっとうまくできます: d 個の個別の一意でない値があると仮定すると、ソリューションが最適であるために必要な唯一のことは、出力の最初の d 個の値です。同様に、出力の最後の d 値は、これらの値を任意の順序 (つまり、異なる順序) で構成する必要があります。(これは、一意でないすべての番号の最初と最後のインスタンスの間にすべての一意の番号が表示されることを意味します。)

一意でない番号の最初のコピーの相対的な順序は重要ではありません。同様に、最後のコピーの相対的な順序も重要ではありません。 値 1 と 2 の両方が入力に複数回出現し、最初の段落で指定した条件に従って、位置 i に 1 の最初のコピーがあり、位置 j に 2 の最初のコピーがある解候補を作成したとします。 >私。ここで、これら 2 つの要素を入れ替えるとします。要素 1 は j - i 位置右に押されているため、そのスコアの寄与は j - i だけ低下します。ただし、要素 2 は j - i 位置だけ左に移動しているため、そのスコアへの寄与は j - i だけ増加します。これらは相殺され、合計スコアは変更されません。

現在、要素の任意の順列は、次の方法で要素を交換することによって実現できます: 位置 1 の要素を位置 1 にある要素と交換し、位置 2 に対して同じことを行います。i 番目のステップの後、順列の最初の i 要素は正しいです。すべてのスワップはスコアリング関数を変更せず、順列は一連のスワップにすぎないことを知っているため、すべての置換でもスコアリング関数は変更されません! これは、出力配列の両端の d 要素に当てはまります。

数字の 3 つ以上のコピーが存在する場合、最初と最後のコピーの位置のみがその数字の距離に影響します。中間のものがどこに行くかは問題ではありません。 両端の d 要素の 2 つのブロックの間の要素を「中央」要素と呼びます。それらは、一意の要素と、少なくとも 3 回出現するすべての一意でない要素のいくつかのコピーで構成されます。前と同様に、これらの「中心」要素の順列が一連の交換に対応し、そのような交換が全体のスコアを変更しないことは簡単にわかります (実際、2 つの中心要素を交換すると、これらの要素のいずれかのスコアへの貢献を変更することさえできます)。

これにより、単純な O(nlog n) アルゴリズム (最初のステップでバケット ソートを使用する場合は O(n)) を使用して、長さ n の入力配列 X からソリューション配列 Y を生成します。

  1. 入力配列 X を並べ替えます。
  2. X を 1 回通過して、一意ではない個別の要素の数を数えます。これを d とします。
  3. i、j、k を 0 に設定します。
  4. i < n の間:
    • X[i+1] == X[i] の場合、一意でない要素があります。
      • Y[j] = Y[nj-1] = X[i] に設定します。
      • i を 2 回インクリメントし、j を 1 回インクリメントします。
      • X[i] == X[i-1] の間:
        • Y[d+k] = X[i] を設定します。
        • i と k をインクリメントします。
    • それ以外の場合は、一意の要素があります。
      • Y[d+k] = X[i] を設定します。
      • i と k をインクリメントします。
于 2013-07-27T22:57:18.700 に答える