amazon - 整数のストリームで最大の要素を見つけます

Question

王様がいます。ある日、息子のb'dayに、彼は息子と結婚するために王国で最も美しい女の子を見つけることにしました。同じように、彼は王国のすべての女の子を呼びます。すべての女の子は列に並んで配置され、呼び出し時に王の前に提示されます。王は女の子を飼うか、それを追い払うことができます。一度女の子が送られると、王の前に提示するために再び呼び出すことはできません。王が可能な限り最大の美しい少女を選択するように戦略を立てます。必ずしも最も美しいとは限りませんが、彼が選択できる最大のものです。

問題は、より単純なステートメントに単純に減らすことができます。整数のストリームが来るとすると、どのようにして最大の要素を選択できますか。現時点では、整数は1つしかなく、将来の情報はありません。

Answer 1

参照:秘書問題

Answer 2

ミッチヌルが言ったことに付け加えます。この問題を決定的に解決することはできません。この問題の解決策は確率的です。それを証明するには、最も美しいものが最後になる可能性があると単純に仮定してください.

この問題について私が知っているすべての解決策は、女の子の数である N に依存します。これは多くのシナリオでは実用的ではありません。

この問題は、面接中に簡単に解決することはできません。簡単には見つけられない素晴らしい数学のトリックがいくつかあります。