0

最近、インタビューでこんな質問をされました。私は O(n) 時間で答えましたが、2 回のパスで答えました。また、彼は、URL リストがメモリに収まらない場合に同じことを行う方法を私に尋ねました。どんな助けでも大歓迎です。

4

5 に答える 5

6

すべてがメモリに収まる場合、問題は単純です。2 つのセットを作成し (好みのデータ構造を選択してください)、両方とも最初は空です。1 つは固有の URL を含み、もう 1 つは複数回出現する URL を含みます。URL リストを 1 回スキャンします。各 URL について、一意のセットに存在する場合は、一意のセットから削除し、複数のセットに入れます。それ以外の場合、複数のセットに存在しない場合は、一意のセットに追加します。

セットがメモリに収まらない場合、問題は困難です。O(n) の要件を満たすのは難しくありませんが、「シングル パス」(特にランダム アクセスを除外しているように見える) の要件は厳しいものです。データに何らかの制約がなければ、それは不可能だと思います。セットのサイズ制限を指定してセット アプローチを使用できますが、これはデータの不運な順序付けによって簡単に打ち負かされ、いずれにせよ、一意の要素が存在する場合、その要素を特定の確率 (<100%) でしか見つけることができません。

編集：

大容量ストレージに存在するセット データ構造を設計でき (そのため、メモリに収まるよりも大きくなる可能性があります)、検索、挿入、および削除を O(1) (償却) 時間で実行できる場合は、それをそのまま使用できます。 2番目の問題を解決するための最初のアプローチを持つ構造。おそらく、インタビュアーが探していたのは、URL の UNIQUE インデックスとカウント列を持つデータベースに URL をダンプすることだけでした。

于 2012-07-01T05:47:15.027 に答える
2

データを保持するために Trie 構造を使用することができます。圧縮されているため、共通の URL 部分のメモリの再利用として、メモリの使用量が少なくなります。

ループは次のようになります。

add string s to trie;
check that added string is not finished in existing node
    internal node -> compress path
    leaf node -> delete path
于 2012-07-01T06:52:59.287 に答える
0

「メモリに収まる」場合、次のように 2 つのハッシュ テーブルを使用できます (疑似コード)。

hash-table uniqueTable = <initialization>;
hash-table nonUniqueTable = <initialization>;
for-each url in url-list {
    if (nonUniqueTable.contains(url)) {
        continue;
    }
    else if (uniqueTable.contains(url)) {
        nonUniqueTable.add(url);
        uniqueTable.remove(url);
    }
    else {
        uniqueTable.add(url)
    }
}
if (uniqueTable.size() > 1)
    return uniqueTable.first();
于 2012-07-01T05:46:57.103 に答える
0

Python ベース

あなたはlist-それがどこから「来ている」のかわかりませんが、すでにメモリにある場合は:

L.sort()
from itertools import groupby
for key, vals in groupby(L, lambda L: L):
    if len(vals) == 1:
       print key

それ以外の場合は、ストレージを使用します (おそらく使用):

import sqlite3
db = sqlite3.connect('somefile')
db.execute('create table whatever(key)')

そこにデータを取得し、「select * from any group by key where count(*) = 1)」を実行します

于 2012-07-01T06:26:15.010 に答える
-1

これは実際、インタビューの古典的な質問であり、彼らが期待していた答えは、最初に URL を並べ替えてからバイナリ検索を行うというものでした。メモリに収まらない場合は、ファイルで同じことを行うことができます。

于 2012-07-01T06:31:46.737 に答える