Given a number x, less than 100. How will you generate true with probability x/100.

 Posted on May 6, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

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]
kodeknight  probability  random  maths 

How many time function gets called?

 Posted on May 6, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Consider the function below: void foo1() { if(A < B) Then { } else if(C < D) then foo2() } How many time foo2 () would get called given A < B 25% of the times and C < D 75% of the times and foo1 () is called 5000 times Solution This is the question of basic probability. As foo2() occurs in 2nd branch of if else, the probability of it being called is . [Read More]
Adobe  kodeknight  probability  maths 

One shot or at least two shots in three games?

 Posted on March 30, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem: You have a basketball hoop and someone says that you can play 1 of 2 games. Game #1: You get one shot to make the hoop. Game #2: You get three shots and you have to make 2 of 3 shots. If p is the probability of making a particular shot, for which values of p should you pick one game or the other? Solution:  For game #1, you have probability p of winning. [Read More]
kodeknight  brainteaser  Mathematical  probability  CrackingTheCodingInterview 

Shuffle a deck of cards perfectly

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

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]
kodeknight  probability  shuffle  array  CrackingTheCodingInterview  random 

The Ant Collision Problem

 Posted on October 8, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem : There are three ants on different vertices of a equilateral triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon.  Solution : Note that equilateral has nothing to do with how they will collide. Also, ants are allowed to move on the sides only. [Read More]
kodeknight  brainteaser  Mathematical  probability  CrackingTheCodingInterview 

Random number generation

 Posted on December 7, 2009  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

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]
kodeknight  probability  shuffle  random 

Red marbles, blue marbles

 Posted on September 18, 2009  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem You have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. (when picking, you’ll first randomly pick a jar, and then randomly pick a marble out of that jar) you can arrange the marbles however you like, but each marble must be in a jar. [Read More]
kodeknight  brainteaser  probability  Puzzles