Find next number in Sequence

you have a sequence where each number is a multiple of 2 or 5 (so: 2^i * 5^j). Given the beginning of the sequence as 1,2,4,5,8,10,16... and find a algorithm to calculate the next number in the sequence?

Answer:
This answer gives u the pattern to make the sequence. Algorithm would look like this.
1. Make set1 with all powers of 2(i.e 2,4,8,...)
2. Make set2 with all powers of 5(i.e 5,25,125 ...)
3. Make set3 with product of numbers from set1 and set2(i.e 10,20,40,50,80,100 etc..)
Make sure that third set is sorted.
Now display elements from set1 till u find a element less than starting element in set2 or set3. Otherwise display minimum element out of elements from set2 or set3.

Design a stack which have O(1) time complexity for finding the minimum element?

This problem can be solved using simple encoding technique. We should use the minimum element to get the next minimum element.Here is a solution which uses O(1) space.PUSH(elem) Operation: In this process we are keeping minimum element on the top of the stack at any given time. And encoding(i.e elem-min) the actual data with minimum and storing. Whenever there is a change in cur minimum data stored in the stack will be negative. This property will be used while poping the elements to find the next minimum. We can define it as shown below. if stack is empty. Store the element twice Else CurMin = POP(); Take difference between elem and Curmin and push it on to stack. Push the least of elem and CurMin on to stack.
POP() Operation: POP process is bit tricky. If minimum is not changing (i.e elements are positive on stack) then return the element + curMin(sitting on stack). If you see a negative stack element then it means there was a shift of curMin (or minimum element is the one which is being popped). In this case we take the current minimum and return it as popped element. We find the new minimum (as current minimum is popped out) by computing curMin-element and push it on top of stack as minimum element. We can summarize it as shown below.curMin = pop();element = pop(); If element is negative then return curMin and push curMin-element on to stack. Else push curMin on to stack and return element + curMin.
FindMin():
This is trivial operation as we are storing minimum element on the top of the stack at any given time. So we pop it and return to the caller. FindMin() steps will be...min=pop();push(min);return min;

Mathematician daughters age problem?

Problem:
Two old friends(Mathematicians) meet each other after 20 years.Lets call them A,B.
A says to B: “how have you been?”
B says: “Great! I got married and I have three daughters now”
A says: “Really? how old are they?”
B says: “Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..”
A says: “I still don’t know”
B says: “The oldest one just started to play the piano”
A says: “my oldest is the same age!”

Solution:

This is simple mathematical problem which can be solved by applying simple logical reasoning in the case of ambiguity.
After first clue A couldn't answer the question just because there might be two sets of three numbers which produce product of 72 and the sum of numbers in both the sets is equal.
After simple calculation we can reduce on two following two sets where sum of numbers is equal.
(8,3,3) & (6,6,2)
In second case two elder kids are of same age, so you cannot pick an “oldest”. Answer is (8,3,3) hence.

Why are manhole covers round rather than square?

This Question was most interviewer's favourite question for years. I hardly find anyone asking it these days. Answer to this question involves some simple maths with commonsense.
All of us know that circle has same diameter in all directions so no matter how you hold it cover cannot be pushed into a circular manhole. Whereas, if it is square, cover can be pushed into manhole via diameter by holding it on edge. Another aspect is, if cover is circular it is easier to roll it so for shorter distances transportation is easy.

Simulate seven sided die using 5 sided die?

This Question is asked in different formats like simulate rand7() using rand5() function.

There is no right answer to this question if interviewer specifies that 7 sided die should have equal probability to al the numbers on it(i.e. 1-7). This is because 5 and 7 are coprime and there is no direct mapping available between coprimes.
There are several solutions which creates a biased 7 sided die.
Sol1:
Throw 5 sided die 7 times. sum will be between 7 and 35, with equal probable numbers. Then take the module 7 of the sum and add 1 to it.
This solution will produce biased die because probability of 1 is higher here.

Sol2:
rand7() = ((ran5() + rand5() + rand5() + rand5() + rand5() - 5) % 7) + 1

Game of Russian roulette!!

You are tied to a chair and can,t get up.Here is the gun , six chambers all empty. Now I put two bullets in the gun and I put these bullets in the adjecent chambers. I close the barrel and spin it. I put the gun to your head and pull the trigger. Clik and the slot was empty. Now before we start the interview I want to pull the trigger one more time , which one do you prefer , that I spon the barrel first or that I just pull the trigger ?

X being a bullet, _ being and empty chamber. The gun rotates from 1 to 6, and the bullets are in adjacent chambers.

The setup: _ X X _ _ _
1 2 3 4 5 6

The interviewer just got a blank, so the current position must be 1,4,5, or 6. If it’s 1, the next one is a bullet. If it’s 4-6, the next one is empty. So if the interviewer just fires again, you have a 1/4 chance of getting shot.

If, on the other hand, the interviewer spins again, you’re back to the initial 2/6 or 1/3 chance of getting shot.

I’ll take the 1/4 chance, myself.

If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?

fill cup5 , pour it in cup3, cup5 left with 2quarters.
pour out cup3, pour cup5 into cup3, cup3 has 2quarters.
fill cup5, pour it in cup3 until cup3 fills
now cup5 has 4quarters.

There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner. What is the probability that they don’t collide?

prob of colliding is
= 1st and 2nd moving towards each other + 2nd and 3rd moving towards each other + 3rd and 1st moving towards each other
= (1/2)* (1/2) + (1/2)* (1/2) + (1/2)* (1/2) = 3/4

probability of not colliding = 1- 3/4 = 1/4

If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands?

For continuous clock where hours and minutes hands move continuously then the answer is 7.5 Minutes.
3.25* 30 - 15*6 = 7.5

For discrete clock where minutes hand moves after 60 secs and hours hand moves after 12 mins then the answer is 6 minutes.

Ratio of boys and girls.

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?

Solution:

50:50.

probability of a boy/girl is always 2 irrespective of the number of conditions.

for the above problem we can prove it with simple probability theory.

Lets assume P(b) be the probability of having a boy. P(g) be the probability of having a girl.

Total expectation of a boy is equal to (probability of having a boy at first instance + probability of having a girl then a boy + probability of having 2 girls followd by a boy + etc... )
E(b) = 1/2 + 1/2*1/2 + 1/2*1/2*1/2 + ......
it comes down to 1 ( infinite series sum = a/1-r = 1/2/1-1/2 = 1).

E(g) = 0 + 1/2 + 1/4 + 1/8....
it comes down to 1.

It means there are equal number of girls and boys in the village.

Number coding

Assume 9 is twice 5; how will you write 6 times 5 in the same system of notation

Solution:

9 is twice 5. So 5 is 4.5.
6 times 5 should be 6*4.5 = 27

Distance between trains

One train runs from A to B at 105 miles per hour; the other runs from B to A at 85 miles per hour. How far apart were the two trains 30 minutes prior to their crossing?

Solution:

Two trains are 95 miles apart 1/2 Hr before they crossed each other

Relative Speed of the trains = 85+105 = 190MPH

One hour before they crossed, they would have been 190 miles apart.

Distance between the trains 1/2 hr before they crossed would be 190/2 = 95miles

Probability of observing a car

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

probability of not observing a car in 30 mins = probabality of not observing a car in first 10 mins * not obs in next 10 mins * not obs in last 10 mins

lets assume observing a car in 10 mins = p

probability of not observing the car in 10 mins = 1-p

probability of not observing the car in 30 mins = (1-p)^3

so (1-p)^3 = 0.05

1-p = (0.05)^1/3.
p = 1- (0.05)^1/3.
p = 1- 0.37
p = 0.63.