Quantitative Interview questions and answers

[pardasani]

King has 1000 bottles of wine. One of the bottles is poisoned. He is using subjects to find out which bottle is poisoned. Objective is to minimize the number of people you use. The rule is you can't let some people drink, wait and let others drink. Everyone will drink at the same time...What is the optimal strategy to minimize the number of people used while finding the poisoned bottle?

My take 999.... pick at random any one bottle keep it aside, bring 999 people to drink from the rest... If someone in those 999 dies, we know which was the poisoned one... If everyone survives then the bottle left out is the poisoned one...

I guess the key statement is "every one will drink at the same time"... Now there are 1000 bottles, to be tested AT THE SAME TIME; I could not any other way to optimize the thing!

The thing that I don't like however with this reasoning is the fact that, suppose there were 2 bottles that were poisoned, and everybody had to drink at the same time -- what then !!!!...

 

[alain]

I agree with SP... 999 people.

 

[Vlad]

King has 1000 bottles of wine. One of the bottles is poisoned. He is using subjects to find out which bottle is poisoned. Objective is to minimize the number of people you use. The rule is you can't let some people drink, wait and let others drink. Everyone will drink at the same time...What is the optimal strategy to minimize the number of people used while finding the poisoned bottle?

Initially I thought that you can use dynamic programming but since all need to drink in the same time you cannot apply recursion methods on the suboptimal problems.
It is the kind of problem where you can use less people if more people will drink the poison -
like in coding : you have memopry/CPUtime trade. The solution makes the following assumptions:
the bottles are big enough an the poison is strong enough so mixing bottles is possible
and mixing takes place before everyone drinks.
Solution1 (2D) : 1000 = 31x31 + 6x6 + 3. Put the bottles in the cells inside a square with
side = 31 ( you get 961 bottles) and in another suqare of side = 6 ( another 36 bottles) and of the last 3 bottles only two people will need to drink (if noone dies than is the last unused bottle). Put the people on two sides of each square and everyone drinks a cocktail made from a mix of all the bottles in the cells in front of his position. This way you use 31+31+6+6+2=76 people. Noone dies or 2 people die, the intersection of their lines will deterimine the poisoned bottle.
Solution2 (3D) : 1000 = 10x10x10. Create a cube of (edges) side = 10 and put the bottles in the 1000 cells inside the cube and the people on the 3 edges parallel to the axes. Each person drinks the cocktail made from a mix from all the bottles in the cells inside the 2D plane in front of him (perpendicular on his edge). 3 people die and the intersection of their planes determine the point/cell where is the poisoned bottle. This way you use only 30 people but with more casualties.
This approach is possible since the problem does not ask to minimize the number of casualties . If you care about the people and you want to save them than you have to use a different approach.
Leave the 4D, 5D ... solutions out for now.

 

[Yuriy]

King has 1000 bottles of wine. One of the bottles is poisoned. He is using subjects to find out which bottle is poisoned. Objective is to minimize the number of people you use. The rule is you can't let some people drink, wait and let others drink. Everyone will drink at the same time...What is the optimal strategy to minimize the number of people used while finding the poisoned bottle?

Can we pour wine from a number of bottles somewhere and then let people drink?

For example, choose N people, divide 1000 bottles among the N people, so everyone gets 1000/N bottles. Pour a little bit of every 1000/N bottles into separate bottles and let those N people drink. Assuming even tiny concentration of the poison kills the tester

One of the N dies, take the suspicious 1000/N bottles and divide them among the N-1 remaining, so everyone gets 1000/N/(N-1) bottles. Pour a little bit of every 1000/N/(N-1) bottles into separate bottles and let those N-1 people drink.

One of the N-1 dies ...

Repeat the process (rounding up the numbers) until we are down to 1 bottle. Then calculate the smallest possible N.

My answer is N=6.
First, each of 6 people drinks a little bit from 166 or 167 bottles (max 167). One dies.
Second, each of 5 survived people drinks a little bit from 33 or 34 bottles (max 34). One dies.
Third, each of 4 survived people drinks a little bit from 8 or 9 bottles (max 9). One dies.
Fourth, each of 3 survived people drinks a little bit from 3 bottles. One dies.
Fifth, each of 2 survived people drinks a little bit from 1 or 2 bottles (max 2). One dies.
Sixth, if the one who drank from 2 bottles survived, he/she drinks from one of the remaining two.

 

[jameshin]

that's true
2.5 i think they told me is the right answer
but how to get tehre

thanks

 

[Jonathan]

I got 2.5 by:

fist rearranging the equation --> (x^2 + 5x)^.5 - x = ((x+2.5)^2 - 6.25)^.5 - x
then I thought as x-> infinity, the 6.25 becomes negligible,
therefore the equation becomes ((x+2.5)^2)^.5 - x = x+2.5 - x = 2.5

I am a newbie here, I'm sure there is a more elegant method, unless of course, I am correct.

 

[quantrecruiter]

Job opportunities...

Hello users,
I am an IT recruiter in the Chicago area representing several financial institutions in the area. I am always looking for qualified candidates with skills such as strong C++, MBS, Fixed Income, Quantitative development/Analytics, Sybase experience, and a strong mathmatics background.
Shoud anyone be interested in a great opportunity, you can send your resume to cchiovatero@osgglobal.com and you can call me at 847-954-8063.
I hope to hear from some of you. Make it a great day.
Craig Chiovatero

 

[jameshin]

Hey Jonathan, thanks for the explanation.. Well it may be a correct method but I heard we may need to use expansion around x.

does anyone have an idea for a simpler and more elegant solution?

thanks

James

 

[rohitbansal]

Answer is 2.5

This how i did
Multiply and divide [ (x^2 + 5x)^0.5 + x ]
-> {[ (x^2 + 5x)^0.5 - x ] * [ (x^2 + 5x)^0.5 + x ]} / [ (x^2 + 5x)^0.5 + x ]
-> {x^2+5x - x^2}/ [ (x^2 + 5x)^0.5 + x ]
-> 5x/[ (x^2 + 5x)^0.5 + x ]
Now taking numerator x down we get
-> 5/ [(x^2 + 5x)^0.5 + x ]/x
-> 5/ { [(x^2 + 5x)/x^2]^0.5 + 1 }
-> 5/ { [1+5/x]^0.5 + 1}
->as x->infinity 5/x tends to 0, so we have
-> 5/ {1+1}
-> 2.5 The answer

Correct me if I am wrong

hey guys

what is lim when x goes to infinity of [ (x^2 + 5x)^0.5 - x ]

thank you
James

 

[Ed]

One of the N-1 dies ...

Repeat the process (rounding up the numbers) until we are down to 1 bottle. Then calculate the smallest possible N.

My answer is N=6.
First, each of 6 people drinks a little bit from 166 or 167 bottles (max 167). One dies.
Second, each of 5 survived people drinks a little bit from 33 or 34 bottles (max 34). One dies.
Third, each of 4 survived people drinks a little bit from 8 or 9 bottles (max 9). One dies.
Fourth, each of 3 survived people drinks a little bit from 3 bottles. One dies.
Fifth, each of 2 survived people drinks a little bit from 1 or 2 bottles (max 2). One dies.
Sixth, if the one who drank from 2 bottles survived, he/she drinks from one of the remaining two.

Yuriy, I like your answer, but it seems to violate the requirement that all drink at the same time.

 

[Andy Nguyen]

Here are two bona-fide job interview questions, as reported by two frazzled interviewees.

[Microsoft] Your boss wants you to design a calendar that she will place on her desk right next to the promotion forms. She gives you two plain wooden cubes that will fit side-by-side in a wooden holder like so (front view):

Your job is to place a single digit between 0 and 9 on each of the twelve faces of the cubes so that any day of any month can be displayed. Can you do it?

 

[VladimirBunicu]

I think this one works
0 1 2 7 8 9
1 2 3 4 5 6
but this solution assumes that one cube can be used by itself (for example, -8 instead of 08 etc)

 

[VladimirBunicu]

The actual solution has its trick, haha.
form a calendar with two cubes (answer) - QuantNetwork - Financial Engineering Forum

 

[Andy Nguyen]

1. There are 3 computers. One always tells the truth, one always tell the opposite of the truth and the third one sometimes tells the truth, sometimes tells the opposite of the truth. We do not know which computer is the one that tells the truth, which is the one that tells the opposite of truth etc. We have only one opportunity to ask a question to one computer. Based on the answer, we want to pick the computer that sometimes tells the truth and sometimes doesn't. We do not need to find out which computer is the one that always tells the truth or which is the one that always tells the opposite of the truth. What question should we ask to one computer?

2. We buy a bag of candy. In the bag, there are 5 candies. Each candy can be one of 50 different candy types, being equally likely from each type. What is the expected number of types of candy we will have in the bag? As an example, if there are two orange candy, two apple candy and one strawberry candy in the bag, then there are 3 types of varieties.

3. X1, X2,...,Xn are independent random variables, uniformly distributed on [0,1]. What is the probability that X1+X2+...Xn<1.
4. (x_0 =1)
(x_n =1+\frac{2}{3x_{n-1}^2})
(x_1 = \frac{5}{3})
(x_2 = \frac{31}{25})
(x_3 = \frac{4133}{2883})

Can you find a closed form for (x_n)

 

[ramnik]

4. 3 points are randomly drawn on a circle. What is the probability of them being on the same semi-circle ?
Answer: 1/2 or 50%

CLEARLY WRONG!!!
I will prove it for n points ie: What is the probability that n point chosen randomly lie on a semi-circle.
Let us choose randomly the points P(one), P(two)..... P(n). Now define events
E(one)=all the n points lie in the clockwise semi-circle, clockwise of P(one) ie: P(one) is one end point of semi circle.
///y E(n)= all the n points lie in the clockwise semi-circle, clockwise of P(n) ie: P(n) is one end point of semi circle.
Now clearly :
E(i) intersection E(j)= phi (since if all points lie to clockwise semi-circle of i, then i is the end point of semi-circle. ///y for E(j) and therefore intersection is null).
We need:
P(E(one)UE(two)U....E(n))=P(E(one)) + P(E(two)) + .... P(E(n))
#using the fact that E(i's) are disjoint and probability measure is sigma additive(here only using finite additivity)

P(E(i))=1/2^(n-1)
Thus P(n points lie on semi circle)= n/(2^(n-1))

I'll try to think why the previous arguments are flawed. Btw the answer for n=3 is 3/4.

 

[Matthew M]

1. Find \(x\) if \(x^{x^{x^{\ldots}}}=2\)
Answer: \(x=\sqrt{2}\)

2. Find all real and complex root of \(x^6=64\)
Answer: \(x_1,\ldots,x_6 =\{\pm 2,\pm 1 \pm \sqrt{3} \}\)

3. The hour and minute hands of a clock meet at 12'oclock. When will be the first time they meet again ?
Answer: After 1 hour, 5 minutes 27.2727 seconds

4. 3 points are randomly drawn on a circle. What is the probability of them being on the same semi-circle ?
Answer: 1/2 or 50%

5. A unit length is broken off into 3 pieces. What is the probability of them forming a triangle ?
Answer: 1/8 or 12.5%

6. Calculate \(\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\ldots}}}} \)
Answer: 2

7. There are 14 identical-looking balls. 13 of them have the same weight while one of them is heavier than the rest. What is the minimum times you can weight to identify the heaviest ball ? How do you generalize for n balls ?
Answer: With 3 weights, I can identify the heaviest ball. For n balls, I can identify the heaviest ball after x times where x is the largest integer such that \(2^x \leq n\)

The answers to 2 and 4 are incorrect. 5 is an ill-posed question.

Edit: there is a possibility that the answer to two is merely a typo. If you insert an i after the \(\sqrt{3}\) then it becomes correct. The real question is why you would put it in a+ib notation instead of exponential notation (where the answer is obvious).

 

[Matthew M]

King has 1000 bottles of wine. One of the bottles is poisoned. He is using subjects to find out which bottle is poisoned. Objective is to minimize the number of people you use. The rule is you can't let some people drink, wait and let others drink. Everyone will drink at the same time...What is the optimal strategy to minimize the number of people used while finding the poisoned bottle?

The answer is 10.

Label the bottles 0,1,2,...999

Line the 10 people up in a row. They are going to act like digits of a binary number. Pour a bit of bottle X in the glass of each of the people for whom the binary representation of X sets their digit to 1. Repeat for all X.


In other words, pour wine from bottle 0 into nobody's glass. Pour wine from bottle 1 into the first person's glass only (counting from the right). Pour wine from bottle 746 into the glasses of the tenth, eighth, seventh, sixth, fourth and second people's glasses (because the binary rep. of 746 is 1011101010). Write down the binary number given by the people who die after drinking. This is the number of the poisoned bottle.

In other words, the guy at the left end has wine from bottles 512 to 999 in his glass. The guy immediately to his right has wine from bottles 256 to 511 and 768 to 999 in his glass, etc.

 

[Matthew M]

3. X1, X2,...,Xn are independent random variables, uniformly distributed on [0,1]. What is the probability that X1+X2+...Xn<1.

Easy enough. It's the volume of an n-dimensional right polyhedron with height is 1 and whose base is the (n-1)th dimensional polyhedron which solved the problem for n-1. The forms are: a line, an isosceles right triangle of base/height 1, a right pyramid with the previous isosceles right triangle as its base, etc.

Unless I'm mistaken (I didn't check) this is 1/n! (proof by induction...after inserting the inductive hypothesis, you integrate (x^{n-1}/(n-1)!dx) from x = 0 to 1)...

 

[Andy Nguyen]

The answers to 2 and 4 are incorrect. 5 is an ill-posed question.

They are wrong. Haven't had time to update.
But I hope the questions are interesting enough

 

[Matthew M]

They are wrong. Haven't had time to update.
But I hope the questions are interesting enough

Those ones are pretty standard high school math competition questions. Some of the later ones in the thread are more interesting.