最近出演したインタビューで質問されました。この問題を解決できませんでした。アルゴリズム設計に関心のある人は、この問題を好むかもしれません。
実数 S の配列が与えられた場合、|x+y| を最小化する S 内の数値 x&y のペアを見つけます。同じアルゴリズムは、O(nlogn) で実行するように設計する必要があります。
これに対する解決策が見つかりませんでした。この問題の解決策を教えてください。どんな提案でも大歓迎です。
質問する
468 次
2 に答える
4
数字を並べ替えます。各要素 x に対して、-x のバイナリ検索を実行します。|x+y| を最小化する最も近い数 y を取得します。
注: 2 番目の部分を最適化することもできます。最初と最後の要素のインデックスから始めます: i=0、j=n-1。反復ごとに合計を計算し、最小合計を更新し、合計が <0 の場合は i を増やし、合計が 0 の場合は j を減らします。
于 2013-04-24T19:00:44.580 に答える
1
インタビュアーの質問、またはあなたの言い直しには、2 つの点で欠けているように思われます。
1) 実数をコンピュータで表現するのは非常に困難です。それらは、シンボリック形式、または浮動小数点としてのサブセット、および実数のサブセット (整数など) で表すことができます。
2) Mod は 2 つの引数を取ります。それらのステートメントは、mod(x,y) ではなく mod(x+y) を最小化することです。
これは、問題の記述が間違っていることに異議を唱えるために設計されたインタビューの問題でしたか?
ウィキペディアでは、"mod" を次のように定義しています。および「ユークリッド除算」として「算術では、ユークリッド除算は、商と剰余を生成する2つの整数の除算の従来のプロセスです。」
実数の「mod」が意味をなさないというさらなる情報源: http://www.abstractmath.org/MM/MMNumberTheory.htm
問題が O(nlogn) で mod(x,y) を最小化する整数の配列として定義されている場合、扱いやすいようです。配列をソートし、すべての要素に適用します --- 基本的に --- すべてのペアのバイナリ検索にひねりを加えます。mod 空間でのバイナリ検索の実行は、読者に任されていると言う人もいるでしょう。
候補者がその質問に疑問を呈する勇気を持っているかどうかを調べるために、同じように使用するインタビューの質問がいくつかあります。この質問には、実数と実数に対する mod の考え方に疑問を呈し、扱いやすい問題 (かなり伝統的な検索データ構造の問題) を解決するという、両方の要素が含まれている可能性があります。
私がこれらの質問をするとき、最初の部分は一種の「落とし穴」の質問になる可能性があります。私は彼らにその問題について数分間困惑させてから、その問題を扱いやすい問題として再提示します。一緒にインタビュー。
于 2013-04-24T19:09:11.973 に答える