Ant and Spider Problem

Given a cube. A ant is placed in a corner and cannot move. A spider starts from the opposite corner, and can move along cube edges in any direction (x,y,z) with probablity 1/3. What is the expected number of steps for this spider to get to the ant?

Let x represent the expected number of moves it takes to reach the ant when the spider is one move away (i.e., at any one of the three vertices of the cube adjacent to the ant). Let y represent the expected number of moves it takes to reach the ant when the spider is two moves away, and let z represent the expected number of moves it takes to reach the ant when the spider is three moves away (at the opposite vertex on the cube).

Then z = 1 + y, since after the first move, the spider will be one move away. From this point, there is a (2/3) chance that the spider will move to a vertex adjacent to the ant and there is a (1/3) chance he will move back to his starting position, Thus, y = 1 + (2/3)x + (1/3)z.

Similarly, x = 1 + (1/3)(0) + (2/3)(y). This system of 3 equations with 3 unknowns has solution z=10, y=9, and x=7. So, it will take 10 steps to reach the ant, on average, from the spider's initial position.

7 Bucket and Poison Problem

There are 7 buckets with water, and one of them is poisoned. You have infinite number of flies, and if you put a fly in poisonous bucket, it will take seven days to die. You need to send your friend a non-poisonous bucket in 1 week, and also you need to find out which bucket is poisoned. How many least number of flies you need to it? and how do you do it?

1) One answer would be, You need one fly for this.

How?  You put the fly in any one of the bucket, and if it dies in one week then it is the poisonous one, and send any one of the other 6 to your friend, and if fly does not die, then its non-poisonous, and you need to send this to your friend and since you have sent to your friend in one week, now take your time and repeat to find out which has the poison with the same fly.

2) Since first answer may be ridiculous, the second answer would be using 3 flies.

How? You need to number the buckets from 1 to 7 in binary and then assign one bit for each flies, and dip the fly in those buckets which has the corresponding bit set in the bucket number in binary, after seven days, if the fly dies consider it as 1 otherwise 0, and get the binary number for bucket which contains the poison.

Classic 25 Horse Problem

Classic 25 horse problem,
25 Horses,
Have a 5 horse track,
No stopwatch,
How many races are required to determine the 3 fastest horses?

Answer : 7 Races

And here goes why? 

1. we have 5 races for 25 horses that 5 horses on a team, define each team as a, b, c, d, e.
2. carry a best horse race for each team first place, define them as a.1,b.1,c.1,d.1,e.1
3. assume prior best horse race 's top 3 places are a.1 b.1 c.1 , so we know the fastest horse is a.1
4. we only need to take last race to know who are second and third quickest horse.
5. The horses that participate in this race are b.1 b.2 a.2 a.3 c.1 , this race 's top 2 places are 2nd and 3rd quickest horses

Search two numbers from array to make a sum

You have a array of random numbers and you are given a number k. Find the 2 elements in the array which sum up to k.

e.g: If my array is {2,5,3,1,8,7,5,4} and k=6.

Then 2 numbers that sum up to 6 are 5 and 1.

step 1: sort the array //O(n.log(n))

arr=2,5,3,1,8,7,5,4 --> 1,2,3,4,5,5,7,8

//size=8

step 2:

i=0, j=7

if a[i]+a[j]==K //done

if a[i]+a[j] > K //j--

if a[i]+a[j] < K //i++

repeat step2, till it reaches mid point //O(n)

Probability

Probability question: Persons A and B go shopping together. Say person A spent X amount of money and B Y. What is the probability that the sum total of their purchases [i.e. X+Y] has 0 cents [i.e. is a whole number]. ?

Answer : The person A can have cents in the range of 0 to 99, and same with the case B. Thus they have 100 cases each, and total number of cases is 100x100. Out of them the cases of our interest is (0, 0) (1,99), (2, 98), (3, 97) ... (99. 1) is 100. So the probability is 100/10000 = 1/100.