You are given a method
int getRandom(int n){
return [0,n)
}
please write a special get random method returns a number not in a given array.
int getSpecialRandom(int n, int[] array){
}
public class Solution {
private static final int NOT_FOUND = -1;
public int getSpecialRandom(int n, int[] array) {
if (array == null || array.length == 0 || n < 0) {
return NOT_FOUND;
}
byte[] bitVectorOfInts = createBitVectorOfInts(array);
int numberOfMissingInts = getNumberOfMissingInts(n, bitVectorOfInts);
if (numberOfMissingInts == 0) {
return NOT_FOUND;
}
int randomIndex = getRandom(numberOfMissingInts); //Provided method
return getRandomValue(randomIndex, bitVectorOfInts);
}
private byte[] createBitVectorOfInts(int[] array) {
long totalSize = ((long) Integer.MAX_VALUE) + 1;
byte[] bitVectorOfInts = new byte[(int) (totalSize / Byte.SIZE)];
for (int number : array) {
bitVectorOfInts[number / Byte.SIZE] |= 1 << (number % Byte.SIZE);
}
return bitVectorOfInts;
}
private int getNumberOfMissingInts(int exclusiveTop, byte[] bitInts) {
int numberOfMissingInts = 0;
int index = 0;
for (int i = 0; i < bitInts.length; i++) {
for (int j = 0; j < Byte.SIZE; j++) {
if (index >= exclusiveTop) {
return numberOfMissingInts;
}
if ((bitInts[i] & (1 << j)) == 0) {
numberOfMissingInts++;
}
index++;
}
}
return numberOfMissingInts;
}
private int getRandomValue(int randomIndex, byte[] bitVectorOfInts) {
int index = 0;
for (int i = 0; i < bitVectorOfInts.length; i++) {
for (int j = 0; j < Byte.SIZE; j++) {
int intBlock = bitVectorOfInts[i];
if ((intBlock & (1 << j)) == 0) {
if (index == randomIndex) {
return i * Byte.SIZE + j;
}
index++;
}
}
}
return NOT_FOUND;
}
}
The idea is -
Put all the unique numbers of the array in a set. Then start from 0 (or Integer.MIN_VALUE
as is the case) till just one more than the length of the array. Why array.length + 1
? Because of Pigeonhole Principle. If array has only n
elements, I need to find at maximum, n + 1
elements before I come across an element I haven't found previously in the set.
public int getSpecialRandom(int n, int[] array){
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < array.length; i++){
set.add(array[i]);
}
for(int i = 0; i < array.length + 1; i++){
if(!set.contains(i))
return i;
}
return 0;
}
Please let me know how I can format the code better. This is my first time posting on this forum
@pratik.joshi.56808 Thank you for posting a solution! However, the question implies (although worded in an unclear way) that:
Your code, unfortunately, does not satisfy the above requirements. It only returns "the smallest element that is not in the set", which is not a random number.
You may want to consider an alternative solution.
@riccardo The problem of my solution is that if array contains all the lements in the target range it will get stuck in a loop; if the array contains most of the elements it would get pretty slow.
from array import array
from random import randint
def special_random(n, nums):
if len(nums) == n:
return None
nums = [num
for num in range(n)
if num nor in set(nums)]
return nums[randint(0, len(nums) - 1)]
@needCoffee I am not clear with the question. The int we random get, does it have a range? like [0, n)?
@user913 Yes. It should be in the rang from 0(inclusive) to n(exclusive). But the getSpecialRandom should make sure the returning number is not in the given array.
@needCoffee Thank you, now I am clear. Some other questions: is the given array fixed? are we going to use the getSpecialRandom() a lot?
@user913 Yes. The given array is fixed. I did not get a chance to ask if "getSpecialRandom() " will be called a lot though.
@needCoffee Thanks, now its more clear :) my first thought, is to build a hashmap, with key: [0, N - ParticularArray.length()) (ParticularArray has no duplicates?), value: all the numbers not in ParticularArray. After this it is O(1) to getSpecialRandom().
To build the hashmap, first sort ParticularArray low to high, which is log(length)*length.
Then build 2 pointers, A from 1~N, B from left of ParticularArray to right. which is N.
@user913 I think that might work. It would be nice if you can show your code. Thanks.
int getSpecialRandom(int n, int[] array){
Arrays.sort(array);
int left, right, hashIndex;
HashMap hashMap = new HashMap();
right = 0;
hashIndex = 0;
for(left = 0; left < n; ++left) {
if (left == array[right])
++right;
else
hashMap.put(hashIndex++, left);
}
Random ran = new Random();
return (int) hashMap.get(ran.nextInt(n - array.length));
}