random

Problem Write a method to randomly generate a set of m integers from an array of size n Each element must have equal probability of being chosen. Solution This question depends on 2 things: how random number generation works? Fisher yates algorithm or Knuth Shuffle? Now that we have fisher yates algorithm in our quiver, we can solve this problem : let m be the number of elements to select for i = 1; i <= m; i++ pick a random number from 1 to n, call it j swap array$j$ and array $n$ (assuming 1 indexed arrays) n-- public static int$$ chooseNFromM(int$$ array, int m) { if (m > array. [Read More]

Problem Given a number x, less than 100. How will you generate true with probability x/100. So if x = 65, how will you generate true with probability 65/100. You can represent true by 1 and false by 0. Solution We can make use of rand() function to generate a number less than 100 by taking rand()%100. If the number is less than x, you can output true, otherwise you output false. [Read More]

Question Write a method to shuffle a deck of cards. It must be a perfect shuffle – in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect. OR How can you shuffle an array in O(n) time and O(1) space? For example, if input is an array of (1, 2, 3, 4, 5), one of the output can be (5, 4, 3, 2, 1) or (4, 2, 3, 1, 5). [Read More]

Understanding how random number generation (RNG) works In java, lets say you wants to generate random number between i to j e.g. [ i,j ) excluding upper limit. One standard pattern for accomplishing this is: Min + (int)(Math.random() \* ((Max - Min) + 1)) The java Math library function Math.random() generates a double value in the range [0,1). Notice this range does not include the 1. In order to get a specific range of values first you need to multiply by the magnitude of the range of values you want covered. [Read More]