15

私は長年潜伏しており、Google のインタビューを受けたところ、次のような質問を受けました。

さまざまなアーティストがロイヤル アルバート ホールでの演奏を希望しており、あなたは彼らのコンサートのスケジュールを立てる責任があります。ホールでの演奏のリクエストは、先着順で対応されます。1日1回の公演のみ可能で、5日以内にコンサートを開催することはできません。

要求された時間 d が不可能である場合 (つまり、すでに予定されているパフォーマンスから 5 日以内)、次の利用可能な日 d2 (d2 > d) を見つけるための O(log n) 時間アルゴリズムを与えます。

解き方がわからなかったのですが、インタビューが終わった今、解き方を知りたくてたまりません。皆さんのほとんどがどれほど賢いかを知っているので、ここで手を差し伸べてもらえないかと思っていました。これは宿題などではありません。将来のインタビューのためにそれを解決する方法を学びたいだけです. フォローアップの質問をしようとしましたが、彼は私があなたに言えるのはそれだけだと言いました.

4

8 に答える 8

9

利用可能な日付の間隔の通常の二分探索木が必要です。d を含む間隔を検索するだけです。存在しない場合は、次の (順番に) 検索が停止したポイントまでの間隔をとります。

注: 連続する間隔は、1 つのノードに融合する必要があります。例: available-dates 間隔 {2 - 15} および {16 - 23} は、{2 - 23} になる必要があります。これは、コンサートの予約がキャンセルされた場合に発生する可能性があります。

または、連続する利用不可の間隔が融合されている場合は、代わりに利用不可の日付のツリーを使用できます。

于 2013-02-28T04:55:16.070 に答える
4

予定されているコンサートを二分探索ツリーに格納し、二分探索を実行して実行可能な解決策を見つけます。

このようなもの：

FindDateAfter(tree, x):
  n = tree.root
  if n.date < x 
    n = FindDateAfter(n.right, x)
  else if n.date > x and n.left.date < x
    return n
  return FindDateAfter(n.left, x)

FindGoodDay(tree, x):
  n = FindDateAfter(tree, x)
  while (n.date + 10 < n.right.date)
    n = FindDateAfter(n, n.date + 5)
  return n.date + 5
于 2013-02-28T02:27:35.743 に答える
0

レベル 1 ですべてのスケジュールの詳細が利用可能であるとします。レベル 2 で 16 日間のグループ スケジュール。レベル 3 でグループ 16 レベル 2 ステータス。レベル 4 でグループ 16 レベル 3 ステータス。拡張する日数に応じて、レベルを上げます。

上位レベルから検索し、最後にバイナリ検索を実行します。

于 2014-08-09T20:12:45.183 に答える
0

上でも述べましたが、基本的には二分木でシンプルに。二分木には log N の複雑さがあることを知っています。したがって、どのアルゴリズムを使用する必要があるかは既にわかっています。必要なのは、ツリー ノード構造を考え出し、バイナリ ツリー挿入アルゴリズムを使用して次に利用可能な日付を見つけることだけです。 5 日間のブロック期間の日付)。ここでも簡単にするために、2 つの日付属性にタイムスタンプを使用します。root = null の初期条件で二分木順序挿入アルゴリズムを使用して、次に利用可能な日付を見つけるのは簡単です。

于 2015-03-16T06:51:36.490 に答える
0

漸近的複雑さ:- 入力が大きくなるにつれてランタイムが変化することを意味します。入力文字列「abcd」があるとします。ここでは、各文字をトラバースしてその長さを見つけます。したがって、かかる時間は、n no of char のように、文字列内の文字数に比例します。したがって、O(n)。しかし、文字列「abcd」の長さを変数に入れると、文字列の長さに関係なく、変数 len を見ることで文字列の長さを見つけることができます。(長さ = 4)。例: 23 を返します。入力内容に関係なく、出力は 23 のままです。したがって、複雑さは O(1) です。したがって、プログラムは入力サイズに対して一定の時間で実行されます。O(log n) の場合 - 操作は対数ステップで行われます。

https://drive.google.com/file/d/0B7eUOnXKVyeERzdPUE8wYWFQZlk/view?usp=sharing

上記リンクの画像をご覧ください。ここに折れ線（対数線）が見えます。ここで、小さい入力の場合、曲がった線でわかるように所要時間が短いため、O(log n) 表記が適切に機能すると言えますが、入力が大きくなると線形表記、つまり O(n) の方が優れた方法と見なされます。また、見られる最良のシナリオと最悪のシナリオもあります。上記の例のように。

アルゴリズムについては、このチートを参照することもできます: http://bigocheatsheet.com/

于 2014-12-14T20:34:01.197 に答える
0

年間、四半期、および月ごとに使用された宿泊数を保存します。無料宿泊を見つけるには、満室ではない最初の年を見つけ、次にその年の四半期、次に月を見つけます。次に、その月の各夜を確認します。

暦体系の不規則性はこれを少しトリッキーにするので、年と月を使用する代わりに、4 夜を「月」、16 ​​夜を「四半期」などの単位のアイデアを適用できます。

于 2013-02-28T06:55:43.203 に答える
-1

Union-Find を使用してみませんか? 各コンサート日 + 次の 5 日間を 1 つのセットの一部としてグループ化し、特定の日に FIND を実行すると、次のコンサート日となる次のセット ID が返されます。

ツリーを使用して実装すると、O(log n) 時間の複雑さが得られます。

于 2014-07-28T22:40:15.253 に答える