Quantitative Interview questions and answers

[quantyst]

Reply to jayg's "My first post"

You have solved a part of the problem, and have done a very good job of solving the Diophantine equation.

But the issue is not only where the function f is maximized, but what that maximum value is subject to f<R. How are we supposed to know in advance that max of f is 101?

Of course taking advantage of gcd(9,20)=1, we simply multiply through by 101 (see quantyst's 'partial' solution), etc. etc. So, given that we have differently signed x and y solution, how can we use this 'insight' to our advantage in order to produce a same signed x and y solution?

For example, allowing x and y to be differently signed, the Diophantine equation 9x+20y=11 has solution (x=-1, y=1). But if we restrict both x and y to being non-negative integers, then it has no solution, even though the maximum value of f(x,y)=9x+20y subject to f<11.7087 is 9 with (x=1, y=0).

 

[newventurect]

n mathematicians and K rooms

I think the solution to put n mathematicians in k rooms is:

(n!/(n-k)!)*k?^(n-k)

 

[newventurect]

n mathematicians and K rooms

I think the solution is:

(n!/(n-k)!)*(k^(n-k))

 

[quantyst]

I think the solution is:

(n!/(n-k)!)*(k^(n-k))

Let us see if your formula gives the correct answer when the number of rooms, k, is 1.




We know when k=1, there is only one way we can place all n mathematicians in just one room. So, we should expect an answer of 1 from a correct formula.

Agreed?

But what answer does your formula give?

Your formula is incorrect!

 

[emil]

I think that the formula should be:

(\frac{n!}{(n-k)!} * (n-k)^{k-1})

 

[fddk]

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

Andy,
a newbie here. Isn't 12/11 hours = 1 hour + 60/11 minutes a good-looking anwser too? :D

Cheers

 

[quantyst]

Circumspectify Circumspecticate Circumspectate Circumspeterize ...

I think that the formula should be:

(\frac{n!}{(n-k)!} * (n-k)^{k-1})

It is best to exercise a bit of restraint before pushing the 'submit' button!

It's important to get into the habit of checking answers with extreme cases, when n and k (or the variables/parameters) take very small values or very large values, like infinity, whatever.

Also it helps to identify which problem the proposed solution/formula is intended to be an answer to.

The formula, quoted above, gives a wrong answer. When n is any large number and k=1, one should expect the answer to be 1, as there is only one way n mathematicians can be placed in one room. (Did you take a look at my answer to the previous post by newventurect?)

But the formula gives answer n. So, it is wrong.

Also it is a good etiquette to study the answers given by others before presenting a new one.

See, for example, answer given by ramnik to this problem.

 

[jayg]

But the issue is not only where the function f is maximized, but what that maximum value is subject to f<R. How are we supposed to know in advance that max of f is 101?

Quantyst, thank you. I sort of misunderstood the question.

 

[newventurect]

yes, you are right

 

[jayg]

Ok I have been trying to solve this problem for a few days now and this is where I got so far.

Given ax+by <= R, we need to find a condition C(R,a,b) such that the equation has a solution (x,y) in nonnegative integers.

My approach.

I am assuming the following:
1. a,b,R > 0 and integers
2. a,b,R are coprime with each other.

since a,b are coprime there exists soluions for ax+by=1. Let this solution be (x0,y0).
A general form for the solutions is (x0+b*k,y0-a*k) for k any integer.

We can sum R such solutions for ax+by=1 such that aX+bY=R . But we need to impose the condition that X>=0 and Y>=0.

summing R solutions of the form (x0+b*k,y0-a*k),
X= Rx0+bS
Y=Ry0-aS
where S is sum of any R integers and hence itself can be any integer.

So we need to find an integer S such that Rx0+bS>=0 and Ry0-aS>=0

Observe that x0y0<=0 since a,b are positive. Also it is enough to impose the condition that XY>0 since X and Y together cannot be negative.

(Rx0+bS)(Ry0-aS)>=0
We can reduce this to -ab(S+Rx0/b)(S-Ry0/a)>=0
Thus if there exists an integer between Rx0/b and -Ry0/a , the equation ax+by=R will have nonnegative integer solutions in (x,y). And this integer will be -S.

Example 1

7x+3y=11
a=7, b=3, R=11
For 7x+3y=1 we have (x0,y0)=(1,-2).
There should be an integer between Rx0/b =(11/3) and -Ry0/a =(22/7) for the equation to have a solution. So there is no solution.

But lets try 7x + 3y =10, then Rx0/b =(10/3) and -Ry0/a =(20/7) and we have S=-3.
one solution is X=Rx0+Sb=1 and Y=Ry0-Sa=1

 

[quantyst]

Unchain the Gold Chain

You've got someone working for you for N days. You own a gold chain of N rings to be paid as compensation to the worker. The gold chain consists of N sequentially connected equal rings with two free ends. You must remit the worker one gold ring at the end of every day for N days. You are only allowed to make MINIMAL number of cuts in the gold chain. How do you EACH DAY pay your worker?

So, what is the minimal number of cuts you need to make in the gold chain, where in the gold chain are these cuts made, and how are the payments made?

Note that a cut ring is equal in value to one that is not cut. For an example to understand this problem better, assume N=7. The minimal number of cuts to be made is one and that occurs on the third ring as follows: 2+1+4=7. So, on the first day, you pay out 1 (the cut) ring. On the second day, you pay out the piece consisting of two connected rings and in return get back the single (cut) ring. On the third day, you pay out the single ring. On the fourth day, you pay out the piece consisting of 4 connected rings and in return you get beck the rings held by the worker. For the remaining days you give out the three rings as before.



Another example: N=23



Solution: 3+1+6+1+12=23.

 

[quantyst]

Find The j Speediest Horses!

There are n horses. You are to determine the minimum number of races it takes to identify the j fastest horses amongst the n horses. Each horse's speed is constant and different than that of any other horse. Each horse race is comprised of a maximum of k horses where k>j. You don't have a stop watch to time the horses' speeds. All you can infer from each race is the rankings of the horses with respect to their speeds in that race.

 

[IlyaKEightSix]

k > n is impossible.
When k=n, the answer is 1.
When k<n, then we can do this simple example:

We race every horse but horse n, and we rank them. Then we replace horse n-1 with horse n. If the results are the same with horse n taking horse n-1's exact rank, we race horses n and n-1 to finally determine the exact order.

That you have to find only the fastest j horses is irrelevant to this problem, since in the worst case scenario, you may end up racing all of them anyway.

I believe the answer is (2^(n-k+1))-1.

 

[quantyst]

What you wrote is off the mark. Did you read the problem carefully?

What does it mean to say " We race every horse but horse n, and we rank them."?

You can have a race of (at most) k horses at a time. What you are proposing is a total disregard for the minimum number of races to determine the j fastest. Your answer doesn't even have a j in it! Did you wonder about your answer lacking a j in it?

An advice I will gladly accept from you and any one else: Before pushing the "submit' button, it's a WONDERFUL and highly profitable habit to check one's answer with extreme values -- very small or very large. For example, with n=6, k=2, j=1, you have six horses and you can compare two at a time to find the fastest among all six. Obviously it will take five races to get the job done. Your answer is way through the roof!

 

[glkev]

Another way for calibration

Let us see if your formula gives the correct answer when the number of rooms, k, is 1.




We know when k=1, there is only one way we can place all n mathematicians in just one room. So, we should expect an answer of 1 from a correct formula.

Agreed?

But what answer does your formula give?

Your formula is incorrect!

I am not sure about the close form solution, but this question should be able to calculate using iterate method with following algorithm:

1. define F(n, k) as the way to put n mathematicians in k rooms
2. F(n, 1) = 1; F(1, 1) = 1; F(2, 1) = 4 ( 1,2|0; 1|2; 2|1; 0|1,2)
3. F(n, k) = C(n, 0)*F(n, k-1) + C(n, 1)*F(n-1, k-1) + .. C(n, i)*F(n-i, k-1) + ... + C(n, n)*F(0, k-1); C(n, i)*F(n-i, k-1) means choose i from n, and put them into room 1, and put the rest of n-i mathematician into k-1 rooms
4. computing algorithm to iterate the formula

Albert

 

[glkev]

Another way for unchaining the gold chain

You’ve got someone working for you for N days. You own a gold chain of N rings to be paid as compensation to the worker. The gold chain consists of N sequentially connected equal rings with two free ends. You must remit the worker one gold ring at the end of every day for N days. You are only allowed to make MINIMAL number of cuts in the gold chain. How do you EACH DAY pay your worker?

So, what is the minimal number of cuts you need to make in the gold chain, where in the gold chain are these cuts made, and how are the payments made?

Note that a cut ring is equal in value to one that is not cut. For an example to understand this problem better, assume N=7. The minimal number of cuts to be made is one and that occurs on the third ring as follows: 2+1+4=7. So, on the first day, you pay out 1 (the cut) ring. On the second day, you pay out the piece consisting of two connected rings and in return get back the single (cut) ring. On the third day, you pay out the single ring. On the fourth day, you pay out the piece consisting of 4 connected rings and in return you get beck the rings held by the worker. For the remaining days you give out the three rings as before.



Another example: N=23



Solution: 3+1+6+1+12=23.

Here's another way to solve it:

1. assuming there is k-1 cut in the chain to produce k chains, and each chain has S1, S2, ... Sk number of golds.
2. we have S1 = 1 for the first day; and S2 = S1 + 1
3. when I give Sj to the worker on a given day, I expect him to give all S1, S2, ... S(j-1) back to me, so we have Sj = S1 + S2 + ... + S(j-1)
4. the total number of golds are N = S1 + S2 + ... + Sj + ... + Sk = (Sk - 1) + Sk = 2*Sk -1
5. after we get the Sk, we apply 4) backward to retrieve S(k-1) and so on

 

[glkev]

The hour and minute hand meet at what time of the day

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

Andy,
a newbie here. Isn't 12/11 hours = 1 hour + 60/11 minutes a good-looking anwser too? :D

Cheers

A general question, what are the times when hour/minute hand get together during the day (0-12 hours)

1. after X seconds, the hour hand forming angel against 12 o'clock is x/3600 * 360 * 1/12 (1)
2. after X seconds, the minute hand forming angle against 12 o'clock is (x mod 3600) /3600 * 360 (2)
3. equate (1) and (2), and make X is 0 - 12*60*60 (half day in seconds)
4. X can be 0, 3600*12* 1/11, 3600*12*2/11, ... 3600*12*10/11

 

[quantyst]

I am not sure about the close form solution, but this question should be able to calculate using iterate method with following algorithm:

1. define F(n, k) as the way to put n mathematicians in k rooms
2. F(n, 1) = 1; F(1, 1) = 1; F(2, 1) = 4 ( 1,2|0; 1|2; 2|1; 0|1,2)
3. F(n, k) = C(n, 0)*F(n, k-1) + C(n, 1)*F(n-1, k-1) + .. C(n, i)*F(n-i, k-1) + ... + C(n, n)*F(0, k-1); C(n, i)*F(n-i, k-1) means choose i from n, and put them into room 1, and put the rest of n-i mathematician into k-1 rooms
4. computing algorithm to iterate the formula

Albert

Your answer is incorrect, but just about THERE!

Hint: Do you need to include the first term C(n, 0)*F(n, k-1) given that no room is empty?

 

[quantyst]

Here's another way to solve it:

1. assuming there is k-1 cut in the chain to produce k chains, and each chain has S1, S2, ... Sk number of golds.
2. we have S1 = 1 for the first day; and S2 = S1 + 1
3. when I give Sj to the worker on a given day, I expect him to give all S1, S2, ... S(j-1) back to me, so we have Sj = S1 + S2 + ... + S(j-1)
4. the total number of golds are N = S1 + S2 + ... + Sj + ... + Sk = (Sk - 1) + Sk = 2*Sk -1
5. after we get the Sk, we apply 4) backward to retrieve S(k-1) and so on

Your answer is incorrect!

If you have (k-1) cuts in the chain (to produce the k subchains in addition to the (k-1) single cut rings), why then don't you use these (k-1) single cut rings to give out exactly one single cut ring for every day of the first (k-1) days?

 

[glkev]

Your answer is incorrect, but just about THERE!

Hint: Do you need to include the first term C(n, 0)*F(n, k-1) given that no room is empty?

My assumption is the room can be empty.