問題タブ [algorithm]

ユーザーが電話をかけ、電話のキーパッドで確認番号を入力する必要があるアプリケーションに取り組んでいます。

入力した数字が正しいかどうかを検出できるようにしたいと思います。電話システムは有効な番号のリストにアクセスできませんが、代わりにアルゴリズム (クレジット カード番号など) に対して番号を検証します。

要件の一部を次に示します。

• 有効なランダムコードを入力するのは難しいに違いない
• タイプミス（桁の入れ替わり、桁違い）をすると有効なコードを取得するのが難しいに違いありません
• 合理的な数の可能な組み合わせが必要です (1M としましょう)
• ユーザーのエラーを避けるために、コードはできるだけ短くする必要があります

これらの要件を考えると、どのようにそのような数を生成しますか?

編集 ：

@Haaked: ユーザーが電話で入力するため、コードは数値でなければなりません。

@matt b: 最初のステップでは、コードが Web ページに表示されます。2 番目のステップでは、コードを呼び出して入力します。ユーザーの電話番号がわかりません。

フォローアップ : 数値の有効性をチェックするアルゴリズムをいくつか見つけました(この興味深い Google Code プロジェクトを参照してください: checkDigits )。

最初にキーワードのリストが与えられ、次に別の与えられた単語がリストにあるかどうかを答える必要がある、適度に効率的な「キーワード認識アルゴリズム」を実装したいとします。

命令型言語では、キーワードをツリーに格納します（文字ごとに1つのノード）。次に、テストする単語を受け取ったら、ツリーをスキャンして、その単語がキーワードであるかどうかをテストします。

そのようなアルゴリズムが関数型言語でどのようにコーディングされるのかを理解したいと思います。「命令型」アルゴリズムの効率を維持しながら、「ステートレス」プログラミングの利点をどのように得るのでしょうか。毎回再構築したくない場合は、ルックアップ間のどこかにツリーを保存する必要はありませんか？

単語の文を形成する文字の配列が与えられたとき、その中の単語 (文字ではない) の順序を逆にする効率的なアルゴリズムを与えてください。

入力と出力の例:

O(N) 時間と O(1) スペースである必要があります (split()スタックのプッシュ/ポップは許可されません)。

パズルはここから取られます。

一般的なリストから 5 つのランダムな要素を選択する簡単なアルゴリズムが必要です。たとえば、 a から 5 つのランダムな要素を取得したいと思いList<string>ます。

50,000 ページの HTML ページから電話番号を見つける方法は?

Jeff Attwood は、仕事に応募するプログラマー向けに 5 つの質問を投稿しました。

電話スクリーナーの作業を簡素化するために、SDE スクリーニング中に尋ねる必要がある 5 つの重要な質問のリストをまとめました。あなたの候補者が優秀であることを保証するものではありません。

1) コーディング受験者は、C、C++、または Java で、正しい構文で簡単なコードを作成する必要があります。

2) OO 設計候補者は、基本的な OO の概念を定義し、単純な問題をモデル化するためのクラスを考え出す必要があります。

3) スクリプトと正規表現受験者は、50,000 ページの HTML で電話番号を見つける方法を説明する必要があります。

4) データ構造受験者は、最も一般的なデータ構造に関する基本的な知識を示さなければなりません。

5) ビットとバイト受験者は、ビット、バイト、および 2 進数に関する簡単な質問に答えなければなりません。

理解してください: 私がここで探しているのは、これらの領域の 1 つで完全に真空であることです。彼らが少し苦労してから理解すればOKです。ちょっとしたヒントやプロンプトが必要な場合は問題ありません。錆びていても遅くても構いません。あなたが探しているのは、問題の分野についてまったく無知であるか、ひどく混乱している候補者です。

>>> ジェフのオリジナル投稿の全文 <<<

注: Steve Yegge が最初に質問を提起しました。

ここでの作業では、文字列のリストから他の入力文字列に最も近い文字列を見つける必要があることがよくあります。現在、Needleman-Wunsch アルゴリズムを使用しています。アルゴリズムは多くの場合、(最小スコアの設定が低すぎると) 偽陽性を返します。必要なときに (最小スコアが高すぎると) 一致が見つからない場合があり、ほとんどの場合、結果を手で確認する必要があります。他の選択肢を試す必要があると考えました。

アルゴリズムの経験はありますか? アルゴリズムが互いにどのように比較されるか知っていますか?

アドバイスをいただければ幸いです。

PS: 私たちは C# でコーディングしていますが、気にする必要はありません。一般的なアルゴリズムについて質問しています。

あ、すみません言い忘れました。

いいえ、重複データの照合には使用していません。探している文字列のリストがあります。これを検索リストと呼びます。次に、さまざまなソース (RSS フィード、Web サイト、フォーラムなど) からのテキストを処理する必要があります - それらのテキストの一部を抽出し (そのためのルール セット全体がありますが、それは無関係です)、一致する必要があります。検索リストに反対するもの。文字列が search-list 内の文字列の 1 つと一致する場合、さらに処理を行う必要があります (これも無関係です)。

ほとんどの場合、外部ソースから抽出された文字列には余分な単語などが含まれているため、通常の比較は実行できません。

とにかく、重複検出用ではありません。

ここで文字列マッチングに関するいくつかの投稿に気付き、解決したい古い問題を思い出しました。Qwertyキーボードに重点を置いた優れたレーベンシュタインのようなアルゴリズムを持っている人はいますか?

2 つの文字列を比較して、タイプミスを許容したい。レーベンシュタインは問題ありませんが、Qwerty キーボードのキー間の物理的な距離に基づくスペルミスも受け入れたいと思います。つまり、ほとんどのキーボードでは、"y" キーが "z" キーよりも "t" キーの近くに配置されているため、アルゴリズムは "zelephone" よりも "yelephone" を優先する必要があります。

どんな助けでも素晴らしいでしょう...この機能は私のプロジェクトの中心ではないので、もっと生産的なことをしなければならないときに、ネズミの穴にはまりたくありません。

Graphアルゴリズム用のJavaライブラリで良い経験をした人はいますか? 私はJGraphを試してみましたが、問題はありませんでした。Googleにはさまざまなものがあります。人々が実際に製品コードでうまく使用している、または推奨するものはありますか?

明確にするために、グラフ/チャートを生成するライブラリを探しているのではなく、最小スパニング ツリー、クラスカルのアルゴリズム ノード、エッジなどのグラフ アルゴリズムに役立つライブラリを探しています。理想的には、いくつかの優れたアルゴリズム/データを備えたライブラリを探しています。素敵な Java OO API の構造。

軸の最小値と最大値を計算するためのまともなアルゴリズムを持っている人はいますか?

特定のデータ項目セットのグラフを作成するとき、アルゴリズムを指定できるようにしたいと思います。

• セット内の最大 (y) 値
• セット内の最小 (y) 値
• 軸に表示される目盛りの数
• 目盛りとして表示する必要があるオプションの値(例: +ve および -ve 値を表示する場合はゼロ)

アルゴリズムは返す必要があります

• 軸の最大値
• 軸の最小値 (ただし、最大値、間隔サイズ、およびティック数から推測できます)
• 間隔サイズ

ティックは一定の間隔である必要があり、「妥当な」サイズである必要があります (たとえば、1、3、5、場合によっては 2.5 ですが、それ以上の sig figs ではありません)。

オプションの値が存在するとこれが歪められますが、その値がないと、最大の項目が上の 2 つの目盛りの間に表示され、最小の値が下の 2 つの目盛りの間に表示されます。

これは言語にとらわれない質問ですが、C#/.NET ライブラリがあれば、それは素晴らしいことです ;)

2006年に非常に小さな学校を卒業して以来、形が悪く時代遅れのプログラムでした（私は外国人で、当時はこれ以上の学校を知りませんでした）.他の高等概念の基礎となる数学的およびソフトウェアの観点。

つまり、アルゴリズム入門に関する MIT のオープン コースウェアを聞いたり見たりしようとしましたが、コースをよりよく理解するための数学的概念がいくつか欠けていることにすぐに気付きました。

では、優れたソフトウェア エンジニアが知っておくべきコアとなる数学的概念とは何でしょうか? そして、あなたが私に推薦する可能性のある本/サイトは何ですか?