woods
BAN USERString reverse(String s)
{
if (s == null) return null;
if (s.length == 0)
return "";
if (s.length == 1)
return s;
return reverse(s.substring(1)) + s.charAt(0) ;
}
Quick testcase: showing recursive call stack.
Input: hello
ello + h => olleh
llo + e => oll + e
lo + l => oll
o + l => ol
o => return o. stack starts to unwind
> Your function takes input stream of numbers continuously in chunks.
Solution 1: At start of the input stream initialize a bitarray of Max_int.
This should take around 4G/8 ~ 500Megs of memory.
For each integer seen, mark the bit.
At the end of the stream, find the min and max and generate a random number between min and max. Verify that the random number generated is indeed found in the BitArray. repeat until the random number generated is found in the bitrarray.
By generating a random number between min and max, we have increased the sample space. (Not all numbers may be present in the input stream). However, the probability of random number selection should be the same?
Any comments?
> The stream could be very large, and you don't have the memory in disk to store it.
- woods June 02, 2012Clearly the entire input stream cannot be stored on disk.
But do we have memory to store the Integer presence in a bit array (present or not present)? This is not clear in the question...