CareerCup

Pick an index at random and check if the element there is non-null. Keep re-picking indexes at random until you get a non-null element. This approach makes no assumptions about the distribution of the data and has an expected running time of O(N/K) if there are K non-null elements in the array, which is the best you can hope for if you have no information about how elements are distributed.

The algorithm as stated above is unbounded in terms of worst-case (as opposed to expected) time, but that can be remedied by adding a condition that if we fail to find a non-null element after n steps, we will do a linear scan of the array to find all the non-null values, and pick randomly from that list. This change caps the algorithm at O(n) time. Since the linear-time scan is only done when O(n) time has already been used anyway, the bounded algorithm is slower than the unbounded one by at most a constant factor for any input. It is therefore O(N/K) expected time and O(N) worst-case time.

* What is implied by 10million? Doesn't look large to me to hold in memory - only 40MB.
* Can I modify the array?
If so, perform binary search until you find a non-null element, then swap out that element with central-most 'null' element in the array. Then return it.

The modifiability and the swap step is so that over time you collect non-null elements near center of the array, gradually making hunt more efficient and perhaps seize to do swap step eventually - say after about (10million/# non-nulls) calls to the method.

An alternative solution is to iterate through the array to filter out the null elements. You can then just choose an element at random from the filtered array.

This has a time complexity of O(n) and a space complexity of O(n). However, if the array does not change regularly, you only need to do the filter stage once ( O(n) ) meaning the select method is constant time.

For methods where the space matters, the array changes regularly or the method is only called once, my other answer is better (as it is constant space and linear time).

Use HashSet set=new HashSet();
and then add all the array elements to a Set....... There will be only one null value in this set...

and then select any random number from that set by using set to array conversion....

Create multiple threads, each get to search a segment of an array and look up from random position and direction, if not found switch direction starting at the same random position. When one thread finds a value, it returns and interrupts other threads.

randomly add random numbers until we get a non null value.

public static Object randomElement(Object [] arr) {
	Random rand = new Random();
	int starting = rand.nextInt(arr.length);
		
	for(int i = starting, count = 0; count < arr.length; i = ++i % arr.length, count++) {
		if(arr[i] != null) {
			return arr[i];
		}
	}
	return null; // All elements are null
}

To remove the non-null elements , you don't need extra space

int i;
int j =0;
for (i = 0;i <n;i++)
{
if(a[i]!=NULL) a[j++] = a[i];
}

In O(n) time, and without using extra space, you've reduced the search space to j elements, then you can probably use linear search . O(n) time,O(1) space




}

To remove the non-null elements , you don't need extra space

int i;
int j =0;
for (i = 0;i <n;i++)
{
if(a[i]!=NULL) a[j++] = a[i];
}

In O(n) time, and without using extra space, you've reduced the search space to j elements, then you can probably use linear search . O(n) time,O(1) space




}

If the numbers in given array are randomly distributed, without any prior information on distribution type, then simple linear scan is good enough and would be equally likely to find non-null as would picking random index.
It is because, randomizing an already random array doesn't add any benefit.

So, in this problem, we have a sparse matrix with mostly nulls.
Are there any efficient algorithms for finding elements in sparse matrices?

Also, I would imagine that there is a very elegant solution using some C hackery.

So we have a sparse matrix, with mostly nulls.
Are there any efficient algorithms for finding elements in sparse matrices?

Also, I would imagine that there is a very elegant solution using some C hackery.

A simple (and quick, O(n) ) answer is to choose a random start position then linear search to find a non-null element.

public static int randomElement(Object[] a, int start, int end) {
    int offset = (new Random()).nextInt(end - start);
    for (int counter = 0; counter < end - start; counter++) {
      // i is the start + counter + offset, but looped such that start <= i < end
      int i = start + ((counter + offset) % (end - start));
      if (a[i] != null) {
        return i;
      }
    }
    // Return -1 if all elements are null
    return -1;
  }

This will be fine if the elements are evenly distributed, but if they are grouped, the element at the start of the group will be returned more often. For example, in the array [null, null, null, foo, bar], foo will be returned more often than bar.

I don't like this question.
1) Situation is stupid. Why would someone who wants this query allow such an array to be built?
2) We don't know what process created the 10million element array (i.e., if we can assume it was a uniform random process, then we can scan to the first non-null element an return it) How many such queries will be performed? This, along with other considerations, will determine if preprocessing makes sense or not.
3) Why would