us
BAN USERAlways a trade-off space vs. time:
import java.util.Random;
public class MyRandomChar {
// Assumption: Array is not given as part of the randomChar() -
// "There is an array of characters... "
private final char[] A = { 'a', 'b', 'c' };
private final double[] W = { 0.3, 0.5, 0.2 };
private final int[] lookup;
private int totalLookupValues = 0;
private final Random rand = new Random();
public MyRandomChar() {
// Assumption: Preparation can take O(n) one time:
totalLookupValues = 0;
// Assumption: "... randomChar() called 100 times should return approx. ..."
// Used m = 10 as the resolution factor (can be increased) hence space O(m):
for (double w : W)
totalLookupValues += Math.round(w * 10);
lookup = new int[totalLookupValues];
int lookupIndex = 0;
for (int weightsIndex = 0; weightsIndex < W.length; weightsIndex++) {
for (int weightRepeat = 0; weightRepeat < Math.round(W[weightsIndex] * 10); weightRepeat++)
lookup[lookupIndex++] = weightsIndex;
}
}
public char randomChar() {
// O(1):
return A[lookup[rand.nextInt(totalLookupValues - 1)]];
}
}
- us November 28, 2013