最近のインタビューで、次の質問をされました。
getrnd50()
1から 50 までの乱数を生成する指定されたメソッドを使用して、1 から 100 までの乱数を出力します。各乱数は、ランダムな順序で 1 回だけ印刷する必要があります。他の乱数発生器の使用は許可されておらず、 i は の定義を変更することを許可されていませんでしたgetrnd50()
。
正しい出力を与える次のコードを思いつきました。
import java.util.Random;
public class Test {
public static void main(String[] args) {
int[] rs = new int[100];
int count = 0;
int k;
while (count != 100) {
// I decided to simply multiply the result of `getrnd50()` by 2.
// But since that would generate only even numbers,
k = getrnd50() * 2;
// I decided to randomly subtract 1 from the numbers.
// Which i accomlished as follows.
if (getrnd50() <= 25) // 25 is to half the possibilities.
k--;
// Every number is to be stored in its own unique location
// in the array `rs`, the location is `(number-1)`.
// Every time a number is generated it is checked whether it has
// already been generated. If not, it is saved in its position, printed and
// `count` is incremented.
if (rs[k-1] == 0) {
rs[k-1] = k;
count++;
System.out.print(k + " ");
}
}
}
// This is the method and i am not supposed to touch it.
static int getrnd50() {
Random rand = new Random();
return (1 + rand.nextInt(50));
}
}
そのラウンドでは受け入れられましたが、次のラウンドで面接担当者は、それgetrnd50()
はコストのかかる方法であり、最良のシナリオでも、生成された数値ごとに 2 回呼び出す必要があると私に言いました。つまり、1 ~ 100 の場合は 200 回です。最悪のシナリオでは、それは無限であり、平均的なケースでは数万です。彼は、平均的なケースを大幅に改善するためにコードを最適化するように私に依頼しました。
私がそれを行うことができないことを表明したとき、彼は私にヒントを与えました.
新しい数を生成する際に、生成される数の数を考慮する。例のために。
count
99 になった場合、電話する必要はありませんgetrnd50()
。残りの番号を見つけて印刷するだけです。
私は彼のドリフトを理解していましたが、それがどのように役立つかわからなかったので、明らかに拒否されました. 今、私は答えを知りたいと思っています。助けて!事前にサンクス!
注:数値生成の部分を指摘するだけで長いコードを書くのが面倒だと感じている人がいる場合、残りは簡単です。また、ヒントに従う義務はありません。