問題タブ [data-structures]

リンクされたリストにサイクルがあるかどうかを判断するための最良の (停止) アルゴリズムは何ですか?

[編集] 時間と空間の両方の漸近的複雑度の分析は、答えをよりよく比較できるようになるでしょう。

[編集] 元の質問は、outdegree > 1 のノードに対処することではありませんでしたが、それについていくつかの話があります。その質問は、「有向グラフでサイクルを検出するための最良のアルゴリズム」の行に沿っています。

私たちが取り組んでいるプロジェクトには、SO のものと同様の「評価」システムが必要です。ただし、私たちの場合、賛成票で「タグ付け」する必要がある複数のエンティティがあります（増分のように、賛成票のみで、反対票を投じることはありません）。エンティティの種類に関係なく、評価の高い順にすべてのエンティティを表示する必要がある場合があり、基本的には結果セットを混ぜ合わせていると思います。柔軟でスケーラブルであるように、これを実装するためにどのデータ構造/アルゴリズムを使用していますか?

数千万ビットのビット配列を作成する情報検索アプリケーションがあります。配列内の「セット」ビットの数は、すべてクリアからすべてセットまで、大きく異なります。現在、私は単純なビット配列（java.util.BitSet）を使用しているので、各ビット配列は数メガバイトかかります。

私の計画は、最初のNビットのカーディナリティを調べてから、残りのデータ構造に使用するデータ構造を決定することです。明らかに、一部のデータ構造は非常にスパースなビット配列に適していますが、他のデータ構造はビットの約半分が設定されている場合に適しています（ほとんどのビットが設定されている場合、否定を使用してスパースなゼロのセットとして扱うことができます）。

• どの構造がそれぞれの極端に適しているでしょうか？
• 真ん中に何かありますか？

ここにいくつかの制約またはヒントがあります：

1. ビットは1回だけ、インデックス順に設定されます。
2. 100％の精度が必要なので、ブルームフィルターのようなものでは不十分です。
3. セットが構築された後、「セット」ビットを効率的に反復できる必要があります。
4. ビットはランダムに分散されるため、ランレングスエンコーディングアルゴリズムは、ビットインデックスの単純なリストよりもはるかに優れているとは限りません。
5. メモリ使用率を最適化しようとしていますが、速度にはまだある程度の重みがあります。

オープンソースのJava実装を備えたものは役に立ちますが、厳密には必要ではありません。ファンダメンタルズにもっと興味があります。

私のデータベースには、多対多の関係を持つ次のテーブルがあります。これは、各メイン テーブルの主キーへの外部キーを持つ接続テーブルによって表されます。

• ウィジェット: WidgetID (PK)、タイトル、価格
• ユーザー: UserID (PK)、FirstName、LastName

各ユーザー ウィジェットの組み合わせは一意であると想定します。データ関係を定義する接続テーブルを構築する方法について、次の 2 つのオプションがあります。

1. UserWidgets1: UserWidgetID (PK)、WidgetID (FK)、UserID (FK)
2. UserWidgets2: WidgetID (PK、FK)、UserID (PK、FK)

オプション 1 には、主キーの列が 1 つあります。ただし、テーブルに格納される唯一のデータは 2 つのプライマリ テーブル間のリレーションシップであり、このリレーションシップ自体が一意のキーを形成できるため、これは不要に思えます。したがって、2 列の主キーを持つオプション 2 につながりますが、オプション 1 が持つ 1 列の一意の識別子が失われます。オプションで、2 列の一意のインデックス (WidgetID、UserID) を最初のテーブルに追加することもできます。

UserWidgets の多対多テーブルを構築するために、パフォーマンスに関して 2 つの実際の違い、または一方のアプローチを他方より優先する理由はありますか?

確かに、XML は非常に便利ですが、非常に冗長になる可能性があります。どのような代替手段があり、それらは特定の目的に特化していますか? コンテンツを簡単に調べるためのライブラリ サポートは、大きなプラス ポイントです。

アプリケーションとデータベース間の通信に使用している特定の方法/アプリケーションは何ですか? ストアド プロシージャを使用したカスタム コードですか? サブソニック？nHibernate? エンティティ フレームワーク? リンク？

基本クラス ライブラリの実装を使用せずに、C# で次のデータ構造を実装する方法を知りたいです。

• リンクされたリスト
• ハッシュ表
• 二分探索木
• 赤黒の木
• Bツリー
• 二項ヒープ
• フィボナッチヒープ

そして、人々が考えることができる他の基本的なデータ構造!

これらのデータ構造の理解を深めたいので興味があります。インターネットに出回っている典型的な C の例ではなく、C# のバージョンを参照してください。

複数の場所から呼び出したい Linq クエリがあります。

メソッドを作成し、このコードをその中に入れて、それを呼び出すにはどうすればよいですか?

候補者のスクリーニング プロセスで効果的だと思われる単純なアルゴリズムまたはデータ構造関連の「ホワイト ボード」の問題は何ですか?

問題解決スキルを検証するために使用する単純なものがいくつかあります。これらは簡単に表現できますが、いくつかのヒューリスティックを適用する機会があります。

私がジュニア開発者に使用する基本の 1 つは、次のとおりです。

一連の単語 (文) を含む文字列を受け取り、それらの単語を X 桁右に回転させる C# メソッドを作成します。文の最後の位置にある単語が回転されると、結果の文字列の先頭に表示されるはずです。

候補者がこの質問に答えるとき、問題を解決するために利用できる .NET データ構造とメソッド (string.Join、string.Split、List など) を確認します。また、最適化の特殊なケースを特定するためにそれらを探します。単語をローテーションする必要がある回数は、実際には X ではなく、単語の X % の数です。

候補者との面接に使用するホワイト ボードの問題と、回答に求めるものは何ですか (実際の回答を投稿する必要はありません)。

リンクリストをMySQLデータベースに保存して、挿入が簡単になり（つまり、毎回たくさんのインデックスを再作成する必要がない）、リストを順番に簡単に引き出すことができるようにするための最良の方法は何ですか？