Cuboidal boxes

You are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other.
For example:
If Box A has LBH as 7 8 9
If Box B has LBH as 5 6 8
If Box C has LBH as 5 8 7
If Box D has LBH as 4 4 4
then answer is A,B,D
A box can fit into another only and only if all dimensions of that is
less than the bigger box. Also Rotation of boxes is not possible.
Answer:
I think this is a modification of longest increasing subsequence problem . First , sort by length then find the longest increasing subsequence by width. Now, in this solution find longest increasing subsequence by height . This would be the answer to this question.

Children in a country

In a country in which people only want boys every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

Ans:
The possibile sequence and the respective probabilty of new born can be:
B - 1/2
GB - 1/2*1/2
GGB - 1/2*1/2*1/2
GGGB - 1/2*1/2*1/2*1/2
...
...
After Summing it up. Total Number of Boys is: 1/2 + 1/2*1/2 + 1/2*1/2*1/2 + ... = 1 On the same lines, Total number of Girls is: 0 + 1/2*1/2 + 2 * 1/2*1/2*1/2 + 3 * 1/2*1/2*1/2 + ... Which also, give 1 on summing up.
Answer is 50/50

Medals puzzle

In a sports contest there were m medals awarded on n successive days (n > 1).
1. On the first day 1 medal and 1/7 of the remaining m - 1 medals were awarded.
2. On the second day 2 medals and 1/7 of the now remaining medals was  awarded; and so on.
3. On the nth and last day, the remaining n medals were awarded.

How many days did the contest last, and how many medals were awarded  altogether?


Total 36 medals were awarded and the contest was for 6 days.
On day 1: Medals awarded = (1 + 35/7) = 6 : Remaining 30 medals
On day 2: Medals awarded = (2 + 28/7) = 6 : Remaining 24 medals
On day 3: Medals awarded = (3 + 21/7) = 6 : Remaining 18 medals
On day 4: Medals awarded = (4 + 14/7) = 6 : Remaining 12 medals
On day 5: Medals awarded = (5 +7/7) = 6 : Remaining 6 medals
On day 6: Medals awarded 6

Is given point lies inside a triangle

Given three points A,B,C which forms a triangle and a point P.Now check whether point P lies inside the triangle formed by ABC.
Solution : Trick is to check for each line of a triangle formed by any two of A,B,C whether point P and remaining point lies on same side or opposite side.If they lies on same side,it will form a triangle.

for line AB----->C,P should be on same side.
for line BC----->A,P should be on same side.
for line CA----->B,P should be on same side.

If it satisfies above three conditions,we can say point is inside the triangle.

Now how do we check whether two points lie on same side of a line?
Substitute the given points in the line and check if they are yielding result with same sign.
ex: eq is Px+Qy+R=0;
for points (X1,Y1),(X2,Y2),substitute these points in the equation..
after substituting,if  PX1+QY1+R and PX2+QY2+R have the same sign,both points are on same side else they are on opposite side.

Method 2 : Calculate areas of triangles ABP,BCP,ACP and ABC.if sum of these 3 triangle areas is equal to the main triangle area,point is inside the triangle.It is very complex to calculate the area of the triangle and if area is float value, comparison will be difficult(doesn't give accurate result).

Angle between hours and minutes hand

Degree of angle between hour and minute hand when the time is 2:20?

Calculate the angle from each hand to 12 o'clock.Add the two angles.If it is more than 180,return the difference between 360 and angle.Each hour on the clock is 360/12 or 30 degrees, so the minute hand has gone 4 x 30 = 120 degrees from 12 o'clock. The hour hand has gone 2 x 30 plus the extra bit between 2 and 3 o'clock. That extra bit is 20/60 minutes, or 1/3 of 30 degrees. So the hour hand has gone 60 + 10 = 70 degrees from 12 o'clock. The difference is 120 - 70 = 50 degrees between the two hands.

50 trucks with payload

Question: Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Assume all the payload will fit in one truck.


http://www.mytechinterviews.com/challenge-50-trucks-with-payload

Interviews Puzzles

You can find good interview puzzles here :

1.   http://www.techinterview.org/
2. http://www.techinterviewpuzzles.com
3. http://www.mytechinterviews.com/

Combinations problem

Q : There are 10 friends planning for a movie.There is no guarantee that all people will go for movie.Either one can go or two or.....ten. How many ways they can go?

Ans: It is simple combinations problem.
10C0 + 10C1 +10C2+......_10C9+10C10 = 2powerN - 1;

OR  we can solve in different way.
Assume all people are like bits.Either one can go or cannot go.
each has two possibilities.For all 10 people it is 2powerN.But it includes the case of no one is going.
Final value is 2powerN - 1

Number of rectangles in NxN matrix is Nc2*Nc2(Square is also a rectangle)
Number of squears in NxN matrix is n*(n+1)*(2n+1)/6;
Refer :http://www.teachingideas.co.uk/maths/chess.htm

For N grid chess board,it will have N+1 rows and N+1 columns.Then answer will become (N+1c2) * (N+1c2)

A game of Russian roulette

Q : You are tied to your chair and can't get up.Here's a gun. Here's the barrel of the gun, six chambers, all empty. Now watch me as I put two bullets in the gun. See how I put them in two adjacent chambers? I close the barrel and spin it. I put the gun to your head and pull the trigger. Click. You're still alive. Lucky you!  I'm going to pull the trigger one more time. Which would you prefer, that I spin the barrel first, or that I just pull the trigger?


A:There are two bullets in six chambers, or, to put it more optimistically, four empty chambers out of six. Spin
the barrel, and you've got a four-in-six, or two-in-three, chance of survival.For the other option, look at it this way. The four empty chambers are all contiguous. One of them just spared your life. For three of these four empty chambers, the "next" chamber in succession will also be empty. The remaining empty chamber is right before one of the two bullets. That means you have a three-in-four chance of survival when you don't spin.
Three-fourths is better than two-thirds, so you definitely don't want the barrel spun again.

Globe Walker

Question: How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started?

Answer: The trivial answer to this question is one point, namely, the North Pole. But if you think that answer should suffice, you might want to think again! 

Let’s think this through methodically. If we consider the southern hemisphere, there is a ring near the South Pole that has a circumference of one mile. So what if we were standing at any point one mile north of this ring? If we walked one mile south, we would be on the ring. Then one mile east would bring us back to same point on the ring (since it’s circumference is one mile). One mile north from that point would bring us back to the point were we started from. If we count, there would be an infinite number of points north of this one mile ring.

So what’s our running total of possible points? We have 1 + infinite points. But we’re not done yet!

Consider a ring that is half a mile in circumference near the South Pole. Walking a mile along this ring would cause us to circle twice, but still bring us to back to the point we started from. As a result, starting from a point that is one mile north of a half mile ring would also be valid. Similarly, for any positive integer n, there is a circle with radius

r = 1 / (2 * pi * n)

centered at the South Pole. Walking one mile along these rings would cause us to circle n times and return to the same point as we started. There are infinite possible values for n. Furthermore, there are infinite ways of determining a starting point that is one mile north of these n rings, thus giving us (infinity * infinity) possible points that satisfy the required condition.

So the real answer to this question is 1 + infinity * infinity = infinite possible points!

Crazy Guy on the Airplane

A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let’s say that the nth passenger in line has a ticket for the seat number n.)

Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in, at random.

What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

Solution :

For four passengers, the possiblities are:

(x-ing out the ones that are not possible--because a "normal" passenger would sit in their own seat if it is open)

1234

1243 x

1324 x

1342 x

1423 x

1432 x

2134

2143 x

2314 x

2341 x

2413 x

2431 x

3124

3142 x

3214 

3241 x

3412 x

3421 x

4123

4132

4213

4231

4312 x

4321 x

Of the 8 valid possibilities, 1/2 of them have player 4 sitting in the his own seat.

An easier way to think about it:

There are only two (relevant) possible outcomes of a random seat choice:

1) Seat 1  (1/100 chance)

2) Seat 100 (1/100 chance)

3) Some other seat (98/100 chance)

Case 1 - Each other person can sit in their assigned seat, and the last passenger can sit his own. Let's call this a "win"

Case 2 - Each other person can sit in their assigned seat, but the last passenger's seat is taken, and he has to sit in seat 1. Let's call this a "loss"

Case 3 doesn't particularly interest us, because it simply defers the "decision" point to a passenger later, who will make another random choice.

At each point, the chances of randomly choosing seat 1 is the same as randomly choosing seat n, so the chances will always be 1/2, no matter how many seats/passengers we're talking about.

Cars on the Road

if the probability of observing a car in 20 minutes on a highway is 609/625, what is the probability of observing a car in 5 minutes (assuming constant default probability)?


probability of not seeing the car in 20 mins = (probability of not seeing the car in 5 mins)^ 4

as we can assume constant default probability

probability of not seeing tha car in 5 mins = (1 - (609/625))^ (1/4) = 2/5

so probability of seeing the car in 5 mins = 1 - (2/5) = 3/5

Why are manhole covers round?

A manhole cover is a removable plate forming the lid over the opening of a manhole, to prevent anyone from falling in and to keep unauthorized persons out.

The question of why manhole covers are typically round, at least in the U.S., was made famous by Microsoft and Google when they began asking it as a job-interview question.Originally meant as a psychological assessment of how one approaches a question with more than one correct answer, the problem has produced a number of alternate explanations, from the pragmatic ("Manhole covers are round because manholes are round.") to the philosophical.

Reasons for the shape include:

• A round manhole cover cannot fall through its circular opening, whereas a square manhole cover may fall in if it were inserted diagonally in the hole. (A Reuleaux triangleor other curve of constant width would also serve this purpose, but round covers are much easier to manufacture. The existence of a "lip" holding up the lid means that the underlying hole is smaller than the cover, so that other shapes might suffice.)
• Round tubes are the strongest and most material-efficient shape against the compression of the earth around them, and so it is natural that the cover of a round tube assume a circular shape.
• Similarly, it is easier to dig a circular hole and thus the cover is also circular.
• The bearing surfaces of manhole frames and covers are machined to assure flatness and prevent them from becoming dislodged by traffic. Round castings are much easier to machine using a lathe.
• Circular covers do not need to be rotated to align them when covering a circular manhole.
• Human beings have a roughly circular cross-section.
• A round manhole cover can be more easily moved by being rolled.
• Most manhole covers are made by a few large companies. A different shape would have to be custom made.

Other manhole shapes can be found, usually squares or rectangles.

Horse and tracks puzzle

You have 25 horses. You have 5 tracks to race on. We need to find 3 fastest horses. How many minimum races required to find that ? We have no stop-watch. Horses run at same speed.


http://techpuzzl.wordpress.com/2009/08/03/25-horses/

Factorial Zeros

How many zeros are at the end of "100!"?

Answer: The trick is remembering that the number of zeros at the end of a number is equal to the number of times "10"(or
"2*5")appears when you factor the number.
Therefore think about the prime factorization of 100! and how many 2s and 5s there are.

so the number of 5s is also the number of 10s in thefactorization.There is one 5 for every factor of 5 in our factorial
multiplication(1*2*...*5*...*10*...*15*...) and an extra 5 for 25, 50, 75, and100.

Therefore we have 20+4=24 zeros at the end of 100!.


The minimum number of multiplications required to evaluate the expression   a + bx + cx2 + dx3 + ex4  is
a+bx+cx2+dx3+ex4
a+x(b+cx+dx2+ex3)
a+x(b+x(c+dx+ex2))
a+x(b+x(c+x(d+ex)))
a+x(b+x(c+x(d+(e*x))))
Number of brackets(4) represent the multiplications required.
Horner's Rule :
A rule for polynomial computation which both reduces the number of necessary multiplications and results in less numerical instability due to potential subtraction of one large number from another. The rule simply factors out powers of  x, giving

Refer : http://en.wikipedia.org/wiki/Horner_scheme


Java Code : 

public class NumberOfZeros {
 public static void main(String[] args) {

  int n = 100;
  int x10 = 0;
  int x5 = 0;
  int x25 = 0;

  for (int i = 1; i <= n; i++) {
   if (i % 10 == 0)
    x10++;
   else if (i % 5 == 0)
    x5++;
   if (i % 25 == 0)
    x25++;
  }
  int totalNumberOfZeros = (x10 + x5 + x25);
  System.out.println("Total number of zeros : " + totalNumberOfZeros);
 }
}

Water, Jug & Thinking Out of Box..Puzzle

You have a five quart jug and a three quart jug, and an unlimited
supply of water (but no measuring cups). How would you come up with
exactly four quarts of water?

NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’
of the jug would be impossible.




/* Initially 3quart jug and 5quart jug are empty */
1. Fill 5 quart jug
/* Now 3quart jug is empty and 5quart jug is full */
2. Pour water from 5quart jug into empty 3quart jug.
/* Now 3quart jug is full and 5quart jug has 2quart remaining in it */
3. Now empty the 3quart jug.
/* Now 3quart jug is empty and 5quart jug has 2quart remaining in it
*/
4. Transfer all water from 5quart jug to 3 quart jug
/* Now 5quart jug is empty and 3quart jug has 2quart remaining in it
*/
5. Now again fill 5 quart jug.
/* Now 5quart jug is full and 3quart jug has 2quart remaining in it
*/
6. Pour water from 5quart jug to 3quart jug till it gets filled up.
/* Now 5quart jug has 4quarts ( which s wat we need :) ) and 3quart
jug is full (which is unnecessary) */

Sum of numbers and/or digits 1-100

What is the sum of the DIGITS of 1 + 2 + 3 +...+ 100?

A good way to approach this problems is to consider smaller problems 
and look for a patterm.

Let's first ask, what is the sum of the digits 0-9? Clearly, this is 
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9, which equals 45.  

Next question: What is the sum of the digits of the numbers 10-19? 
We know that these numbers all have a "1" in the tens place, and a 
number 0-9 in the units place. There are ten of these numbers, so 
there are ten 1's and the digits 0, 1, 2, 3, 4...9. So, the sum of 
these numbers must be 10x1 + (0 + 1 +...+ 9).

What about the sum of the digits of the numbers 20-29? Again, we need 
to add ten 2's and the digits 0-9, which is 10x2 + (0 + 1 +...+ 9).

Do you see the pattern? So, when we add up the digits of all numbers 
0-99, the expression is:

       (0 + 1 +...+ 9) +              The numbers 0-9
10x1 + (0 + 1 +...+ 9) +              The numbers 10-19
10x2 + (0 + 1 +...+ 9) +              The numbers 20-29
10x3 + (0 + 1 +...+ 9) +              The numbers 30-39
10x4 + (0 + 1 +...+ 9) +              The numbers 40-49
10x5 + (0 + 1 +...+ 9) +              The numbers 50-59
10x6 + (0 + 1 +...+ 9) +              The numbers 60-69
10x7 + (0 + 1 +...+ 9) +              The numbers 70-79
10x8 + (0 + 1 +...+ 9) +              The numbers 80-89
10x9 + (0 + 1 +...+ 9)                And, finally, the numbers 90-99.

Thank goodness we can simplify this! From the distributive law of 
multiplication, we know that 

(10x1 + 10x2 +...+ 10x9) = 10(1 + 2 ...9). 

We also know that there are ten additions of (0 + 1 +...+ 9), 
which is another way of saying that there are ten times 
(0 + 1 +...+ 9),  10(0 + 1 +...+ 9). 

So, the sum of digits of the numbers 1-99 is:

10(0 + 1 +...+ 9) + 10(0 + 1 +...+ 9) = 20(0 + 1 + 2...9)
               
Since (0 + 1 +...+ 9) = 45, this equals: 
                              20 x 45 = 900

We add the digit 1 from "100" because we want the sum of digits 1-100, 
and the final answer is 901.